QuickGraph - 我如何讓A *跳過特定的邊緣？

我進行路徑查找庫。 QuickGraph，開放圖庫，符合我的所有要求，但我遇到了一個問題。我需要最短路徑算法來跳過當前移動代理無法訪問的邊。我想是這樣的：QuickGraph - 我如何讓A *跳過特定的邊緣？

Func<SEquatableEdge<VectorD3>, double> cityDistances = delegate(SEquatableEdge<VectorD3> edge) 
{ 

    if(edge.IsPassableBy(agent)) 
     return edgeWeight; // Edge is passable, return its weight 
    else 
     return -1; // Edge is impassable, return -1, which means, that path finder should skip it 

}; 

Func<VectorD3, double> heuristic = ...; 

TryFunc<VectorD3, IEnumerable<SEquatableEdge<VectorD3>>> tryGetPath = graph2.ShortestPathsAStar(cityDistances, heuristic, sourceCity);

我能想象通過創建圖表的副本，並刪除不可逾越的邊緣解決這個問題，但它是電腦的不必要的資源浪費。請問，請告訴我如何解決這個問題？或者有沒有解決辦法，我應該更新來源？

來源

2013-01-13 PanCotzky

快速黑客會讓不通的邊緣的重量大於真實最短路徑的總重量。 A *算法將始終將包含您的「不可通過」邊緣的路徑移動到優先級隊列的末尾，並找到真正的最短路徑。這種方法的缺點是*如果目標的每條路徑都會穿越一條「無法通行」的邊緣，那麼被破解的算法將選擇一條路徑，而不是做正確的事情並且失敗*。 –

@EricLippert圍繞該解決方法的解決方法可能是您要檢查結果路徑長度，並且如果它大於您的「不可通過的」邊緣權重，您會期望它找不到路徑。 – Luaan

如果你想指定一個自定義的方法距離檢索方法，是不是像'DelegateIncidenceGraph'這樣的東西是爲了做你需要的東西？ – Superbest

鑑於你的重量是double類型，你應該能夠使用double.PositiveInfinity來計算不可接受的邊的重量。

正如Eric Lippert所說，高重量的故障情況是一條完整的路徑，但是從double.PositiveInfinity的任何加法或減法應該仍然是無窮大。 double類型有一個IsPositiveInfinity方法來測試。

因此，嘗試將無法通過的重量設置爲無窮大並測試最終路徑長度。

來源

2014-03-20 19:52:02

QuickGraph - 我如何讓A *跳過特定的邊緣？

回答

相關問題