Re: [問題] 考慮禁轉的最短路徑演算法...
※ 引述《archon (三腳貓的把戲)》之銘言:
: 一般常用的最短路徑演算法就是 Dijkstra Algorithm,
: 原理相信各位前輩都比我清楚,就不在此贅述了。
: 不過,在實際應用上,有時會遇到某些路徑的限制(譬如說道路的禁轉),
: 某些該 relax 的點被限制不能拜訪,就破壞了 Dijkstra 演算法的特性。
: 舉個例子來說:
: | | 假設 A->B->F 這是一個禁左轉的路口,
: ---C---D--- Dijkstra 是無法規劃出 A->B->C->D->E->B->F 這樣的結果。
: | |
: F---B---E---
: | |
: A
: 請問這樣子的問題,是被稱做什麼樣的問題呢?有關鍵字嗎?
: 或者是,有什麼演算法適用這種問題呢?
這樣的話我會把 B 拆成四個點
B1 B2 B3 B4
分別有四個方向的單向邊連進來
連出去則是可以轉的方向
所以就會變成
A→B1→E,C
E→B2→C,F
C→B3→F,A
F→B4→A,E
這樣就可以正確跑出 A→B1→C→D→E→B2→F 的路線
--
実琴:「河野!你真的就這樣被物質慾望給吸引過去了嗎?!」
亨:「只要穿著女裝擺出親切的樣子,所有必要花費就能全免,似乎一點都不壞啊。」
実琴:「難道你沒有男人的尊嚴了嗎?!」
亨:(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前,沒有那種東西。」
--プリンセス・プリンセス 第二話
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
→
03/15 15:47, , 1F
03/15 15:47, 1F
推
03/15 15:51, , 2F
03/15 15:51, 2F
→
03/16 13:38, , 3F
03/16 13:38, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):