半夜過橋(Bridge and Torch Problem)

問題一

有一座橋沒有路燈每次只能有兩個人通行, 半夜過橋沒燈會怕怕, 現在有五個人, 他們過橋的速度分別是 1, 3, 6, 8, 12 分鐘, 他們只有一盞可以點燃 30 分鐘的燈籠, 如何才能讓這五個人順利過橋呢?

問題二

當有六個人過橋速度分別是 2, 3, 8, 15, 18, 19 他們至少要花幾分鐘過橋呢?

# perl math03.pl 6 0 2 3 8 15 18 19
People Cost List:
1:(2) 2:(3) 3:(8) 4:(15) 5:(18) 6:(19)
Finish..100000!
Finish..200000!
Finish..300000!
Total Case:324000
Min. Cost :53

問題三

當有七個人過橋速度分別是 4, 8, 8, 9, 9, 9, 13 他們至少要花幾分鐘過橋呢?

# perl t.pl 7 3 4 8 8 9 9 9 13
People Cost List:
1:(4) 2:(8) 3:(8) 4:(9) 5:(9) 6:(9) 7:(13)
Guess Min. Cost:76
Total Time:29 sec
Min. Cost :76

推論公式

推論 min. cost 公式: (需要先將過橋時間由小到大排列)
2個人: (2) [2]
3個人: (6) [1]+[2]+[3]
4個人:
- 4a:(11) [1]*1+[2]*3+[4]
  1. 最快的兩個[1][2]先過去(2), 其中一個[1]回來(2+1)
  2. 最慢的兩個[3][4]再過去(2+1+4), 另一個[2]快的回來(2+1+4+2) (完成最慢兩個[3][4]過去)
  3. 最快的兩個[1][2]再過去
- 4b:(11) [1]*2+[2]+[3]+[4]
  1. 最快[1]和最慢[4]先過去(4), 最快的[1]回來(4+1)
  2. 最快[1]和第二慢[3]的過去(4+1+3), 最快的[1]回來(4+1+3+1) (完成最慢兩個[3][4]過去)
  3. 最快的兩個[1][2]再過去
- 所以當 ([1]+[2]*2+[4] < [1]*2+[3]+[4]) 採用 4a 方式, 否則就採用 4b 方式
5個人:
- 先取最快兩個 [1] [2] 與最慢兩個 [4] [5] 來進行 4a 4b 的比較方式, 將最慢兩個 [4] [5] 送過去
- 之後就變成 [1] [2] [3] 3個人的問題了
6個人:
- 先取最快兩個 [1] [2] 與最慢兩個 [5] [6] 來進行 4a 4b 的比較方式, 將最慢兩個 [5] [6] 送過去
- 之後就變成 [1] [2] [3] [4] 4個人的問題了

產生的程式碼

https://svn.ichiayi.com/opensvn/opentrysoft/math/math03.pl

產生的結果

三個人過橋
四個人過橋
五個人過橋
六個人過橋
七個人過橋

載入中 ...

→ 此頁連結

三個人過橋

呈現所有過程資訊, 隨機提供三個人的過橋時間

# perl math03.pl 3 2
People Cost List:
1:(13) 2:(20) 3:(2)
[000](0) - L:[ 1 2 3 ] R:[ ]
[1, 2] -> (0)+(20)
        [110](20) - L:[ 3 ] R:[ 1 2 ]
<- [1] (20)+(13)
                [010](33) - L:[ 1 3 ] R:[ 2 ]
[1, 3] -> (33)+(13)
                        [111](46) - L:[ ] R:[ 1 2 3 ]
Finish..1! (46)
<- [2] (20)+(20)
                [100](40) - L:[ 2 3 ] R:[ 1 ]
[2, 3] -> (40)+(20)
                        [111](60) - L:[ ] R:[ 1 2 3 ]
Finish..2! (60)
[1, 3] -> (0)+(13)
        [101](13) - L:[ 2 ] R:[ 1 3 ]
<- [1] (13)+(13)
                [001](26) - L:[ 1 2 ] R:[ 3 ]
[1, 2] -> (26)+(20)
                        [111](46) - L:[ ] R:[ 1 2 3 ]
Finish..3! (46)
<- [3] (13)+(2)
                [100](15) - L:[ 2 3 ] R:[ 1 ]
[2, 3] -> (15)+(20)
                        [111](35) - L:[ ] R:[ 1 2 3 ]
Finish..4! (35)
[2, 3] -> (0)+(20)
        [011](20) - L:[ 1 ] R:[ 2 3 ]
<- [2] (20)+(20)
                [001](40) - L:[ 1 2 ] R:[ 3 ]
[1, 2] -> (40)+(20)
                        [111](60) - L:[ ] R:[ 1 2 3 ]
Finish..5! (60)
<- [3] (20)+(2)
                [010](22) - L:[ 1 3 ] R:[ 2 ]
[1, 3] -> (22)+(13)
                        [111](35) - L:[ ] R:[ 1 2 3 ]
Finish..6! (35)
Total Case:6
Min. Cost :35

結論

可透過遞迴方式來產生所有可能的狀況來計算出每個狀況所需花費的時間
出現最少時間的狀況有可能會超過一個
只要推論 2個人, 3個人, 4個人, 5個人, 6個人就可以獲得之後所有人數的 Min. Cost 計算方式