改进A*搜索算法以在三角形环境中寻找路径

Question

5

我有一个由约束德劳内三角剖分表示的区域。我正在尝试解决在两个点之间寻找路径的问题。我使用Marcelo Kallmann提供的论文作为参考来解决这个问题。然而，我计划使用A*搜索算法代替Kallmann提出的Chazelle漏斗算法paper link，该算法可以在网格环境中高效地规划路径。

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

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

Visibility Graphs

现在这种技术在密集的三角形区域中不起作用。但是，如果一组点的生成三角剖分看起来像这样 500-pt triangulation

，那么是否有办法通过使用IDA*或ID-DFS等其他技术来提高算法效率？已经提出了一个三角剖分减少A*（TRA*）的方法，但由于过于正式定义，我无法理解它。TRA*方法的详细信息可以在Demyen的thesis第5节中找到。我希望能听取一些意见。如果需要共享某些代码，我会编辑此帖子。

- chaitanya

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Scott Hunter · Accepted Answer

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