A* поиск пути с приоритетом узлов

Я пытаюсь найти кратчайший путь в лабиринте с определенными начальными и конечными точками, лабиринт построен как 2D-таблица (строки и столбцы), когда в некоторых ячейках таблицы вы не можете пройти («стены» ), пока все хорошо, и алгоритм A* работает нормально, проблема начинается, когда определенные ячейки имеют лучший "вес", чем другие... например, возьмем лабиринт 3*3:

  • отправная точка 1*1
  • конечная точка 3*3
  • ячейка 1*3 имеет лучший вес по сравнению с другими, а это значит, что если в итоге у вас будут равные маршруты, вам лучше пройти через эту ячейку

так что по A * он даже не заставит ячейку 1 * 3 понять, что у нее лучший вес!

есть ли решение этой проблемы?

Благодарность!


c algorithm path-finding maze pacman
person user2144097    schedule 16.02.2014    source источник
comment
^ это должен был быть мой ответ   -  person washcloth    schedule 16.02.2014
comment
@HenkHolterman, user2144097 - Алгоритм Дейкстры в основном представляет собой A * с h (v) = 0. Итак, если у вас есть хорошая эвристическая функция - Дейкстра уступает A *.   -  person amit    schedule 16.02.2014
comment
@ user2144097 - вы можете спросить нас, но почему бы не спросить Google или Википедию?   -  person Henk Holterman    schedule 16.02.2014
comment
@HenkHolterman Я не согласен с вашим последним комментарием. Это не классика, как решить вопрос лабиринта. У ОП уже есть решатель лабиринта, и он хочет знать, как добавить новый аспект «важных узлов», который должен быть одобрен алгоритмом, если это возможно. Требуется большой опыт в этой области, чтобы придумать правильные ключевые слова для этого запроса, IMO.   -  person amit    schedule 16.02.2014

Ответы (1)


arrow_upward
4
arrow_downward

Создайте график, представляющий ваш лабиринт G=(V,E).

Создайте новый взвешенный граф с функцией веса для ребер в графе:

w(u,v) = 1                if v is "not important"
         1-1/(n+1)        if v is important.
(n is the total number of vertices/cells in your maze).

Теперь обратите внимание, что путь, который проходит через v, «лучше» (короче), чем путь, который не проходит через него, но все же более короткие (по расстоянию) пути всегда предпочтительнее.

Теперь вы можете использовать A* с модифицированной эвристической функцией:

h'(v) = h(v)*[1-1/(n+1)]  [where h(v) is the original admissible heuristic you had]

Примечание: не обращайте внимания на комментарии. Алгоритм Дейсктры уступает A*, если у вас есть допустимая эвристическая функция, и похоже, что она у вас есть.

person amit    schedule 16.02.2014