作者yauhh (喲)
看板Prob_Solve
標題Re: [請益] 街道型的Two Shortest Path
時間Sun May 9 02:28:44 2010
※ 引述《MrGG (頭有點痛)》之銘言：
: ╔═══╦═══╦═══╦═Ｄ═╗
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠═══╬═══╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠═══╬═══╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ ○ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠Ｓ→→→═○═╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ Ｘ ║ ║ ║
: ║ ║ ║ ║ ║
: ╚═══╩═══╩═══╩═══╝
: 假設現在由S走到D，
: 當在第一個路口的時候，我可以選擇○兩條路徑行走(最短路徑)
: 因此，此時會有兩種情境，暫定Case1和Case2
: 如果走Ｘ的話，則會繞遠路
這沒有可煩惱的. 路網表達為圖就是
.----.----.----.-.--.
| | | | D |
.----.----.----.----.
| | | | |
.----.----.----.----.
| | | | |
.-.--.----.----.----.
| S | | | |
.----.----.----.----.
固定路段權重都一樣, S與D局部路段用內插法分配權重,
然後用一般的選路法,選就對了.
繞路這種事,在選路法中會自動避開.
而如果你想的是人的選擇,就是另外一個比較複雜的問題了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.209.141
1F：推 MrGG:考慮的就是人的選擇...，所以必須在路口提供<=2條最短路徑 05/09 02:32
2F：→ MrGG:給人選擇... 05/09 02:32
3F：→ yauhh:我猜你可能也想要將路線限制,例如何處禁止左轉,加入考慮範圍 05/09 02:43
4F：→ yauhh:大概就路線,匣道限制限定的路網先定好,然後把交通情況定為 05/09 02:45
5F：→ yauhh:像權重那樣的動態影響因素,這時才來看人的決策模型... 05/09 02:46
6F：推 MrGG:目前還沒想到路線限制，想看看能不能算出<=2條最短路線 05/09 02:47
7F：推 MrGG:當初的想法是，因為路線在規劃時，假設使用GPS.. 05/09 02:49
8F：→ yauhh:但現在看起來並沒有明確定義路網的情況下,你說要<=2條路徑, 05/09 02:49
9F：→ MrGG:GPS會推出一條最短路徑，那麼如果遇到塞車或是前方車禍的情形 05/09 02:49
10F：→ yauhh:這個方法不對喔 05/09 02:49
11F：→ MrGG:會在推出另外一條最短路徑.. 05/09 02:50
12F：→ yauhh:那你就要定義這種影響因素化為參數,如何傳播並影響路線權重, 05/09 02:51
13F：→ yauhh:才做得下去. 05/09 02:51
14F：推 MrGG:但是像塞車這類情況必須由人判斷，如果沒塞車，也是有可能換 05/09 02:56
15F：→ MrGG:路線，所以目前只有想說如何在每個路口提供一條最短路徑 05/09 02:57
16F：→ yauhh:當你要說遠近的時候,只能看路線配置及路線權重,所以像前面 05/09 02:59
17F：→ yauhh:你說"不能繞遠路",顯然是普通選路法已經能解決的事情,這就 05/09 03:00
18F：→ yauhh:顯得你的問題不明確. 05/09 03:00
19F：→ yauhh:嗯..人為判斷塞車的意思,就是...在眼前看到塞車時,就按一下 05/09 03:04
20F：→ yauhh:GPS,叫它重算目前位置到目的地的路徑... 05/09 03:05
21F：推 MrGG:但是，GPS重新規劃需要有一段時間，所以我必須在每個路口先 05/09 03:10
22F：→ MrGG:估計出可能的最短路徑 05/09 03:10
23F：推 PsMonkey:純亂罵：你這樣前提假設根本沒說清楚... [攤手] 05/09 06:28
24F：→ yauhh:如果你要事先估好,這叫預測.而預測的可怕之處是難以衡量 05/09 10:37
25F：→ yauhh:模擬系統是否符合真實系統的行為,很難找理由解釋清楚. 05/09 10:38
26F：→ yauhh:在此不是喜歡否定你而已,而是告知一些你的研究可能會遭遇的 05/09 10:40
27F：推 MrGG:所以，我的系統是希望S走到D的時候，能夠行走最短路徑.. 05/09 10:40
28F：→ yauhh:障礙,也許你在前期是比較不會先想到. 05/09 10:40
29F：推 MrGG:當初的構想是，因為人們在都市使用GPS導航，但是GPS的重新 05/09 10:42
30F：→ MrGG:定位需要一段時間，然後封包在傳遞時，盡可能的不要中斷 05/09 10:43
31F：→ MrGG:所以才想要找出另一條可能的最短路徑，防止駕駛臨時變換路線 05/09 10:44
32F：→ MrGG:所以當GPS導航出一條路線時，在每個路口，需要找出另一條可能 05/09 10:45
33F：→ MrGG:的最短路線，以防止駕駛者臨時改變路線 05/09 10:45
34F：→ MrGG:然而找過一些資料，在道路的拓墣上幾乎道路長短皆不同 05/09 10:48
35F：→ MrGG:因此很容易規劃出最短路線，然而我想到的是使用田字型來減少 05/09 10:48
36F：→ MrGG:未來模擬時的複雜度，但是 衍伸出的就是每條路的長度皆相同 05/09 10:49
37F：→ MrGG:不知道該怎麼去算出最短路線 05/09 10:49
38F：推 stimim:田字形的只要一直朝目標走就是最短了不是嗎? 05/09 11:01
39F：→ stimim:如果 D-S = (a,b) 在走的時候就要讓 |a|,|b| 減少 05/09 11:03
40F：→ stimim:因此a>0的時候不能向 -x 方向走，b>0的時候不能向-y方向走 05/09 11:04
41F：→ yauhh:路段長度是天生的權重,照著選路法做一定有答案,當然不只一條 05/09 11:05
42F：→ yauhh:最短的. 05/09 11:05