Оптимизация алгоритма A-Star

Question

Я реализовал алгоритм A * Согласно реализации Википедии на здесь Тем не менее, он слишком медленный для запуска на мобильных устройствах. Я должен ждать бесконечные часы, чтобы завершить функцию, хотя она отлично работает на настольном компьютере. Что я могу сделать, чтобы оптимизировать алгоритм?

Вот фактический код

public DriveRoute findroute(routenode from, routenode to)
        {
            Dictionary<int, routenode> openlist = new Dictionary<int, routenode>();
            openlist.Add(from.nodeid, from);
            Dictionary<int, routenode> closedlist = new Dictionary<int, routenode>();
            Dictionary<int, double> gscores = new Dictionary<int, double>();
            gscores.Add(from.nodeid, 0);
            Dictionary<int, double> hscores = new Dictionary<int, double>();
            hscores.Add(from.nodeid, distanceForRouting(from.latlon, to.latlon));
            Dictionary<int, double> fscores = new Dictionary<int, double>();
            fscores.Add(from.nodeid, gscores[from.nodeid] + hscores[from.nodeid]);
            Dictionary<int, routenode> came_from = new Dictionary<int, routenode>();
            while (openlist.Values.Count > 0)
            {
                routenode x = getLowestFscore(openlist, fscores);
                if (x.latlon.Equals(to.latlon))
                {
                    return rebuildPathWay(came_from, to);
                }
                openlist.Remove(x.nodeid);
                closedlist.Add(x.nodeid, x);
                foreach (routearc arc in x.outgoingarcs)
                {
                    if (closedlist.Keys.Contains(arc.endnode))
                        continue;
                    double tentative_g_score = gscores[x.nodeid] + arc.time;
                    bool tentative_is_better = false;
                    if (!openlist.Keys.Contains(arc.endnode))
                    {
                        openlist.Add(arc.endnode, map.routenodes[arc.endnode]);
                        tentative_is_better = true;
                    }
                    else if (tentative_g_score < gscores[arc.endnode])
                    {
                        tentative_is_better = true;
                    }
                    if (tentative_is_better)
                    {
                        if (came_from.ContainsKey(arc.endnode))
                            came_from[arc.endnode] = x;
                        else
                            came_from.Add(arc.endnode, x);
                        gscores[arc.endnode] = tentative_g_score;
                        hscores[arc.endnode] = distanceForRouting(arc.endlatlon, to.latlon);
                        fscores[arc.endnode] = gscores[arc.endnode] + hscores[arc.endnode];
                    }
                }
            }
            return null;
        }

Answer 1

Трудно дать какие-либо подсказки, не видя весь код, но я могу дать некоторые подсказки:

Основное действие, которое вы выполняете над словарем, - это найти что-то с наименьшей стоимостью. Структура данных за словарем должна быть оптимизирована для этой операции. Классической структурой данных была бы куча (не вещь, связанная с new / delete malloc / free, а структура данных: http://en.wikipedia.org/wiki/Heap_%28data_structure%29)

Вы найдете подтипы этой структуры данных, такие как fibonacci-heaps и так далее. Стоит дать им попробовать. Не реализовав A *, я бы также попробовал splay-tree (поиск по вики даст вам хиты).

Второе: вы вставляете и удаляете узлы во время выполнения алгоритма? Если это так, убедитесь, что вы создали себе пул предварительно выделенных узлов и используете его вместо вызова new / delete или malloc / free. Выделение памяти может быть очень медленным.

Answer 2

Вы должны кэшировать свои оценки для каждого узла в очереди с приоритетами. Таким образом, вам просто нужно выталкивать первый узел из очереди приоритетов каждый раз, когда вам нужен новый узел, вместо того, чтобы вызывать getLowestFscore. При реализации PriorityQueue просто используйте SortedDictionary<int, List<routenode>>. Используйте SetDefault (см. здесь для примера), чтобы облегчить вашу жизнь.

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

Answer 3

Можете ли вы распараллелить цикл for? Вы работаете с конкретным мобильным устройством, которое имеет несколько ядер? Если это так, посмотрите Tasks.Parallel.For (....) или Foreach.

Кроме того, рассмотрите возможность кэширования любой информации, которую сможете.

По какой причине вы используете A * вместо алгоритма Джикстры?

Answer 4

Большая часть оптимизации A * идет на реализацию открытых и закрытых списков.В частности, используются следующие четыре метода: добавление, удаление, получение наименее значимого элемента и поиск записи, относящейся к конкретному узлу.Лично я обнаружил, что использование Complete Binary Heap для структурирования открытого списка значительно увеличит скорость моего кода A *, который был создан в Python.Надеюсь, это поможет!

Answer 5

A * - хороший эвристический алгоритм, но вам, вероятно, тоже нужна оптимизация.

Оптимизация, которую я бы сделал, - это использование групп узлов вместо всех узлов, чтобы найти «лучший» путь. Скажем, у вас есть 1000 городов, почему бы не сгруппировать их и не найти лучший путь в более глобальном масштабе, а затем оптимизировать его.

Я только пытался реализовать обычную A *, но не с этой оптимизацией. Почему бы тебе не попробовать;)