Алгоритмы поиска путей на пальцах: Часть 1 — Поиск в ширину05.11.2024 12:31

Давайте представим, что вы устроились много лет назад в 2GIS и вам выпала честь написать алгоритм, который будет прокладывать самый короткий автомобильный маршрут от точки A к точке B.

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

В первой части:

Что такое графы, как их читать и составлять
Как работает алгоритм поиска в ширину (BFS)
Что такое двусторонняя очередь (модуль deque)

Во второй части:

Прежде чем мы продолжим, хочу пригласить в мой телеграмм канал Don Python, где я делюсь интересными особенностями языка, не очевидными фишками и решаю разные задачи.

Подписаться

Введение в графы

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

Графы — это математическая структура, которая состоит из вершин (или узлов) и соединяющих их рёбер. Графы бывают разного типа: ориентированные (где рёбра имеют направление) и неориентированные (где направление не имеет значения), взвешенные (с весами рёбер) и невзвешенные.

В процессе разбора алгоритмов мы обсудим неориентированные невзвешенные и взвешенные графы. А в этой части обойдемся неориентированным и невзвешенным графом:

С помощью этого графа мы имитируем карту небольшой местности, где круглые фигуры — это узлы, а соединяющие их линии — это рёбра. Также не трудно догадаться, что узлы имитируют здания (места), а рёбра дороги.

Зададимся вопросом: если некто хочет попасть из узла Home в узел Theater, каким будет самый короткий маршрут для предстоящего пути? Руководствуясь имеющимися данными, которые не учитывают направлений и протяженности дорог, можно сказать что самый короткий маршрут будет таким:

[Home, Park, Cafe, Theater]

Так как в этом графе рёбра не имеют веса, мы присваиваем каждому ребру единицу, которая сообщает, что для перехода к соседней вершине необходимо преодолеть некую единицу маршрута. Таким образом мы можем «проехать» к театру двумя способами:

[Home, Park, Cafe, Theater] — 3 ребра
[Home, Park, Museum, Shop, Theater] — 4 ребра

Теперь мы видим, что выделенный на изображении маршрут короче другого возможного маршрута на единицу.

Визуально это определить довольно легко, но как это представить с помощью кода?

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

Поиск в ширину — Breadth First Search (BFS)

BFS — это классический алгоритм для работы с невзвешенными графами.

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

Наш первый случай — это как раз невзвешенный граф, в котором мы ищем кратчайший путь между вершинами.

Прежде чем переходить к решению, давайте посмотрим наглядно как происходит обход графа:

Что бы работать с графом, нам нужно каким-то образом представить его в виде объекта в коде. В нашем случае это будет словарь:

city_map = {  
    'Home': ['Park', 'School', 'Mail'],  
    'Park': ['Home', 'Museum', 'Cafe'],  
    'School': ['Home', 'Library', 'Mail'],  
    'Mail': ['Home', 'School', 'Hospital'],  
    'Library': ['School', 'Hospital'],  
    'Hospital': ['Library', 'Mail', 'Office'],  
    'Cafe': ['Park', 'Theater', 'Office'],  
    'Museum': ['Park', 'Shop'],  
    'Shop': ['Museum', 'Theater'],  
    'Theater': ['Shop', 'Cafe'],  
    'Office': ['Cafe', 'Hospital']  
}

Такое представление удобно для хранения связей между вершинами графа, где ключи — это вершины, а значения — это списки соседних вершин, с которыми они соединены.

Напишем функцию для нахождения кратчайшего пути от Home до Theater, а затем поэтапно разберем итоговый код.

from collections import deque  
  
  
def bfs_shortest_path(city_map, start, goal):   
    queue = deque([[start]])  
    visited = set()  
  
    while queue:  
        path = queue.popleft()  
        node = path[-1]  
  
        if node in visited:  
            continue  
  
        visited.add(node)  
  
        if node == goal:  
            return path  
  
        for neighbor in city_map.get(node, []):  
            new_path = list(path) 
            new_path.append(neighbor)  
            queue.append(new_path)  
  
    return None  
  

