改善在三角環境中查找路徑的搜索

Question

我有一個由約束Delaunay三角剖分表示的區域。我正在玩弄兩點之間的路徑問題。我使用Marcelo Kallmann提供的論文作爲解決這個問題的參考點。然而，我沒有使用Kallmann paper link提出的Chazelle漏斗算法，而是計劃使用A *搜索算法，它非常有效地在網格環境中計劃路徑。

對於啓發式成本函數，我使用從當前節點到目標節點的歐幾里得距離，並選擇相鄰節點，我繪製從當前點p到邊緣中點的線段的三角形。 [這個想法是由卡爾曼提出的]鄰居節點的成本也由它們之間的歐幾里得距離給出。

下面是來自卡爾曼的圖，演示瞭如何使用邊緣技術的中點來生成包含目標節點的三角形的各種路徑。

現在，當三角形密度不是在一個區域足夠大，這種技術能正常工作。但是說，如果生成的一組點的三角形看起來像這樣

我想知道是否有一種方法可以通過使用其他技術（如IDA *或ID-DFS）來提高算法的效率？減少三角函數A *（TRA *）已經被提出，但由於其過於正式的定義，我無法理解它。 TRA *方法的細節可以在Demyen的thesis的第5部分中找到。

我希望對此有所瞭解。如果需要分享一些代碼，我將編輯這篇文章。

Answer 1

注意，ID算法通過重複工作，從而有可能使它們更慢（但是希望不是很慢）折衷由A *招致簿記成本。那麼你想要提高效率的措施會影響這些將會是多麼有用。