單向的最短距離路線(筆記)

昨天去聽一門北一女中的選修課，是成大數學系許瑞麟教授授課，他給的題目是由下圖的結點①到結點⑨，所經過的最短距離路徑(或花最短時間的路線)，每條路線上的數字當作長度(或所花的時間)。

許教授有講解一個解題的algorithm，我邊聽邊想，找到一個解決這個問題的方法：

對於每一個結點 j，我記錄所有從結點1到達結點 j 的路線長度，取其最小值。取最小值的動作是在每一個結點都要做。

所以我這樣做：先把結點i會到達結點 j 的路徑長度記為a_ij，寫成一個上半矩陣。

第一步：先寫出相連兩結點的路徑長，如下：

	①	②	③	④	⑤	⑥	⑦	⑧	⑨
①		1	2
②				6	12
③				3		4
④					4	3	15	7
⑤							7
⑥								7	15
⑦									3
⑧									10
⑨

第二步：記錄所有的a_1j，取最小值，記法如下：

 所以，最短路徑可記為：

即①→③→④→⑤→⑦→⑨為最短的路線，距離和為19單位。

不過，如果路線改成雙向的，似乎無法用這個方法來處理，或是需要再修正，我還要再想一想。

一道固定點的問題(筆記)

上禮拜去參加一場「差異化教學」的研習，左台益教授在演講的過程中提到他曾在師大的通識課裡，給了學生一道有趣的問題，題目大概是這樣的：

海盜搶了寶藏後，想在一個小島上埋寶藏，他從椰子樹下T走到一塊大石頭A處，順時針方向旋轉90°，走相同的距離到達C點，再從C點走到另一塊大石頭B點處，順時針方向旋轉90°，再走相同的距離到D點，然後在D和T的中點M處埋下寶藏。但因颱風之故，椰子樹被吹倒不見了，一年後海盜來到島上，只見大石頭A和B，請問他要怎麼找到寶藏？

我的想法是這樣：

顯然，從題意來看，如果椰子樹T消失了，如果海盜還能找到寶藏，那就表示埋寶藏P的地點一定和T無關，只能跟A和B有關，所以P應該是一個固定點(fixed point)。所以，在複數平面上考慮，令A(0)，C(z₁)，B(z₂)。因為T為C對A順時針旋轉90°，故T(－iz₁)，又D為C對B逆時針旋轉90°，故D(z₂＋i(z₁＋z₂))，所以，與C(z₁)和T(－iz₁)無關。所以把任意一點當成原本的椰子樹，照著原本埋寶藏的方法去尋找，就可以找到寶藏了。如果把這「任意一點」取大石頭A點，則寶藏的的位置即A對B逆時針方向旋轉90°後，再和A取中點的地方，這也就是M點座標所表示的意思。

鬼腳圖公平嗎？

最近忙著調整一些人生的規畫，都沒有在部落格發表文章，前幾天拿自己曾在學校刊物上發表的文章看一看，干脆把其中一篇放上來。

鬼腳圖是一種常被拿來取代抽籤的遊戲，例如A、B、C、D四個人，要抽a、b、c、d四支籤，可以畫四條縱線，在線的下方任意排上a、b、c、d，再在縱線之間任意畫一些橫線，這些橫線連接相鄰的縱線，但不可橫跨兩條以上的縱線，A、B、C、D四人則各自挑選一條縱線，由最上方當起點往下走，遇到橫線就必需轉彎，到達底端的位置即為所挑中的籤。如圖，則A抽中a，B抽中d，C抽中b，D抽中c：(較粗的線段即為C所走的路線)

學期初的時候，老師們總是要討論週考、段考要由誰命題，有時候會用抽籤決定，這學期有老師說：「不如來用鬼腳圖吧！」於是我提出一個放在心裡一陣子但沒仔細去思考的問題：「鬼腳圖公平嗎？」。

就以四條縱線的情況，先設定基本條件：縱線與縱線之間的橫線高低均不同，且共有n條橫線，n條橫線放在每個位置的機會均等。因每一條橫線都有可能放在和之間、和之間、和之間，故共有3ⁿ種不同的排列方式，假設這3ⁿ種的排列方式發生的機會均等，那麼在不知道n條橫線怎麼排列的情況下，由A出發到達a、b、c、d的機率就一定不同( 不會整除)。同理，由B或C或D出發，抵達各終點的機率也不同。那麼，實際上的機率該怎麼計算呢？(這裡的「機率」指的只是所使用的鬼腳圖選定的起、終點在所有含n條橫線的鬼腳圖中的比例。)

假設由A出發到a、b、c、d的機率分別為P_A,a(n)、P_A,b(n)、P_A,c(n)、P_A,d(n)，這裡的n指的是共有n條橫線(叉路)。由於有n條橫線的情況，相當於原有(n－1)條橫線的情況再搭配最後一條(第n條)橫線擺在和之間，或和之間，或和之間，故到達a的位置的機率可想成：

(1)若是第n條橫線在和之間，則最後要到達a，必先經過前(n－1)條橫線後走到縱線，再經由第n條橫線走到a，這種情況的機率為；

(2)若是第n條橫線在和之間或是在和之間，則最後要到達a，必先經過前(n－1)條橫線後走到縱線，不需理會第n條橫線，直接走到a，這種情況的機率為；

由(1)和(2)的情形可以得知：

 同樣的方式討論可以得到：

 

反過來思考，無論從A、B、C、D哪一個點出發，若過(n－1)條橫線後留在縱線上，則：(1)假如第n條橫線在和之間或和之間，則最後的終點會在a，其機率為2/3；(2)假如第n條橫線在和之間，則最後的終點會在b，其機率為1/3。若其機率向量為v₁，則v₁^T＝(2/3, 1/3, 0, 0)。同理，若過(n－1)條橫線後留在縱線上，其機率向量為v₂，則v₂^T＝(1/3, 1/3, 1/3, 0)；若過(n－1)條橫線後留在縱線上，其機率向量為v₃，則v₃^T＝(0, 1/3, 1/3, 1/3)；若過(n－1)條橫線後留在縱線上，其機率向量為v₄，則v₄^T＝(0, 0, 1/3, 2/3)，因此可寫出轉移矩陣 ：

故可以得到：

 實際上，我們可以列出：

 運用一點線性代數的技巧，可得

最後可以留意一下這個有趣的矩陣，只要n為正整數，這個矩陣的每一個元都是有理數，且當n→∞時，每個元的極限值都是1/4。也就是說，只要橫線數夠多，由每個起點出發，到達各終點的可能性愈接近。

還是要提醒一下，如果已經完整畫出鬼腳圖的情況下，起點和終點的位置就早已固定了，那就沒什麼機率的問題，這裡所談的「機率」，只是考慮4條縱線n條橫線所有可能的鬼腳圖中，給定起點而去討論終點可能發生的位置比例。