Wikipedia A * алгоритм поиска пути занимает много времени

Question

Я успешно внедрил A * pathfinding в C #, но он очень медленный, и я не понимаю, почему. Я даже пытался не сортировать список 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 * для своей корректности требует, чтобы эвристика всегда недооценивала фактическое расстояние, необходимое для перемещения между двумя точками. Если на графике есть какие-либо "диагональные" улицы, то манхэттенское расстояние переоценивает расстояние по этим путям, и поэтому алгоритм не обязательно найдет кратчайший путь .

Почему вы не используете евклидово расстояние в качестве эвристики?

Вы пробовали свой алгоритм, используя "всегда ноль" в качестве эвристики? Это гарантированно будет недооценивать. (Это дает вам реализацию алгоритма Дейкстры.)

В-третьих, вы, кажется, делаете очень много сортировки в этой реализации. Конечно, вы можете использовать приоритетную очередь; это намного дешевле, чем сортировка.

В-четвертых, у меня есть реализация A * в C # 3 в моем блоге, которую вы можете использовать; нет явных или подразумеваемых гарантий, используйте на свой страх и риск.

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 также будет немного быстрее, чем перечисление списка по индексу.

Answer 3

Вы можете сравнить его (или просто использовать) реализацию A * в библиотеке быстрых графов :

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

Answer 4

Используете ли вы сетку для представления местности?Если это так, то лучшей эвристикой в ​​этом случае является Octile:

Эвристическая стоимость = (мин (Разница по x, Разница по y) * квадратный корень из 2 + max (Разница по x, Разница по y) -min (разница по x, разница по y))

Для сеток это всегда будет оптимальным.К сожалению, эта эвристика не так хорошо известна.

Еще один полезный совет - выбрать структуру данных для вашего открытого списка, соответствующую размеру вашей карты.Если ваша карта относительно мала (100 x 100), то самый быстрый способ - несортированный вектор.Чтобы удалить элементы, просто поменяйте местами последний элемент и тот, который вы хотите удалить, и вызовите pop_back.Если у вас есть карта большего размера, используйте кучу.Вы заботитесь только о самом дешевом узле, поэтому сортировка всего остального не принесет пользы.Куча вставляет и сортирует со сложностью log n, идеально подходит для средних и больших наборов данных, но медленно для маленьких.

И наконец, если скорость так велика, внедрите Search Point Search.Это в среднем в 20-30 раз быстрее, чем поиск пути A *, без лишних затрат памяти (или, как утверждается в исследовательской работе, никаких доказательств этого не найдено).Он в основном заменит шаг «найти соседей» A * на «найти преемников», поэтому его включение в ваш код должно быть относительно простым.

Надеюсь, это поможет.

Answer 5

Вы вычисляете стоимость узла обхода следующим образом:

cost = current.G + 10;

Но для эвристики у вас есть простое расстояние.Почему бы не использовать одинаковое расстояние даже здесь?В зависимости от того, как далеко сейчас находятся ваши узлы, ваша эвристика может быть слишком низкой.

Еще одна «деталь», которая может быть неправильной: current.GetNeighborNodes.Как это реализовано?Возвращает ли он один и тот же узел, как и должен для одного и того же местоположения, так что один и тот же узел на разных путях является общим, или он всегда выделяет новый узел, используя новый?

Answer 6

На что похоже потребление памяти? Загрузите инструменты Red Gate. Используйте Performance Profiler, чтобы узнать, на что тратится больше всего времени, и Memory Profiler, чтобы определить, есть ли у вас какие-либо проблемы с утечками памяти или с недостаточно быстрым удалением объекта.

Как указал @Rodrigo, вы можете иметь большую карту для работы. Вложенные циклы никогда не будут эффективными.