尋路算法難度

修改A *算法我們爲減少匝數優化。該算法現在將找到從（a，b）到任何TILE ADJACENT TO（x，y）的路徑，其中（x + 1，y）或（x-1，y）在可能的情況下傾向於。

我嘗試的解決方案：

運行從原來的A *算法（A，B）到（x，y）的。
找到經過（x-1，）或（x + 1,）（如果有的話）的路徑中的最後一個座標。
如果在該座標平面中存在從*到y的直線可訪問垂直線，請修改該路徑以跟隨該線。

視覺演示：（來自S對路徑e其中X是無法訪問）

......S   .....S 
.  X   . X 
.   =>  .  
.     . 
E    E.

但是我不知道我的解決方案會在某些情況下工作，即：

......S   .....S 
.  X   . X 
.X  ???  X.  
.     . 
E    E..

任何人都可以想出解決這個問題的辦法嗎？

注意：A *算法是通用的，不同於考慮方向更改的數量，以減少生成路徑中的轉彎次數。

來源

2012-04-14 whats canasta

什麼是「儘可能喜歡」的意思？這是否意味着如果存在與（x + 1，y）和（x，y + 1）等長的路徑，那麼必須找到（x + 1，y）的路徑？或者這是否意味着如果有一條通往（x + 1，y）的路徑，它必須被找到，即使更長？另外鄰居是什麼意思？（x + 1，y + 1）是否相鄰？ – btilly 2012-04-14 21:37:54

只有當它仍然是最短路徑時，纔有可能意味着。相鄰不包括對角線。 – 2012-04-14 21:41:29

我的朋友建議：1.查找返回的路徑是否經過了x + 1或x-1平面。 2.從開始運行A *到（x + 1，y）或（x-1，y）（無論哪一側更靠近）。如果生成的路徑更短，則返回它。這似乎根據我的測試給出了正確的解決方案，但基本上需要兩次運行算法。好奇，如果有什麼更優雅的。 – 2012-04-14 21:43:37

A *實際上是Dijkstra's algorithm知情的版本，因此它實際上是[與admissible heuristic功能]旨在找到最短路徑，所有頂點 [從單一來源。

可以定義鄰近(x,y)作爲目標頂點[A *能巧妙地處理多個目標]所有的瓷磚，你也將需要修改啓發函數，給一個允許值到任何目標節點。這可以通過簡單修改h'(tile) = max { h(tile) - 1 , 0}來完成 - 但在某些情況下，您可能有更好的方法來完成。

建立在上述過程之後，我們可以得出以下修改原來的A *：

潤A *，直到找到目標圖塊後延到目標小塊[路徑，作爲如上所述]。讓路徑的長度爲d。
現在，繼續運行A*與當前狀態，直到開放節點的最小值 f(tile)嚴格大於d。 你是保證找到所有可從源到達的路徑長度爲d的路徑，具體來說 - 您將找到所有具有來自長度爲d的路徑的目標瓦片。 [假設可接受的啓發式功能]。
從所有這些瓷磚中，您可以選擇「首選」，並返回一個路徑給他們。如果找不到首選磁貼，則返回一個路徑到任意目標磁貼。

我希望有幫助！

來源

2012-04-14 21:45:53 amit

謝謝你的建議，我必須咀嚼它，看看我是否可以得到這個工作。 – 2012-04-14 22:09:44

修改啓發式功能，使點(x+1,y)和(x-1,y)略有提升。然後，如果你在完成路線的兩個步驟，關係將被打破，贊成這2點。

來源

2012-04-15 22:17:56 btilly

尋路算法難度

回答

相關問題