如何通过连接的航点列表找到最短的路线

本文关键字：列表 何通过 连接 | 更新日期: 2023-09-27 17:56:44

public class Waypoint
{
    System.Drawing.Point _loc = new System.Drawing.Point();
    public System.Drawing.Point Location { get { return _loc; } }
    List<Waypoint> _connections = new List<Waypoint>();
    public List<Waypoint> Connections { get { return _connections; } }
    public Waypoint() { }
    public Waypoint(int x, int y) { _loc = new System.Drawing.Point(x, y); }
}

。是我的航点类。
我需要找到从Waypoint A到Waypoint B的最短路.
航点是相互连接的。（例如：X.Connections包含Y因此Y.Connections包含X）
当我设计系统时，我想到了找到它们的方法......但它不起作用。

如何通过连接的航点列表找到最短的路线

你想要的是A*算法。

A* 是 Dijkstra 算法的扩展，但使用启发式算法来估计到最终目的地的剩余距离（就像广度优先搜索一样）。这是两全其美的。:)

Amit 的页面非常适合学习整个算法，但为了更流畅地介绍，请查看此链接。我花了一段时间才了解 A* 的工作原理，但在我看来，花在学习它上的时间真的很值得。

您正在描述最短路径问题。
维基百科有一个算法列表。

您可以通过从初始点到到达航点执行广度优先搜索来最简单地做到这一点。

相关文章：