维基百科A*寻路算法需要花费大量时间

Question

我已经在C#中成功实现了A*pathfinding,但它很慢,我不明白为什么.我甚至尝试不对openNodes列表进行排序,但它仍然是相同的.

地图是80x80,有10-11个节点.

我从维基百科那里拿了伪代码

这是我的实施:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

这是我正在使用的启发式:

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

我究竟做错了什么？这是一整天我一直在看同样的代码.

Answer 1

首先,使用分析器.使用工具告诉你什么是缓慢的; 什么是慢的往往令人惊讶.并使用调试器.制作一个包含五个节点的地图,并在尝试查找路径时逐步执行代码的每一行.什么意外发生了？如果是这样,请弄清楚发生了什么.

其次,抛开你的性能问题,我认为你也有正确性问题.你能解释一下为什么你认为曼哈顿距离是一个合理的启发式算法吗？

(对于那些不熟悉度量标准的人来说,"曼哈顿距离"或"出租车距离"是指如果你住在一个网格上的城市,你必须经过的两点之间的距离.在东北方向14英里处,您必须向北行驶10英里,然后向东行驶10英里,总共行驶20英里.)

A*算法要求其正确性,启发式总是低估了在两点之间行进所需的实际距离.如果有图中的任何"对角线快捷方式",然后街道曼哈顿距离高估对这些通路的距离,因此该算法并不一定能找到最短路径.

为什么你不使用欧氏距离作为你的启发式？

您是否尝试使用"始终为零"作为启发式算法？这保证是低估的.(这样做可以实现Dijkstra的算法.)

第三,你似乎在这个实现中进行了大量的排序.当然你可能正在使用优先级队列; 这比分拣便宜很多.

第四,我在我的博客上实现了C#3中的A*,欢迎您使用; 没有明示或暗示的保证,使用风险自负.

http://blogs.msdn.com/b/ericlippert/archive/tags/astar/

我的代码很简单; 我的实现中的算法如下所示:

var closed = new HashSet<Node>();
var queue = new PriorityQueue<double, Path<Node>>();
queue.Enqueue(0, new Path<Node>(start));
while (!queue.IsEmpty)
{
    var path = queue.Dequeue();
    if (closed.Contains(path.LastStep)) continue;
    if (path.LastStep.Equals(destination)) return path;
    closed.Add(path.LastStep);
    foreach(Node n in path.LastStep.Neighbours)
    {
        double d = distance(path.LastStep, n);
        var newPath = path.AddStep(n, d);
        queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
    }
}

我们的想法是保持路径的优先级队列 ; 也就是说,路径队列始终能够以最小距离告诉您到目前为止的路径.然后我们检查一下我们是否已经到达目的地; 如果是这样,我们就完成了.如果没有,那么我们根据他们(低于)到目标的估计距离排队一堆新路径.

第五,维基百科中的伪代码可以得到改进.事实上,我的实际代码在很多方面比伪代码更容易遵循,这表明伪代码中可能存在太多细节.

Answer 2

几个笔记:

List<T>未针对删除第一个元素进行优化.更好的是以相反的顺序排序并采取最后一个元素.或使用Stack<T>或Queue<T>.

List.Remove(current)是非常低效的.您已经知道要删除的索引,不要在整个列表中搜索该元素.

openNodes通过在正确的位置插入新节点来保持排序应该比连续使用整个列表快得多.跳过列表排序会通过删除重要的不变量来破坏整个算法.您需要更快地排序,而不是跳过它.

你正在进行的主要操作closedNodes是存在测试closedNodes.Contains().使用针对该优化的数据结构,例如Set<T>.或者更好的是,在每个节点中放置一个封闭的标志字段,并在每次传递开始时将它们全部清除.这比closedNodes在每次迭代中进行线性搜索要快得多.

你不应该在solutionNodes最初放置任何东西,mEnd并且mStart将在遍历路径的最终循环期间添加.

neighborNodes可能是一个IEnumerable<T>而不是一个List<T>,因为你从来不需要整个列表.使用foreach也比按索引枚举列表稍快一些.