如何讓我的路徑尋找算法不會相反？

我的路徑查找方法有兩個對象，其中包含存儲在數組列表中的標識，名稱，x/y座標和路徑。路徑數據是它可以直接連接到的每個對象的ID。我們的目標是遞歸地調用我的方法，直到它找到使用最短距離的目標，並且當它到達結尾時它將返回true。如何讓我的路徑尋找算法不會相反？

問題：如果到達節點的距離比當前節點路徑中的其他節點短，則會導致無限循環在兩個節點之間來回跳動。我一直在努力解決這個問題幾個小時，可能會過度思考。任何意見或建議將不勝感激！

算法：

while (!pathfound) { 
    current = findPath(current, end); 
} 

public static Place findPath(Place curPlace, Place endPlace) { 
    ArrayList<Integer> path = curPlace.path; 
    int id; 
    double lastdist = 999; 
    double distance; 
    Place bestPlace = null; 

    for (int i = 0; i < path.size(); i++) { 
     id = curPlace.path.get(i); 
     distance = distance(getPlace(id), curPlace) 
       + distance(getPlace(id), endPlace); 
     if (distance < lastdist) { 
      bestPlace = getPlace(id); 
     } 

     lastdist = distance; 
    } 

    if (result.length() == 0) { 
     result += bestPlace.name; 
    } else { 
     result += ", " + bestPlace.name; 
    } 

    System.out.println("CURCITY: " + bestPlace.id); 
    System.out.println(result); 
    System.out.println(lastdist); 

    if (bestPlace == endPlace) { 
     pathfound = true; 
    } 

    return bestPlace; 
}

可以忽略的結果，它是保持與所傳遞的節點。如果您還想了解其他任何細節，請詢問。

來源

2014-02-22 billabrian6

如果修改Place是可以接受的，則可以添加一個布爾型「visited」標誌。在運行算法之前將它們全部重置爲false;在訪問時設置爲true，在離開時設置爲false（不要忘記在退出的時候將它們取消設置 - 如果正確執行此操作，則可以避免在啓動之前顯式重置標誌）。跳過標誌爲true的節點。

一個更近視的選擇是將上次訪問的Place作爲參數傳遞給函數，並跳過該函數。這不會阻止較大的循環，但可能完全適合您的情況並且是最簡單的實現。

以上都是O（1），開銷很小。如果您無法修改Place，則可以存儲訪問過的地點的Set（在遞歸過程中將其從集合中移除），並跳過已經在該集合中的地點。根據你的性能要求，如果你使用HashSet，你會想出一個合適的哈希函數。

沿着這些路線，犧牲更多的內存，如果您的身份證號碼是唯一的並且覆蓋了合理大小的有限範圍，那麼由ID號碼索引的boolean[]是一個恆定時間替代這裏的一個集合（它本質上是「訪問「標誌選項與外部存儲標誌）。

來源

2014-02-22 21:37:26

感謝您花時間幫忙！我可以修改地方，我其實是試圖做一些類似的布爾標誌和一個額外的方法來檢查，如果訪問。我擔心這會導致同樣的問題。我一直收到空指針，因爲bestPlace被設置在循環內部，然後被結果使用。這可能是因爲我的邏輯關閉了，但我不確定如何使用標誌來構造代碼。 – billabrian6

@ billabrian6我也建議使用訪問'地點'的'Set'。 – ggovan

@ billabrian6你還沒有發佈完整的遞歸算法，所以很難給出任何更具體的建議。一般來說，使用標誌方法時，遞歸函數首先檢查標誌，如果它爲假，則將其設置爲true，然後在返回之前再次將其設置爲false。該標誌實質上意味着「現在引用這個地方是否有堆棧上的遞歸函數」。雖然我同意ggovan;參觀場所的「集合」是健壯而清晰的。 –

使用遞歸方法尋路算法可能相當棘手，因爲您總是需要某種全局信息來評估，所以兩條路徑中的哪條路徑更合適。雖然遵循單一路徑，但如果它是正確的，你永遠無法確定。即使你總是追隨最近的節點，它也不一定是正確的路徑。這被稱爲best-first search策略，雖然它不是最好的，但它可以工作，但是你必須確保嘗試其他路徑，因爲你不能通過簡單地始終堅持最靠近的節點來實現它。

如果你想做一個路徑尋找算法，你將需要跟蹤所有的節點，你已經詳盡地探索過，因此永遠不需要再次訪問。這可以通過將訪問節點列表存儲在某種結構中明確地完成，也可以通過更明智的方式來實現，並通過良好的策略設計來選擇要訪問的新節點。

換句話說，如果您跟蹤要訪問的節點以及到每個節點的距離（priority queue），並且始終確保訪問最近未訪問的節點，則永遠不會再訪問相同的節點節點，而不必明確強制執行，如A* algorithm或Dijkstra。

來源

2014-02-22 21:48:48 Warlord

感謝您花時間嘗試和幫助我！ – billabrian6

如何讓我的路徑尋找算法不會相反？

回答

相關問題