3

我已经在 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);
    }

我究竟做错了什么？我整天都在看相同的代码。

4

6 回答 6

16

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

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

（对于那些不熟悉该指标的读者来说，“曼哈顿距离”或“出租车距离”是指如果您居住在网格上的城市中，您必须经过两点之间的距离。也就是说，要向东北方向行驶 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);
    }
}

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

第五，维基百科中的伪代码可以改进。事实上，我的实际代码在很多方面都比伪代码更容易理解，这表明伪代码中可能有太多细节。

于 2011-02-01T17:26:55.470 回答
5

几点注意事项：

List<T>没有针对删除第一个元素进行优化。最好以相反的顺序排序并取最后一个元素。或使用Stack<T>or Queue<T>。

List.Remove(current)效率极低。您已经知道要删除的索引，不要在整个列表中搜索该元素。

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

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

solutionNodes您最初不应该放入任何东西，mEnd两者mStart都会在遍历路径的最终循环中添加。

neighborNodes可以是 aIEnumerable<T>而不是 a List<T>，因为您从不需要一次整个列表。使用foreach也比按索引枚举列表要快一些。

于 2011-02-01T16:22:05.800 回答
1

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

QuickGraph.Algorithms.ShortestPath.AStarShortestPathAlgorithm<TVertex,TEdge>
于 2011-02-01T16:20:49.880 回答
0

内存消耗是怎样的？下载红门工具。使用 Performance Profiler 查看花费最多的时间，并使用 Memory Profiler 确定您是否有任何内存泄漏问题或对象没有足够快地处理。

正如@Rodrigo 指出的那样，您可以处理一张大地图。嵌套循环永远不会被期望是高性能的。

于 2011-02-01T16:15:54.987 回答
0

您可以像这样计算遍历节点成本：

cost = current.G + 10;

然而，对于启发式方法，您有一个简单的距离。为什么即使在这里也不使用相同的距离？根据您的节点当前的距离，您的启发式方法可能太低了。

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

于 2011-02-01T16:37:18.940 回答
-1

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

启发式成本 = (min(x 中的差异，y 中的差异) * 2 的平方根 + max(x 中的差异，y 中的差异) - min(x 中的差异，y 中的差异))

对于网格，这将始终是最佳的。不幸的是，这种启发式方法并不为人所知。

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

最后，如果速度是一个非常重要的问题，请实施 Jump Point Search。平均而言，它比寻路 A* 快 20 到 30 倍，而且没有内存开销（或者研究论文声称，没有找到任何关于这一点的证据）。它基本上将 A* 的“查找邻居”步骤替换为“查找继任者”，因此将其合并到您的代码中应该相对简单。

希望有帮助。

于 2013-06-25T19:43:07.897 回答