我必须编写一个模拟代码,我需要一种方法来找到从一个位置到另一个位置的最短路径.该方法仅获得起始位置和最终位置,并返回表示位置之间最短道路的位置列表.像这样的东西:
public List<Tuple<int, int> ShortestRoad(Tuple<int,int> start, Tuple<int,int> end, int[,] park)
{//Code}
如何为此方法执行Dijkstra算法实现？
您应该查找A*搜索算法,这是一种广泛的首次搜索算法,具有启发式算法,可以使其更快.
基本上A*算法是像Dijkstra算法那样广泛的第一次搜索,但是它使用启发式算法,或者猜测最短路径是什么(一个提示,你可以说,告诉A*算法哪个节点更好看).使用启发式算法可以使A*算法比Dijkstra算法快得多,因为它通常不会像Dijkstra算法那样关注那么多节点.
但是,需要注意的一点是,您的启发式函数(两个节点之间的成本/距离的猜测)绝不能小于给定节点之间的实际成本.如果您的启发式函数产生较小的结果,则A*算法不一定会找到最佳/最短/最便宜的路径.
现在,如果你想要一些不错的动画(特别是关于A*和Dijkstra算法之间的差异),那么在维基百科上搜索,两个动画之间在同一环境中执行相应算法的动画.从他们那里可以很容易地看出A*算法更好.