city_map = {...}
  
start = 'Home'  
goal = 'Theater'  
shortest_path = bfs_shortest_path(city_map, start, goal)  
print("Кратчайший путь от Home до Theater:", shortest_path)

# >>> Кратчайший путь от Home до Theater: ['Home', 'Park', 'Cafe', 'Theater']

Давайте обсудим что происходит.

Двусторонняя очередь в Python

Для работы мы импортируем класс deque встроенного в python модуля collections. Подробно вы можете почитать вот здесь. Я же коротко объясню зачем нам это.

Класс deque (от «double-ended queue» — двухсторонняя очередь) в python удобен для работы с коллекцией элементов, где важны операции добавления и удаления элементов в начале и в конце списка. Обычные списки делают это медленно, так как элементы приходится смещать, а deque оптимизирован под такие операции, выполняя их за O (1).

from collections import deque  
  
# Создаем deque и добавляем элементы  
queue = deque([1, 2, 3])  
queue.append(4)       # добавляет 4 в конец  
queue.appendleft(0)   # добавляет 0 в начало  
  
print(queue)          # deque([0, 1, 2, 3, 4])  
  
# Удаляем элементы  
queue.pop()           # удаляет последний элемент  
queue.popleft()       # удаляет первый элемент  
  
print(queue)          # deque([1, 2, 3])

Большего для текущей задачи знать не нужно.

Инициализация функции

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

def bfs_shortest_path(city_map, start, goal):  
    queue = deque([[start]])  
    visited = set()

	return None

В примере с deque мы передавали одномерный список, а здесь передаём двумерный. Что бы не сбиться с толку, не обращайте пока что на это внимания, дальше всё станет понятно.

Цикл while

Мы не можем точно сказать, сколько нам потребуется итераций что бы достичь нужного результата. Поэтому функция будет работать, пока не переберет все возможные пути, либо пока не придет к цели. Для этого и будем использовать цикл while.

while queue:

Пока в очереди есть объекты, цикл работает. Почему очередь должна закончится узнаем дальше.

Теперь нам нужно выполнить три действия и две проверки:

1. Извлекаем первый путь из очереди:

while queue:
	path = queue.popleft()

На первой итерации извлекается путь [Home], так как в нашем случае это стартовый узел и другие пути еще неизвестны. Далее будут добавляться следующие пути для проверки. Здесь же становится понятно, почему мы создали очередь с двумерным списком: путь чаще состоит из последовательности элементов, поэтому нам нужен список списков (путей).

2. Достаем последний узел в текущем пути:

while queue:
	path = queue.popleft()  
	node = path[-1]

Мы извлекли (удаляем из очереди и присваиваем переменной path) первый путь из очереди. Из этого пути достаем (без изменения пути) последний узел. Последний, потому что как было видно на изображении, граф — это структура данных, которая ветвится сверху вниз. Поиск в ширину обходит все узлы и на каждой итерации начинает с крайнего (последнего) доступного.

3. Проверяем, был ли узел посещен:

while queue:
	path = queue.popleft()  
	node = path[-1]  

	if node in visited:  
		continue

Если узел был посещен — ничего больше не делаем и переходим к следующей итерации. Почему некоторые вершины могут появиться два раза? Вернитесь к изображения графа и обратите внимание, что, например, узел School является соседом для двух вышестоящих или равных по уровню узлов: Home и Mail. Так как узел Home имеет прямую связь с узлом School, после первой итерации цикла while очередь будет выглядеть вот так:

deque([['Home', 'Park'], ['Home', 'School'], ['Home', 'Mall']])

Когда цикл обработает путь по индексу 1, узел School будет обработан. Но когда дело дойдет до узла Mail, в очередь попадёт следующий путь:

['Home', 'Mall', 'School']

