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

Удивительно, но алгоритм поиска в ширину идентичен алгоритму поиска в глубину, только область поиска не стек, а очередь. Такое изменение области поиска меняет последовательность просмотра состояний и гарантирует, что первыми будут просмотрены состояния, ближайшие к начальному (файл generic_search.py).

def bfs(initial: T, goal_test: Callable[[T], bool],
        successors: Callable[[T], List[T]]) -> Optional[Node[T]]:
    # froпtier - это то, что мы только собираемся проверить
    frontier: Queue[Node[T]] = Queue()
    frontier.push(Node(initial, None))
    # expLored - это то, что уже проверено
    explored: Set[T] = {initial}
    # продолжаем, пока есть что проверять
    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state: T = current_node.state
        # если мы нашли искомое, то процесс закончен
        if goal_test(current_state):
            return current_node
        # ищем неисследованные ячейки, в которые можно перейти
        for child in successors(current_state):
            if child in explored: #пропустить состояния, которые уже исследовали
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))
    return None # все проверили, пути к целевой точке не нашли

Если вы запустите bfs(), то увидите, что эта функция всегда находит кратчайшее решение для рассматриваемого лабиринта. Следующий пробный запуск добавляется в раздел файла

if __name__ == "__main__":

сразу после предыдущего кода, так чтобы можно было сравнить результаты для одного и того же лабиринта.

if __name__ == "__main__":
    # Тестирование DFS
    m: Maze = Maze()
    print(m)
    solution1: Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successors)
    if solution1 is None:
        print("Поиском в глубину решение не найдено!")
    else:
        path1: List[MazeLocation] = node_to_path(solution1)
        m.mark(path1)
        print(m)
        m.clear(path1)
    # Тестирование BFS
    solution2: Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)
    if solution2 is None:
        print("Поиском в ширину решение не найдено!")
    else:
        path2: List[MazeLocation] = node_to_path(solution2)
        m.mark(path2)
        print(m)
        m.clear(path2)

Архив со всеми измененными файлами можно взять здесь.

Это удивительно, но мы можем, не меняя алгоритм, просто изменить структуру данных, к которой он обращается, и получить кардинально различные результаты. Далее показан результат вызова bfs() для того же лабиринта, для которого ранее мы вызывали dfs(). Обратите внимание на то, что на этот раз звездочки обозначают более прямой путь к цели, чем в предыдущем примере:

Рис.1. Результат работы приложения

На следующем шаге мы рассмотрим поиск по алгоритму A*.

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