最低成本路徑

Question

我有一個景觀與幾個棲息地（即具有不同ID的多邊形）。棲息地的每個多邊形都由多個補丁組成。另外，棲息地的每個多邊形都有相關的成本。我希望獲得包含烏龜的多邊形與包含烏龜的多邊形周圍2公里的所有多邊形之間的最小成本路徑。

在第一次，我想使用NW加長的「weighted-distance-to」。根據與此基元關聯的示例，我應該在包含烏龜的多邊形和所有在2 km緩衝區中的多邊形之間創建一個鏈接，然後我應該爲該鏈接分配一個權重值。在這個例子中，兩隻烏龜之間的每個鏈接都被分配給一個由用戶定義的權重值。在我的情況下，由於鏈接跨越不同的棲息地，是否有可能計算一個權重值等於朝向2 km緩衝區中的多邊形之一的路徑的累積成本？

非常感謝您的幫助。

Answer 1

聽起來像你可以創建一個Dijkstra的最短路徑算法的酷變種。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

如果你保持在一個TreeSet所有生成的路徑上排序長度，你拉電流最短路徑，與沒有被訪問尚未所有可能的多邊形擴展它，並在TreeSet中推動這些解決方案。如果從多邊形開始，只能以比迄今爲止發現的最短路線更高或相同的成本移動到周圍的多邊形，則可以放棄該路線。這樣，你只擴展最短的路線，生成廣度最先搜尋最近的龜，同時截斷永遠不會工作的可能性。

好運！