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

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

看板Prob_Solve (計算數學 Problem Solving)作者ckaha (★閃亮數學推理★)時間14年前 (2010/05/12 23:23)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串7/7 (看更多)

高中數學會告訴你本題的捷徑走法會是 5!/(2!3!) = 10種中間你想要怎麼走就怎麼走反正就是5步打死右右上上上看你喜歡用哪個演算法都可以用不想用演算法直接座標點對減看X差多少 Y差多少看喜歡先水平移動還是垂直移動就好了 ※ 引述《MrGG (頭有點痛)》之銘言： : 請問一下，如果在街道型的Shortest Path 該如何解 (如下圖) : ╔═══╦═══╦═══→→Ｄ═╗ : ║　　　║　　　║　　　↑　　　║ : ║　　　║　　　║　　　↑　　　║ : ║　　　║　　　║　　　↑　　　║ : ╠═══╬═══→→→→↑═══╣ : ║　　　║　　　↑　　　║　　　║ : ║　　　║　　　↑　　　║　　　║ : ║　　　║　　　↑　　　║　　　║ : ╠═══→→→→↑═══╬═══╣ : ║　　　↑　　　║　　　║　　　║ : ║　　　↑　　　║　　　║　　　║ : ║　　　↑　　　║　　　║　　　║ : ╠Ｓ→→↑═══╬═══╬═══╣ : ║　　　║　　　║　　　║　　　║ : ║　　　║　　　║　　　║　　　║ : ║　　　║　　　║　　　║　　　║ : ╚═══╩═══╩═══╩═══╝ : 假設情境S→D，那麼箭頭所指向的是最短路徑 : 如果S走到第一個十字路口時，不依照箭頭所指的路線 : 而繼續前進，該怎麼在求出最短路徑呢? : 找過一些有關最短路徑的演算法，EX.Dijkstra..等等 : 但是，這些演算法所預設的路線長度皆不同 : 所以可以依據路線長度來計算出最短路徑 : 那麼如果以街道型的來規劃最短路徑，每條街區長度皆相同 : 該如何去算出最短路徑? : 曾經有想過要以角度來規畫出最短路徑， : 但是，後來想到如果S和D在不同象限的話 : 那麼可能推出來的就不太一樣了 : 不曉得各位有沒有甚麼比較好的想法呢? -- Every thing can be wrong unless you can proof it is true. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.109.16.227