Обрабатывая этот путь, циклу придется снова иметь дело с узлом School. Но так как этот узел уже был посещен, на этом этапе мы игнорируем дальнейшие действия с помощью условия.

4. Отмечаем посещенный узел:

while queue:
	path = queue.popleft()  
	node = path[-1]  

	if node in visited:  
		continue  

	visited.add(node)

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

5. Сравниваем текущий узел с целевым:

while queue:
	path = queue.popleft()  
	node = path[-1]  

	if node in visited:  
		continue  

	visited.add(node)  
	
	if node == goal:  
		return path

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

Цикл For. Добавление пути в очередь.

Если цикл while не завершился и все проверки были пройдены, функция должна обработать всех соседей текущего узла. Здесь мы будем использовать цикл for, так как количество итераций зависит от количества соседей.

def bfs_shortest_path(city_map, start, goal):  
    ...
    while queue:
	    ...
	    for ...
	...

1. Пробегаемся по списку соседей:

def bfs_shortest_path(city_map, start, goal):  
    ...
    while queue:
	    ...
	    for neighbor in city_map.get(node, []):
	...

Для обращения к текущему узлу в словаре city_map используем метод get(). Почему не обращаемся напрямую? Метод get() гарантирует безопасное обращение. Если вдруг узла не окажется в словаре, то код не упадёт с ошибкой, а вместо запрашиваемого значения просто вернется пустой список.

2. Создаем новый путь и добавляем к нему следующий узел:

def bfs_shortest_path(city_map, start, goal):  
    ...
    while queue:
	    ...
	    for neighbor in city_map.get(node, []):  
		    new_path = list(path)
		    new_path.append(neighbor)  
    ...

path представляет собой текущий путь от начального узла до node. Это условно статичные данные в рамках действия алгоритма, поэтому менять напрямую их нельзя. Что бы избежать изменений, создаём новый путь и копируем в него текущий. Это позволяет нам расширять путь для каждого соседа, не изменяя исходный путь.

Далее мы добавляем текущего соседа neighbor в конец копии пути new_path. Теперь new_path представляет собой путь от начального узла до neighbor через node.

3. Добавляем новый путь в очередь:

def bfs_shortest_path(city_map, start, goal):  
    ...
    while queue:
	    ...
	    for neighbor in city_map.get(node, []):  
		    new_path = list(path)
		    new_path.append(neighbor)  
		    queue.append(new_path)
    ...

После добавления new_path в queue BFS сможет продолжить поиск, начиная с нового соседа, на следующей итерации.

Функция готова. Осталось только вызвать ее с необходимыми параметрами.

Вызов функции

Определим начало и конец пути, и вызовем функцию:

def bfs_shortest_path(city_map, start, goal):
	...


start = 'Home'  
goal = 'Theater'  
shortest_path = bfs_shortest_path(city_map, start, goal)  
print("Кратчайший путь от Home до Theater:", shortest_path)

# >>> Кратчайший путь от Home до Theater: ['Home', 'Park', 'Cafe', 'Theater']

Предлагаю вернуться к обратно к полному коду, зафиксировать решение, переписать код и поиграться с разными графами и входными данными.

Замечание

Если в графе есть несколько одинаковых коротких путей, алгоритм вернет первый найденный короткий путь. Если вы знаете как доработать решение для возврата всех коротких путей, поделитесь ответом в комментариях.

Говоря о нашем примере, если вы начнете поиск от Mail до Theater, то функция вернет следующий путь:

['Mail', 'Home', 'Park', 'Cafe', 'Theater']

Хотя есть еще один путь, который на первый взгляд более очевиден:

['Mail', 'Hospital', 'Office', 'Cafe', 'Theater']

Это была первая часть. В следующей части мы разберем более интересный случай и будем работать с неориентированным взвешенным графом и применим алгоритм Дейкстры для поиска кротчайшего пути.

Good coding!

Телеграм канал о разработке на python — Don Python

Ресурсы

Редактор графов
Редактор gif
Пособие по алгоритмам