Re: [請益] 街道型的Two Shortest Path
看板Prob_Solve (計算數學 Problem Solving)作者MrGG (頭有點痛)時間14年前 (2010/05/09 02:06)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/7 (看更多)
P大您好，可能我表達不夠完善@@
╔═══╦═══╦═══╦═Ｄ═╗
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╠═══╬═══╬═══╬═══╣
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╠═══╬═══╬═══╬═══╣
║ ║ ║ ║ ║
║ ○ ║ ║ ║
║ ║ ║ ║ ║
╠Ｓ→→→═○═╬═══╬═══╣
║ ║ ║ ║ ║
║ Ｘ ║ ║ ║
║ ║ ║ ║ ║
╚═══╩═══╩═══╩═══╝
假設現在由S走到D，
當在第一個路口的時候，我可以選擇○兩條路徑行走(最短路徑)
因此，此時會有兩種情境，暫定Case1和Case2
如果走Ｘ的話，則會繞遠路
Case 1 Case 2
╔═══╦═══╦═══╦═Ｄ═╗ ╔═══╦═══╦═══╦═Ｄ═╗
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
╠═══╬═══╬═══╬═══╣ ╠═══╬═══╬═══╬═══╣
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║ ○ ║ ║ ║ ║ ║ ║ ║ ║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
╠═Ｘ═↑═○═╬═══╬═══╣ ╠═══╬═══╬═══╬═══╣
║ ↑ ║ ║ ║ ║ ║ ║ ║ ║
║ ↑ ║ ║ ║ ║ ║ ○ ║ ║
║ ↑ ║ ║ ║ ║ ║ ║ ║ ║
╠Ｓ→→↑═══╬═══╬═══╣ ╠Ｓ→→→→→→→═○═╬═══╣
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
║ ║ ║ ║ ║ ║ ║ Ｘ ║ ║
║ ║ ║ ║ ║ ║ ║ ║ ║ ║
╚═══╩═══╩═══╩═══╝ ╚═══╩═══╩═══╩═══╝
在Case1這部分，到第二個路口時，又可以選擇往上或往右走
但是不能往左邊走，因為此時這樣就會變成繞遠路
在Case2這部分，到第二個路口時，也是可以選擇往上或往右走
但是不能往下走，因為往下走則會變成繞遠路
把問題簡單的來說，就是需要在每個路口判斷<=2條最短的路徑
因為其中一條會是繞遠路
※ 引述《PsMonkey (痞子軍團團長)》之銘言：
: ※ 引述《MrGG (頭有點痛)》之銘言：
: : 請問一下，如果在街道型的Shortest Path 該如何解 (如下圖)
: : ╔═══╦═══╦═══→→Ｄ═╗
: : ║ ║ ║ ↑ ║
: : ║ ║ ║ ↑ ║
: : ║ ║ ║ ↑ ║
: : ╠═══╬═══→→→→↑═══╣
: : ║ ║ ↑ ║ ║
: : ║ ║ ↑ ║ ║
: : ║ ║ ↑ ║ ║
: : ╠═══→→→→↑═══╬═══╣
: : ║ ↑ ║ ║ ║
: : ║ ↑ ║ ║ ║
: : ║ ↑ ║ ║ ║
: : ╠Ｓ→→↑═══╬═══╬═══╣
: : ║ ║ ║ ║ ║
: : ║ ║ ║ ║ ║
: : ║ ║ ║ ║ ║
: : ╚═══╩═══╩═══╩═══╝
: : 假設情境S→D，那麼箭頭所指向的是最短路徑
: 我先往東走到交會點，接著往北一直走到 D 的 y 座標，然後在往東走到 D
: 這樣也是最短路徑.... （應該沒錯吧？）
: 如果這樣的話，這個問題就...
: 先一直走到 Dy - 1（或 +1）
: 然後接著增加（或減少）x 座標，直到等於 Dx，然後再走到 D
: （判斷括號內容也很簡單吧？）
: ㄜ...... 抱歉，我不覺得這是個問題啊... 囧?
: 還是我哪裡誤會 or 你有什麼前提沒有說清楚
: : 那麼如果以街道型的來規劃最短路徑，每條街區長度皆相同
: : 該如何去算出最短路徑?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.175.197.82
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
