这个路径规划算法叫什么名字？

Question

这些图片展示了一个节点图，排列方式类似像素网格，有直行和直列。每个节点（除了边缘的节点）都有8条边，指向周围最近的8个节点。右侧的图片展示了使用简单距离加欧几里得距离启发式搜索的A*算法。

现在，我认为右侧图片给出的路径不够好。相反，我想要一条连接起始节点和目标节点的最短路径。如何获取该路径的算法叫什么？

- Hosdgfag2

---

左边的图片显示了一条有效路径，而右边的图片则没有。这并不是关于特定算法的问题，而是关于改变您的环境表示方式（蓝点=墙壁，在节点之间移动没有限制）的问题。 - Dese

你的地图结构是什么样子的（是一个网格吗？），你如何行走（通过欧几里得距离传送到任何节点，只要你不穿过墙壁）？ - harold

Answer 1

使用二维网格离散化可找到基于欧几里得最短路径，这可以通过Theta*算法实现。

另一种（更常用的）方法是基于标准的4向或8向路径查找（左图），然后进行“拉弦”优化。最常用的算法是"Funnel algorithm"。

请注意，这些方法都不能保证产生全局最短路径。此外，这些假设您将世界表示为网格；如果您将其表示为一组凸多边形，则其他算法更合适。

- Sneftel

---

你提到了有一些_更适合处理凸多边形的其他字符串匹配算法_；您可以请列出它们的名称吗？这可能会很有用。 - legends2k

如果您的环境可以描述为多边形分解，则可以在多边形本身的面/边上执行A*，可以使用中点启发式或（如果您要求绝对最优性但代价是巨大的复杂性）Hershberger算法，该算法在“平面欧几里得最短路径的最优算法”中有所描述。 - Sneftel

Answer 2

这是一个有多边形障碍物的二维欧几里得最短路径问题。

若要使用算法求解，请参考以下两个参考文献：

• Hershberger, John; Suri, Subhash (1999), "An optimal algorithm for Euclidean shortest paths in the plane", SIAM Journal on Computing 28 (6): 2215–2256, doi:10.1137/S0097539795289604.

• Kapoor, S.; Maheshwari, S. N. (1988), "Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles", Proc. 4th ACM Symposium on Computational Geometry, pp. 172–182, doi:10.1145/73393.73411, ISBN 0-89791-270-5.

- user1196549