维基百科的A*寻路算法需要很长时间。

Question

我已经成功地在C#中实现了A*路径查找，但速度很慢，我不知道为什么。我甚至尝试过不对openNodes列表进行排序，但结果还是一样的。

这张地图大小为80x80，有10-11个节点。

我从这里Wikipedia取得了伪代码。

以下是我的实现：

 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);
    }

我到底做错了什么？整整一天了，我都在看同样的代码。

- Vittorio Romeo

---

你的地图大小是多少？扩展次数取决于到目标节点的距离，而这又取决于地图的大小。 - Please treat your mods well.

你的列表中有多少个节点？“慢”到底是指做某事需要多长时间？ - Suma

有11个房间和10个总路径连接。Pathfind方法需要大约8-10秒钟。 - Vittorio Romeo

11个节点需要10秒钟？即使您的启发式算法很差，这绝对太多了。最坏情况下，您应该在几毫秒内彻底检查所有节点。在这种情况下，我真的建议使用“穷人的分析器”，该分析器在https://dev59.com/onVC5IYBdhLWcg3whRgw中有描述。 - Suma

请纠正我，如果我错了，但是您有if (current == mEnd) { while (current != null) { solutionNodes.Add(current); current = current.Parent; } return solutionNodes; } mEnd和mStart不已经在solutionNodes列表中吗？ 您的逻辑不会再次添加它们吗？ - Dave

@Ben Voigt在他的回答中解决了我的问题。 - Dave

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);
    }
}

我们的想法是维护一条路径的优先级队列;也就是说，这是一个总是能告诉你到目前为止距离最短的路径的队列。然后我们检查是否已经到达了目的地;如果是，则完成了。如果没有，那么我们根据它们（低估的）到目标的距离排队了一堆新路径。

第五个，维基百科中的伪代码可以改进。事实上，我的实际代码在许多方面比伪代码更易于理解，这可能意味着伪代码中有太多的细节。

- Eric Lippert

---

你能向我们解释一下为什么你认为曼哈顿距离是一个合理的启发式吗？由于他不会对角线移动（扩展四个邻居，参见https://dev59.com/sVPTa4cB1Zd3GeqPnuwd#4865257的评论），因此曼哈顿距离是正确的。 - Suma

距离使用什么，估计使用什么？它们都使用欧几里得吗？ - Vittorio Romeo

@Vee：“distance”是任何接受两个节点并计算它们之间精确距离的函数；“estimate”是一个接受一个节点并估计从该节点到目标节点的距离的函数。只要这些方法正确且高效地完成它们的工作，它们如何完成工作与A的实现无关。如果有意义的话，它们可能是欧几里得距离。请记住，A可以用于在任意图中查找路径；它不一定是真实世界的地图。欧几里得度量仅在坐标系中有意义。 - Eric Lippert

如果允许对角线移动并且其代价与网格移动相同，则欧几里得距离（2-范数）不是正确的度量标准。无穷范数（max(abs(x1-x2),abs(y1-y2))）才是正确的度量标准。当不允许对角线移动时，曼哈顿距离（1-范数，abs(x1-x2)+abs(y1-y2)）是正确的。 - Ben Voigt

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也比按索引枚举列表稍快。

- Ben Voigt

Answer 3

你可以将其与quickgraph库中的A*实现进行比较（或直接使用）：

QuickGraph.Algorithms.ShortestPath.AStarShortestPathAlgorithm<TVertex,TEdge>

- digEmAll

---

我没有找到任何关于如何使用它的文档。TVertex 应该是我的 PGNode，对吗？TEdge 呢？ - Vittorio Romeo

@Vee：你应该将你的地图转换成一个图形（基本上每个瓦片（节点）通过一条边连接到可访问的邻居，例如 new Edge<int>(source,target)）。 - digEmAll

Answer 4

内存消耗如何？下载Red Gate工具。使用性能分析器查看最耗时的地方，使用内存分析器确定是否存在内存泄漏或对象无法快速释放的问题。

正如@Rodrigo所指出的，您可能需要处理一个大型映射。嵌套循环通常不会有良好的性能表现。

- Dustin Davis

Answer 5

你可以这样计算遍历节点的成本：

cost = current.G + 10;

对于启发式算法，您有一个简单的距离。为什么不在这里也使用相同的距离？根据您的节点当前的距离有多远，您的启发式算法可能会低很多。

另一个可能出错的“细节”： current.GetNeighborNodes。它是如何实现的？它是否返回应该返回的相同位置的相同节点，以便在不同路径上使用相同的节点，还是总是使用 new 分配新节点？

- Suma

---

current.GetNeighborNodes返回4个相邻的已存在节点。一个80x80的节点数组与地图一起创建。 - Vittorio Romeo

好的。那么启发式算法呢？如果节点之间的距离为1，成本为10，则启发式应该是距离*10，而不是距离。如果低估了启发式，您的搜索将接近Djisktra算法。 - Suma

Answer 6

你在使用网格来表示地形吗？如果是这样，那么在这种情况下最好的启发式方法是八叉树：

启发式成本=（x轴差异，y轴差异中的最小值* 2的平方根+ x轴差异，y轴差异中的最大值- x轴差异，y轴差异中的最小值）

对于网格，这将始终是最优的。不幸的是，这个启发式方法并不是很出名。

另一个有用的提示是选择适合地图大小的开放列表数据结构。如果您的地图相对较小（100 x 100），则未排序的向量将是最快的方法。要删除元素，只需进行迭代器交换最后一个元素和要删除的元素，并调用pop_back。如果您有更大的地图，请使用堆。您只关心最便宜的节点，因此对其他所有内容进行排序将没有任何好处。堆插入和排序的复杂度为log n，非常适合中型和大型数据集，但对于小型数据集而言速度较慢。

最后，如果速度是一个很大的问题，可以实现跳点搜索（Jump Point Search）。据研究论文称，它平均比路径查找A*快20到30倍，而且没有内存开销（虽然我还没有找到任何证据来证明这一点）。它基本上将A*的“查找邻居”步骤替换为“查找继承者”，因此将其纳入您的代码中应该相对简单。

希望这有所帮助。

- Bruno Ayllon