※ 引述《yjd (le petit prince)》之銘言： : 現在有一地區道路規劃如下 : (1,1) : ↘10 20 30 40 50 60 (單位:km/hr) : 10 ┌──┬──┬──┬──┬──┐ : │ │ │ │ │ │↖ (6,1) 所有道路以棋盤格方式排列 : │ │ │ │ │ │ : 20 ├──┼──┼──┼──┼──┤ 行走方向不限 : │ │ │ │ │ │ : │ │ │ │ │ │ (東西 南北 雙向皆可通) : 30 ├──┼──┼──┼──┼──┤ : │ │ │ │ │ │↖ (6,3) 每條道路有其速限 : │ │ │ │ │ │ : 40 ├──┼──┼──┼──┼──┤ 標示在最上端 (縱向道路速度) : │ │ │ │ │ │ 及最左端 (橫向道路速度) : │ │ │ │ │ │ : 50 ├──┼──┼──┼──┼──┤ e.g.從(1,1)→(3,1)→(3,2) : │ │ │ │ │ │ ↑ ↑ : │ │ │ │ │ │ 行車速度必須從10km/hr→30km/hr : 60 └──┴──┴──┴──┴──┘ : ↗ ├──┤ ↗ (假設速度可在瞬間轉換) : (1,6) 10km (6,6) : 每條道路皆為10公里 : 請問: : (i) 現在要從(1,1)走到(6,3),所需最短時間為多少? 路徑要如何走? : (ii)如果現在想將所有交叉路口都走過並且只能走過一次(道路不必全走過) : 所需最短時間又為多少? 路徑要如何安排? (以(1,1)為起點) (1)的部份頗類似演算法裡的Shortest-path問題 於是我利用這個方法來做 得到的答案是200分鐘: [ 0]→[ 60]→[ 120] [ 165] [ 192] [ 220] ↓ ↓ ↑ ↑ ↑ [ 60]→[ 90]→[ 120]→[ 150]→[ 180]→[ 210] ↓ ↓ ↓ ↑ [ 120] [ 120]→[ 140]→[ 160]→[ 180]→[ 200] ↓ ↓ ↓ [ 165]←[ 150] [ 160]→[ 175]→[ 190]→[ 205] ↓ ↓ ↓ ↓ [ 192]←[ 180] [ 180] [ 190]→[ 202]→[ 214] ↓ ↓ ↓ ↓ ↓ [ 220]←[ 210]←[ 200] [ 205] [ 214]→[ 224] 箭頭代表走法 (2) 我目前只能想到這種走法: １→２　９→10　25→26 　　↓　↑　↓　↑　↓ ４←３　８　11　24　27 ↓　　　↑　↓　↑　↓ ５→６→７　12　23　28 　　　　　　↓　↑　↓ 16←15←14←13　22　29 ↓　　　　　　　↑　↓ 17→18→19→20→21　30 　　　　　　　　　　↓ 36←35←34←33←32←31 費時60*5+30*2+20*4+15*6+12*8+10*10=726分鐘 基本想法是盡量不要用到60分鐘(速度10km/hr)的路 然後一圈圈往外 盡量利用目前能用的最快路線 不要回頭走 (會用到慢速度的路浪費時間) 至於還有沒有更快的就要再找找了 -- [LPH] Oops, your OOP's a problem? 說: 你現在還是看不到狗? ************* 說: 看得到 只是 他們不會跑 就一直呆呆在那邊 一直在起點 [LPH] Oops, your OOP's a problem? 說: 你要按"ㄅㄧㄤˋ"它們才會跑啊@@" --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.91.5