algorithm - 改进 a* 搜索以在三角环境中寻找路径

Question

我有一个区域，它由受约束的 delaunay 三角剖分表示。我正在解决在两点之间寻找路径的问题。我正在使用 Marcelo Kallmann 提供的论文作为解决此问题的引用点。然而，而不是使用 Kallmann 提出的 Chazelle 漏斗算法 paper link ，我打算使用 A* 搜索算法，该算法非常有效地规划网格环境中的路径。

对于启发式成本函数，我使用从当前节点到目标节点的欧几里德距离，为了选择邻居节点，我从当前点 p 到边缘的中点绘制一条线段三角形。 [这个想法是由kallmann提出的]邻居节点的成本也由它们之间的欧氏距离给出。

这是 Kallmann 的图，演示了使用边的中点技术生成通往包含目标节点的三角形的各种路径。

现在，当某个区域的三角形密度不够大时，此技术可以正常工作。但是假设为一组点生成的三角剖分看起来像这样

我想知道是否有一种方法可以通过使用 IDA* 或 ID-DFS 等其他技术来提高算法的效率？已经提出了 Triangulation Reduction A* (TRA*)，但我无法理解它，因为它定义得太正式了。 TRA* 方法的详细信息可以在本 thesis 的第 5 节中找到德米恩。

我将不胜感激。如果需要共享某些代码，我将编辑这篇文章。

Answer 1

请注意，ID 算法通过重复工作来抵消 A* 产生的簿记成本，因此可能使它们变慢(但希望不会慢很多)。因此，您尝试提高效率的措施将影响这些工具的实用性。