Homework 3.

Presentation on theme: "Homework 3."— Presentation transcript:

1 Homework 3

2 題目 給一個交通地圖,從起點走到終點 (1)透過Dijkstra’s algorithm找最佳路徑(30point)
(3)在考慮紅綠燈的情況下,走到終點前要先經過指定的地點(AOV) (30point)

3 (1)透過Dijkstra’s algorithm找最佳路徑(沒有紅綠燈)

4 Dijkstra’s algorithm 範例:從 a 走到 b 先建立一張以 a 為主的時間表，並填上相對耗時 若到達不了則以無限大表示
次數 1(a) 2 3 4 5(b) 6 7 9 ∞ 14 點上數字為編號 線上數字為走過去花費的時間

5 Dijkstra’s algorithm 再來以耗時最少的點為連接點，判斷 a 到各點的時間花費 若比原本的值還小則替換
如下以2為連接點，到3的耗時為17 比原本的9還大則不替換 但到4的耗時為22，則比原本的無限大還小即可替換 由於2無法到達5，因此還是無限大 次數 1(a) 2 3 4 5(b) 6 7 9 ∞ 14 1 22 點上數字為編號 線上數字為走過去花費的時間

6 Dijkstra’s algorithm 接下來以3為連接點，到2的耗時為19比7還大不替換 到4的耗時為20比22小，因此做替換
到6的耗時為11比14小，也可以做替換 次數 1(a) 2 3 4 5(b) 6 7 9 ∞ 14 1 22 20 11 點上數字為編號 線上數字為走過去花費的時間

7 Dijkstra’s algorithm 接下來以6為連接點，因為剩456沒做，而a到6耗時最少 這邊要懂一個概念
只要看6連出去的點即可，所以6有連到1, 3, 5 到1的耗時為25比11還大不替換 到3的耗時為13比11還大不替換 到5的耗時為20比無限大小因此做替換 次數 1(a) 2 3 4 5(b) 6 7 9 ∞ 14 1 22 20 11 點上數字為編號 線上數字為走過去花費的時間

8 Dijkstra’s algorithm 接下來以4為連接點 到2的耗時為35比7還大不替換 到3的耗時為31比9還大不替換
到5的耗時為26比20還大不替換 我們可以發現到4的最低耗時是20，比表上其他點大 所以這次其實可以直接pass 次數 1(a) 2 3 4 5(b) 6 7 9 ∞ 14 1 22 20 11 點上數字為編號 線上數字為走過去花費的時間

9 Dijkstra’s algorithm 所以最後我們的得到a點到各點的最低耗時 而目標是到b點的，由表上可以看出是20 次數 1(a) 2
3 4 5(b) 6 7 9 ∞ 14 1 22 20 11 點上數字為編號 線上數字為走過去花費的時間

10 輸入 地圖(課程網頁上會提供10*10的地圖) 其中每個點用“Ｏ”表示,起點用”S”表示,終點用”D”表示,每個邊用 “ -”或”|”(“-”代表水平邊,”|”代表垂直邊)表示 例如給一個3*3的地圖,在console的表示為: S-O-O | | | O-O-O O-O-D

11 S-O-O | | | O-O-D 輸出(求出最佳路徑) 路徑 Cost數

12 (2)在每個十字路口加入紅綠燈,找出最佳解

13 紅綠燈 每個紅綠燈有兩個狀態: 綠燈與紅燈 wait 綠燈可以直行,左右轉 不是只能直走 紅燈不能移動, 等到綠燈才能移動

14 4 3 1 4 3 如左圖，每點都一個紅綠燈 每個紅綠燈的編號跟點的編號一樣 例如點2上面的紅綠燈 在表格內的編號為2
起始狀態為目前的燈號顏色 燈號倒數為再過幾秒會變燈 點1 點2 點3 5 7 2 8 3 點4 點5 點6 5 6 1 4 紅綠燈編號 起始狀態 燈號倒數 紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

15 3 4 在來是求點1走到點6的最佳路徑 5 7 2 8 3 5 6 1 點1 點2 點3 點4 點5 點6 紅綠燈編號 起始狀態 燈號倒數
紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

16 7 5 4 3 點1走到點2時，時間為5秒 此時點2以變為綠燈 所以可以從點2走到點3或走到點5 或者往回走 5 7 2 8 3 5 6
點4 點5 點6 5 6 紅綠燈編號 起始狀態 燈號倒數 紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

17 X X X 2 4 點2走到點5時，時間過了3秒 此時點5為紅燈，所以不能移動 5 7 2 8 3 5 6 1 點1 點2 點3 點4 點5
點6 5 6 紅綠燈編號 起始狀態 燈號倒數 紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

18 5 8 1 4 5 7 要過4秒後才能移動 2 8 3 5 6 點1 點2 點3 點4 點5 點6 紅綠燈編號 起始狀態 燈號倒數
紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

19 6 2 移動到點6時，時間為18秒 若是不考慮紅綠燈 只要花13秒 5 7 2 8 3 5 6 3 點1 點2 點3 點4 點5 點6
紅綠燈編號 起始狀態 燈號倒數 紅燈持續時間 綠燈持續時間 2 Red 4 8 3 Green 7 1 5

20 輸入 輸出(求出最少時間路徑) 地圖(課程網頁上會提供5*5的地圖) 其中點的表示方式跟上題一樣, 紅綠燈狀態圖(課程網頁上會提供) 路徑
Cost數

21 (3)在考慮紅綠燈的情況下,走到終點前要先經過指定的地點(AOV)

22 例如:點1走到點6的最短距離 但是要先經過點4才能經過點6 所以最短路徑為 點1->點4->點5->點6 5 7 2 8
點2 點3 5 7 2 8 3 點4 點5 點6 5 6 紅綠燈編號 起始狀態 燈號倒數 紅燈持續時間 綠燈持續時間 2 Green 4 3 7 Red 1 5

23 輸入 輸出(求出最少時間路徑) 地圖(課程網頁上會提供6*6的地圖) 其中點的表示方式跟第一題一樣, 紅綠燈狀態圖(課程網頁上會提供) 路徑
Cost數

24 請寫word檔說明你的作業步驟,如果你的程式不符合規定,你的word檔 請寫出你做到什麼地步斟酌給分 寄信主旨請打以下格式
HW3_學號_姓名(不合規定斟酌扣分) 用ZIP壓縮word及程式碼(檔名請打你的學號) 請寄到 Deadline 2017/12/25 用Yahoo信箱我好像收不到 不管你要用什麼寫,請你確定可以在Dev-C++上執行再寄給我 Code請不要貼在txt或word檔,我一定扣分 抄襲嚴懲 , 請打上註解不然不計分