在三角测量环境中改进搜索寻找路径

Question

我有一个由受约束的delaunay三角剖分表示的区域.我正在解决两点之间寻找路径的问题.我使用Marcelo Kallmann提供的论文作为解决这个问题的参考点.然而,我没有使用Kallmann 纸质链接提出的Chazelle漏斗算法,而是计划使用A*搜索算法,该算法可以非常有效地规划网格环境中的路径.

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

以下是来自Kallmann的图,演示了使用边缘技术的中点来生成包含目标节点的三角形的各种路径.

现在,当一个区域的三角形密度不够大时,这种技术可以正常工作.但是,如果生成的一组点的三角测量看起来像这样

我想知道是否有办法通过使用IDA*或ID-DFS等其他技术来提高算法的效率？已经提出了三角测量减少A*(TRA*),但由于它过于正式定义,我无法理解.TRA*方法的细节可以在Demyen的论文的第5部分中找到.

我会很感激一些想法.如果需要共享某些代码,我将编辑此帖子.

Answer 1

请注意，ID 算法通过重复工作来权衡 A* 产生的簿记成本，因此可能会使它们变慢（但希望不会慢很多）。因此，您尝试提高效率的措施将影响这些措施的有用程度。