На этом шаге мы рассмотрим реализацию таких очередей.

    Чтобы выбрать из области поиска состояние с наименьшим f(n), при поиске А* в качестве структуры данных используется очередь с приоритетом для данной области поиска. В очереди с приоритетом элементы сохраняются во внутренней последовательности, так что первый извлеченный элемент - это элемент с наивысшим приоритетом. (В нашем случае наиболее приоритетным является элемент с наименьшим значением f(n).) Обычно это означает задействование внутри очереди бинарной кучи, что дает сложность O(lg n) для помещения в очередь и извлечения из нее.

    В стандартной библиотеке Python есть функции heappush() и heappop(), которые принимают список и сохраняют его в виде бинарной кучи. Мы можем реализовать очередь с приоритетом, создав тонкую обертку вокруг этих стандартных библиотечных функций. Класс PriorityQueue будет похож на классы Stack и Queue с методами push() и рор(), модифицированными для использования heappush() и heappop() (файл generic_search.py).

class PriorityQueue(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container  # не Тrue для пустого контейнера

    def push(self, item: T) -> None:
        heappush(self._container, item)  # поместить в очередь по приоритету

    def pop(self) -> T:
        return heappop(self._container)  # извлечь по приоритету

    def __repr__(self) -> str:
        return repr(self._container)

    Чтобы определить приоритет конкретного элемента по сравнению с аналогичными элементами, в heappush() и heappop() выполняется сравнение этих элементов с помощью оператора <. Вот почему ранее нам нужно было реализовать __lt__() для Node. Объекты Node сравниваются между собой по их значениям f(n), которые являются простой суммой свойств cost и heuristic.

    На следующем шаге мы рассмотрим эвристику.

Предыдущий шаг Содержание Следующий шаг