Отслеживание фрагментов в* поиске

Давайте запустим интерактивный интерпретатор и посмотрим, что мы можем найти. (Вы не указали название своего класса в вопросе, поэтому я назвал его Search.)

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: <__main__.Node instance at 0x104895518>

Хорошо, первая проблема заключается в том, что эти Node экземпляры не говорят сами за себя. Мы ничего не можем сделать с «Экземпляром узла по адресу 0x104895518», поэтому давайте добавим метод __repr__ в класс Node:

def __repr__(self):
    return 'Node({0.value}, {0.pos}, {0.cost})'.format(self)

и попробуй еще раз:

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: Node(East, (1, 2), 3.41421356237)

Хорошо, это более информативно. Давайте запустим отладчик Python и выполним вскрытие:

>>> import pdb
>>> pdb.pm()
> q19128695.py(25)aStar()
-> openSet.remove(curNode)
(Pdb) openSet
set([Node(North, (2, -1), 6.0), Node(East, (2, 2), 4.65028153987), 
     Node(West, (-1, 1), 5.0), Node(North, (0, -1), 5.0),
     Node(South, (1, 3), 6.65028153987), Node(South, (0, 3), 6.0), 
     Node(East, (3, 0), 6.0), Node(West, (-1, 0), 5.0),
     Node(North, (1, -1), 5.0), Node(East, (3, 1), 6.65028153987),
     Node(West, (-1, 2), 6.0)])
(Pdb) closedSet
set([Node(0, (0, 0), 4), Node(South, (2, 1), 3.41421356237),
     Node(East, (1, 1), 3.0), Node(South, (0, 1), 3.0),
     Node(East, (2, 0), 3.0), Node(East, (1, 0), 3.0),
     Node(East, (1, 2), 3.41421356237), Node(South, (0, 2), 3.0)])
(Pdb) curNode
Node(East, (1, 2), 3.41421356237)
(Pdb) curNode in closedSet
True

Итак, узел уже закрыт. Как это могло произойти? Ну, это могло случиться, если узел был добавлен к openSet и openHeap дважды. Затем он будет извлечен из openHeap дважды (поскольку в кучах может быть несколько одинаковых элементов), но его можно будет удалить из openSet только один раз. Рассматриваемый код выглядит следующим образом:

if t not in openSet or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    openSet.add(t)
    heapq.heappush(openHeap, (cost,t))

Первая проблема заключается в том, что вы нажимаете пару (cost, t), даже если вы потрудились дать своим Node объектам методы __lt__ и __gt__. Вместо этого просто поместите t в кучу:

heapq.heappush(openHeap, t)

Это требует пары изменений в другом месте: вместо

openHeap.append((curNode.cost,curNode))
while openSet:
    curNode = heapq.heappop(openHeap)[1]

вам придется написать

openHeap = [curNode]
while openSet:
    curNode = heapq.heappop(openHeap)

Теперь вторая проблема (это моя вина — извините) заключается в том, что если t уже находится в openSet, то мы не должны снова добавлять его в кучу. Вместо этого мы должны повторно выполнить heapify:

t_open = t in openSet
if not t_open or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    if t_open:
        heapq.heapify(openHeap)
    else:
        openSet.add(t)
        heapq.heappush(openHeap, t)

Возвращаясь к выводу отладчика, вспомните следующее:

(Pdb) curNode
Node(East, (1, 2), 3.41421356237)

Это 3.41421356237 должно вас беспокоить: не должна ли стоимость всегда быть целым числом? Похоже, что расчет стоимости все еще неверен. В нем говорится:

    cost = (curNode.cost
            - self.manHatDist(curNode.pos, end) 
            + self.euclidDist(curNode.pos, current)
            + self.manHatDist(t.pos, end))

но эта третья строка должна сказать:

            + self.euclidDist(curNode.pos, t.pos)

Итак, со всеми этими исправлениями, давайте попробуем еще раз:

>>> Search().aStar((0,0), (2,2))
['North', 'North', 'East', 'East']

Ответы на комментарии

1. "Как вы позвонили Search().aStar(...) из переводчика?" Я запустил интерпретатор, а затем ввел эту строку кода в приглашении интерпретатора. См. руководство.

2. «Поэтому евклидово расстояние всегда будет единицей». Да, если вы ищете пути в сетке с одинаковой стоимостью, то евклидово расстояние между соседями всегда будет одинаковым.

3. «Если подумать, curNode.cost - self.manHatDist(curNode.pos, end) всегда равно нулю». Это не правильно. В вашей реализации cost узла поиска — это (i) стоимость достижения этого узла с самого начала, плюс (ii) допустимая оценка стоимости достижения конца из этого узла. Поэтому, если вы вычтете допустимую оценку, вы должны снова вернуться к (i).