PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] 街道型的Two Shortest Path

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