Homework 3.

Slides:



Advertisements
Similar presentations
不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
Advertisements

高雄師範大學103學年度教育學程招生準備方向 高師大師培中心 凃金堂
第十課 第九味目錄 徐國能 課文 注釋 問題與討論.
狙公 劉基.
天主教善導小學 錦繡中華 --- 專題研習報告比賽 實地考察 福建客家土樓的變與同.
Introduction to C Programming
第二組 組長:16葛詠馨 組員:8張庭瑋、14葉映歡 17鄭琇文、37黃世宣
市直单位财务明细信息表 填报说明 珠海市财政局 2013年12月 1.
Homework (I) Implementing the spread-spectrum watermarking system
漫 步 現 金 流 現金流,這輩子非得瞭解….
第5章 排版的高级应用.
通用技术教学与实践 常德市鼎城区第八中学 刘启红.
50个经典面试问答 主讲:卢秀峰.
创业计划书的编写 白城师范学院创业教育 与文化研究中心 陆东辉.
生物学 新课标.
物流账册系统介绍 2012年5月16日 北京.
經濟部文書作業實務 報告人:何國金.
台灣加油!! 決不放棄!! 加油!! 加油!! 馬英九.
論文心得報告 冷凍二忠 39號 顏酩修.
教育訓練.
第十八章 沟通的真理.
2010年高考语文《考试大纲》对本考点的要求是:“正确使用标点符号。”能力层级为D(表达应用)。
崇右技術學院 電子公文線上簽核系統教育訓練
注重物理基本思想和方法教学 讲究实效 ——2012年高考物理复习备考建议
經國管理學院 電子公文線上簽核系統教育訓練
題目:十六對一多工器 姓名:李國豪 學號:B
Chap5 Graph.
在NS-2上模擬多個FTP連線,觀察頻寬的變化
R教學 安裝RStudio 羅琪老師.
以下這個謎題無法透過宮摒除法完成解題。 但可透過「區塊宮摒除法」或「行列摒除法」完成 By TTHsieh
檔案與磁碟的基本介紹.
數獨教學 ~~By北安國中韓佳瑾.
電腦攻擊與防禦 使用電腦教室VMware軟體說明.
Bandgap reference layout
《新一代數學》(第三版) 六下D冊 20 行程圖.
建立一 function s (type) 可以用來繪製cyclic-harmonic curves
愛惜生命.
味精的妙用 班別:4A 姓名:盧芷桐(23),吳宝怡 (25),余心 穎,(26).
珊瑚白化和全球化之關係 作者:仲士豪、姜少強.
生化實驗 組別 姓名 BCX 結果圖表 結果圖表 結果圖表 結果摘要 (1) (2) (3) 結果圖表 結果圖表 圖表一 說明文字
組員:4960P013 陳佳琪 4960P018 柯琬婷 4960P054 林家瑜 指導老師: 陳碩珮 老師
最短路徑 The Shortest Path.
HTML – 超連結與圖片 資訊教育.
國有公用財產管理簡介 總 務 處 保管組 104年04月07日.
本章結構 網路簡介 最短路徑問題 最小展開樹問題 最大流量問題 10-1.
出生於:1866年11月12日 是中國的革命家,第一任中華民國臨時大總統
數字獨樂樂 --數獨原來這麼簡單.
Quiz7 繳交期限: 12/14 23:59.
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
如何成立公司 組員:洪鼎鈞 謝宜龍 林永貴 曾賴志行.
Chapter 15 檔案存取 LabVIEW中的檔案存取函數也可將程式中的資料儲存成Excel或Word檔。只要將欲存取的檔案路徑位址透過LabVIEW中的路徑元件告訴檔案存取函數後,LabVIEW便可將資料存成Excel或Word檔;當然也可以將Excel或Word檔的資料讀入LabVIEW的程式中。
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
大学计算机基础——周口师范学院 第3章 Word字处理软件 3.8页眉与页脚.
作業
薏仁=益人 20510李佶秝.
國立台灣大學 關懷弱勢族群電腦課程 By 資訊工程 黃振修
1757: Secret Chamber at Mount Rushmore
5432-認知-P-期末-0501 檔案命名規則 課號: 5432 課程名稱:認知與數位教學 作業名稱:認知-P-期末-0501 分組名單
資料結構與C++程式設計進階 期末考 講師:林業峻 CSIE, NTU 7/ 15, 2010.
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
行政救濟實務 -行政訴訟 楊東連 行政救濟實務.
106 Data Structure Homework 4
All Sources Shortest Path The Floyd-Warshall Algorithm
學校:德明財經科技大學 系別/班級:國貿系四年甲班 姓名:彭咨錞 2010/08/26
10440: Ferry Loading II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
指導老師:黃日鉦 組員名單:王友倫.李糧旭.王浩綱.黃種慶.郭宗維
Unix指令4-文字編輯與程式撰寫.
走讀台灣旅遊計畫範本.
JUDGE GIRL 使用介紹 & 常見問題 TAs :
Presentation transcript:

Homework 3

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

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

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

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 點上數字為編號 線上數字為走過去花費的時間

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 點上數字為編號 線上數字為走過去花費的時間

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 點上數字為編號 線上數字為走過去花費的時間

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 點上數字為編號 線上數字為走過去花費的時間

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

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

走過的點,採用”@”表示: S-O-O | | | @-@-@ O-O-D 輸出(求出最佳路徑) 路徑 Cost數

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

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

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

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

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

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

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

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

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

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

例如:點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

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

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