道路速限/線 - 拼圖

※ 引述《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? 說:
你要按"ㄅㄧㄤˋ"它們才會跑啊@@"

--