Понимание эвристики A* для лабиринта с одной целью

У меня есть лабиринт, подобный следующему:

||||||||||||||||||||||||||||||||||||
|                                 P|
| ||||||||||||||||||||||| |||||||| |
| ||   |   |      |||||||   ||     |
| || | | | | |||| ||||||||| || |||||
| || | | | |             || ||     |
| || | | | | | ||||  |||    |||||| |
| |  | | |   |    || ||||||||      |
| || | | |||||||| ||        || |||||
| || |   ||       ||||||||| ||     |
|    |||||| |||||||      || |||||| |
||||||      |       |||| || |      |
|      |||||| ||||| |    || || |||||
| ||||||      |       ||||| ||     |
|        |||||| ||||||||||| ||  || |
||||||||||                  |||||| |
|+         ||||||||||||||||        |
||||||||||||||||||||||||||||||||||||

Цель состоит в том, чтобы P найти +, с подцелями

  • Путь к + является наименее затратным (1 прыжок = стоимость+1)
  • Количество искомых ячеек (развернутых узлов) сведено к минимуму.

Я пытаюсь понять, почему моя эвристика A* работает намного хуже, чем моя реализация для Greedy Best First. Вот два бита кода для каждого:

#Greedy Best First -- Manhattan Distance
self.heuristic = abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0])

#A* -- Manhattan Distance + Path Cost from 'startNode' to 'currentNode'
return abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0]) + self.costFromStart

В обоих алгоритмах я использую heapq, расставляя приоритеты на основе эвристического значения. Первичный цикл поиска одинаков для обоих:

theFrontier = []
heapq.heappush(theFrontier, (stateNode.heuristic, stateNode)) #populate frontier with 'start copy' as only available Node

#while !goal and frontier !empty
while not GOAL_STATE and theFrontier:
    stateNode = heapq.heappop(theFrontier)[1] #heappop returns tuple of (weighted-idx, data)
    CHECKED_NODES.append(stateNode.xy)
    while stateNode.moves and not GOAL_STATE:
        EXPANDED_NODES += 1
        moveDirection = heapq.heappop(stateNode.moves)[1]

        nextNode = Node()
        nextNode.setParent(stateNode)
        #this makes a call to setHeuristic
        nextNode.setLocation((stateNode.xy[0] + moveDirection[0], stateNode.xy[1] + moveDirection[1]))
        if nextNode.xy not in CHECKED_NODES and not isInFrontier(nextNode):
            if nextNode.checkGoal(): break
            nextNode.populateMoves()
            heapq.heappush(theFrontier, (nextNode.heuristic,nextNode))

Итак, теперь мы подошли к вопросу. Хотя A* находит оптимальный путь, это довольно затратно. Чтобы найти оптимальный путь cost:68, он расширяет (перемещает и ищет) 452 узла. a_star

В то время как моя реализация Greedy Best находит неоптимальный путь (стоимость: 74) всего за 160 расширений.

greedy_best_first

Я действительно пытаюсь понять, где я ошибаюсь. Я понимаю, что алгоритмы Greedy Best First могут вести себя так естественным образом, но разрыв в раскрытии узлов настолько велик, что я чувствую, что здесь что-то должно быть неправильным... любая помощь будет оценена по достоинству. Я рад добавить детали, если то, что я вставил выше, каким-то образом неясно.


python artificial-intelligence path-finding a-star heuristics
person MrDuk    schedule 23.02.2015    source источник
comment
Не обращайте внимания на мои предыдущие комментарии. Это совершенно нормальное поведение. Я сначала подумал, что + это начало. Найти оптимальные решения подобных проблем сложно; вот почему мы часто не беспокоимся.   -  person user2357112 supports Monica    schedule 23.02.2015
comment
Я обнаружил одну вещь, которая на самом деле не устраняла разницу между ними, но в целом повышала эффективность, заключалась в добавлении следующего в конец основного цикла: CHECKED_NODES.append(nextNode.xy) - это, похоже, сократило мое расширение вдвое для обоих алгоритмов. ..   -  person MrDuk    schedule 23.02.2015

Ответы (3)


arrow_upward
4
arrow_downward

A* дает оптимальный ответ на задачу, жадный поиск по первому наилучшему дает любое решение.

Ожидается, что A* должен выполнить больше работы.

Если вам нужен вариант A*, который больше не является оптимальным, но возвращает решение намного быстрее, вы можете посмотреть на взвешенный A*. Он просто состоит в том, чтобы присвоить эвристике вес (вес > 1). На практике это дает вам огромный прирост производительности

Например, не могли бы вы попробовать это:

return 2*(abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0])) + self.costFromStart
person B. Decoster    schedule 23.02.2015

arrow_upward
2
arrow_downward

Поиск A* пытается найти наилучшее возможное решение проблемы, в то время как жадный поиск наилучший просто пытается найти какое-либо решение вообще. A* имеет гораздо более сложную задачу, и он должен приложить много усилий для изучения каждого пути, который может быть лучшим, в то время как жадный алгоритм поиска лучшего первым просто выбирает вариант, который выглядит наиболее близким к цели. .

person user2357112 supports Monica    schedule 23.02.2015

arrow_upward
1
arrow_downward

Поскольку это не было решено, и хотя что-то не так, заданное OP, можно решить с помощью Fezvez answer, я чувствую, что мне нужно спросить об этом и, возможно, ответить на то, что не так, и почему ответ Февеза может позаботиться об этом: вы проверили эвристическое значение всех ваших узлов с помощью алгоритма A * и заметили что-то странное? Разве они не все равны? Потому что, хотя ваша эвристика верна для алгоритма поиска лучшего первого, она не подходит напрямую для вашего алгоритма A*. Я сделал проект, похожий на java, и у меня была эта проблема, поэтому я спрашиваю здесь. Например, предположим, что у вас есть следующие достопримечательности:

  • Старт(П) - (0,0)
  • Конец(+) - (20,20)
  • P1 - (2,2) -> (Ваша эвристика) + (стоимость пути) = ((20-2) + (20-2)) + ((2-0) + (2-0)) = 40
  • P2 - (4,3) -> (Ваша эвристика) + (стоимость пути) = ((20-4) + (20-3)) + ((4-0) + (3-0)) = 40

И, если я не ошибаюсь, это будет справедливо для всех ваших точек в лабиринте. Теперь, учитывая, что алгоритм A* обычно реализуется точно так же, как алгоритм поиска в ширину с эвристикой (и стоимостью пути), поскольку ваша эвристика всегда дает вам одну и ту же сумму (F = h+g), она на самом деле становится алгоритмом в ширину, который также дает вам наилучшее возможное решение, но на практике всегда медленнее, чем обычно делает A *. Теперь, как предположил Фезвес, придание веса вашей эвристике может просто смешать лучшее из обоих миров (сначала лучший и первый в ширину) и будет выглядеть так с приведенными выше точками:

  • Старт(П) - (0,0)
  • Конец(+) - (20,20)
  • P1 - (2,2) -> 2*(Ваша эвристика) + (стоимость пути) = 2*((20-2) + (20-2)) + ((2-0) + (2-0)) = 76
  • P2 - (4,3) -> 2*(Ваша эвристика) + (стоимость пути) = 2*((20-4) + (20-3)) + ((4-0) + (3-0)) = 73
person pandaman1234    schedule 15.03.2016