Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

В предыдущей главе вы узнали, как найти путь из точки A в точку B.

Найденный путь не обязательно окажется самым быстрым. Этот путь считается кратчайшим, потому что он состоит из наименьшего количества сегментов (три сегмента). Но предположим, с каждым сегментом связывается продолжительность перемещения. И тогда выясняется, что существует и более быстрый путь.

В предыдущей главе рассматривался поиск в ширину. Этот алгоритм находит путь с минимальным количеством сегментов (граф на первом рисунке). А если вы захотите найти самый быстрый путь (второй граф)? Быстрее всего это делается при помощи другого алгоритма, который называется алгоритмом Дейкстры.

Работа с алгоритмом Дейкстры

Посмотрим, как этот алгоритм работает с графом.

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

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

Этот путь занимает 7 минут. А может, существует путь, который займет меньше времени? Алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).

2. Обновить стоимости соседей этого узла (вскоре я объясню, что имеется в виду).

3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь.

Шаг 1: найти узел с наименьшей стоимостью. Вы стоите в самом начале и думаете, куда направиться: к узлу A или к узлу B. Сколько времени понадобится, чтобы добраться до каждого из этих узлов?

До узла A вы будете добираться 6 минут, а до узла B — 2 минуты. Что касается остальных узлов, мы о них пока ничего не знаем.

Так как время достижения конечного узла остается неизвестным, мы считаем, что оно бесконечно (вскоре вы увидите почему.) Узел B — ближайший… он находится всего в 2 минутах.

Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей B при переходе по ребру из B.

Ого, да мы обнаружили более короткий путь к узлу A! Раньше для перехода к нему требовалось 6 минут.

А если идти через узел B, то существует путь, который занимает всего 5 минут!

Если вы нашли более короткий путь для соседа B, обновите его стоимость. В данном случае мы нашли:

• Более короткий путь к A (сокращение с 6 минут до 5 минут).

• Более короткий путь к конечному узлу (сокращение от бесконечности до 7 минут).

Шаг 3: повторяем!

Снова шаг 1: находим узел, для перехода к которому требуется наименьшее время. С узлом B работа закончена, поэтому наименьшую оценку времени имеет узел A.

Снова шаг 2: обновляем стоимости соседей A.

Путь до конечного узла теперь занимает всего 6 минут!

Алгоритм Дейкстры выполнен для каждого узла (выполнять его для конечного узла не нужно). К этому моменту вам известно следующее:

• Чтобы добраться до узла B, нужно 2 минуты.

• Чтобы добраться до узла A, нужно 5 минут.

• Чтобы добраться до конечного узла, нужно 6 минут.

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

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

В предыдущей главе мы использовали поиск в ширину для нахождения кратчайшего пути между двумя точками. Тогда под «кратчайшим путем» понимался путь с минимальным количеством сегментов. С другой стороны, в алгоритме Дейкстры каждому сегменту присваивается число (вес), а алгоритм Дейкстры находит путь с наименьшим суммарным весом.

На всякий случай повторим: алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).

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

3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь (об этом в следующем разделе!).

Терминология

Я хочу привести еще несколько примеров применения алгоритма Дейкстры. Но сначала стоит немного разобраться с терминологией.

Когда вы работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом.

Граф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.

Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры. В графах также могут присутствовать циклы:

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

Есть ли смысл в перемещении по циклу? Что ж, вы можете использовать путь без прохождения цикла:

А можете пройти по циклу:

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

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

Наконец, вы еще не забыли наше обсуждение направленных и ненаправленных графов из главы 6?

Само понятие ненаправленного графа означает, что каждый из двух узлов фактически ведет к другому узлу. А это цикл!

В ненаправленном графе каждое новое ребро добавляет еще один цикл. Алгоритм Дейкстры работает только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph).

История одного обмена

Но довольно терминологии, пора рассмотреть конкретный пример! Это Рама. Он хочет выменять свою книгу по музыке на пианино.

«Я тебе дам за книгу вот этот постер, — говорит Алекс. — Это моя любимая группа Destroyer. Или могу дать за книгу редкую пластинку Рика Эстли и еще $5». — «О, я слышала, что на этой пластинке есть отличные песни, — говорит Эми. — Готова отдать за постер или пластинку мою гитару или ударную установку».

«Всю жизнь мечтал играть на гитаре, — восклицает Бетховен. — Слушай, я отдам тебе свое пианино за любую из вещей Эми».

Прекрасно! Рама с небольшими дополнительными тратами может поменять свою книгу на настоящее пианино. Теперь остается понять, как ему потратить наименьшую сумму на цепочке обменов. Изобразим полученные им предложения в виде графа:

Узлы графа — это предметы, на которые может поменяться Рама. Веса ребер представляют сумму доплаты за обмен. Таким образом, Рама может поменять постер на гитару за $30 или же поменять пластинку на гитару за $15. Как Раме вычислить путь от книги до пианино, при котором он потратит наименьшую сумму? На помощь приходит алгоритм Дейкстры! Вспомните, что алгоритм Дейкстры состоит из четырех шагов. В этом примере мы выполним все четыре шага, а в конце будет вычислен итоговый путь.

Прежде чем начинать, необходимо немного подготовиться. Постройте таблицу со стоимостями всех узлов. (Стоимость узла определяет затраты на его достижение.)

Таблица будет обновляться по мере работы алгоритма. Для вычисления итогового пути в таблицу также необходимо добавить столбец «родитель».

Вскоре я покажу, как работает этот столбец. А пока просто запустим алгоритм.

Шаг 1: найти узел с наименьшей стоимостью. В данном случае самый дешевый вариант обмена с доплатой $0 — это постер. Возможно ли получить постер с меньшими затратами? Это очень важный момент, хорошенько подумайте над ним. Удастся ли вам найти серию обменов, при которой Рама получит постер менее чем за $0? Продолжайте читать, когда будете готовы ответить на вопрос. Правильный ответ: нет, не удастся. Так как постер является узлом с наименьшей стоимостью, до которого может добраться Рама, снизить его стоимость невозможно. На происходящее можно взглянуть иначе: предположим, вы едете из дома на работу.

Если вы выберете путь к школе, это займет 2 минуты. Если вы выберете путь к парку, это займет 6 минут. Существует ли путь, при котором вы выбираете путь к парку и оказываетесь в школе менее чем за 2 минуты? Это невозможно, потому что только для того, чтобы попасть в парк, потребуется более 2 минут. С другой стороны, можно ли найти более быстрый путь в парк? Да, можно.

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

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

Шаг 2: Вычислить, сколько времени потребуется для того, чтобы добраться до всех его соседей (стоимость).

Стоимости бас-гитары и барабана заносятся в таблицу. Они были заданы при переходе через узел постера, поэтому постер указывается как их родитель. А это означает, что для того, чтобы добраться до бас-гитары, вы проходите по ребру от постера; то же самое происходит с барабаном.

Снова шаг 1: пластинка — следующий по стоимости узел ($5).

Снова шаг 2: обновляются значения всех его соседей.

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

Следующий по стоимости узел — бас-гитара. Обновите данные его соседей.

Хорошо, мы наконец-то вычислили стоимость для пианино при условии обмена гитары на пианино. Соответственно, гитара назначается родителем. Наконец, задается стоимость последнего узла — барабана.

Оказывается, Рама может получить пианино еще дешевле, поменяв ударную установку на пианино. Таким образом, самая дешевая цепочка обменов обойдется Раме в $35.

Теперь, как я и обещал, необходимо вычислить итоговый путь. К этому моменту вы уже знаете, что кратчайший путь обойдется в $35, но как этот путь определить? Для начала возьмем родителя узла «пианино».

В качестве родителя узла «пианино» указан узел «барабан».

А в качестве родителя узла «барабан» указан узел «пластинка».

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

Серия обменов, которую должен сделать Рама, выглядит так:

До сих пор я использовал термин «кратчайший путь» более или менее буквально, понимая под ним вычисление кратчайшего пути между двумя точками или двумя людьми. Надеюсь, этот пример показал, что кратчайший путь далеко не всегда связывается с физическим расстоянием: он может быть направлен на минимизацию какой-либо характеристики. В нашем примере Рама хотел свести к минимуму свои затраты при обмене. Спасибо Дейкстре!

Ребра с отрицательным весом

В предыдущем примере Алекс предложил в обмен на книгу один из двух предметов.

Предположим, Сара предложила обменять пластинку на постер и при этом она еще и даст Раме $7. Рама ничего не тратит при этом обмене, вместо этого он получит $7. Как изобразить это предложение на графе?

Ребро, ведущее от пластинки к постеру, имеет отрицательный вес! Если Рама пойдет на этот обмен, он получит $7. Теперь к постеру можно добраться двумя способами.

А значит, во втором обмене появляется смысл — Рама получает $2!

Теперь, если вы помните, Рама может обменять постер на барабан. И здесь возможны два пути.

Второй путь обойдется на $2 дешевле, поэтому нужно выбрать этот путь, верно?

И знаете что? Если применить алгоритм Дейкстры к этому графу, Рама выберет неверный путь. Он пойдет по более длинному пути. Алгоритм Дейкстры не может использоваться при наличии ребер, имеющих отрицательный вес. Такие ребра нарушают работу алгоритма. Посмотрим, что произойдет, если попытаться применить алгоритм Дейкстры к этому графу. Все начинается с построения таблицы стоимостей.

Теперь найдем узел с наименьшей стоимостью и обновим стоимости его соседей. В этом случае постер оказывается узлом с наименьшей стоимостью. Итак, в соответствии с алгоритмом Дейкстры, к постеру невозможно перейти более дешевым способом, чем с оплатой $0 (а вы знаете, что это неверно!) Как бы то ни было, обновим стоимости его соседей.

Получается, что теперь стоимость барабана составляет $35.

Перейдем к следующему по стоимости узлу, который еще не был обработан.

Обновим стоимости его соседей.

Узел «постер» уже был обработан, однако вы обновляете его стоимость. Это очень тревожный признак — обработка узла означает, что к нему невозможно добраться с меньшими затратами. Но вы только что нашли более дешевый путь к постеру! У барабана соседей нет, поэтому работа алгоритма завершена. Ниже приведены итоговые стоимости.

Чтобы добраться до барабанов, Раме потребовалось $35. Вы знаете, что существует путь, который стоит всего $33, но алгоритм Дейкстры его не находит. Алгоритм Дейкстры предположил, что, поскольку вы обрабатываете узел «постер», к этому узлу невозможно добраться быстрее. Это предположение работает только в том случае, если ребер с отрицательным весом не существует. Следовательно, использование алгоритма Дейкстры с графом, содержащим ребра с отрицательным весом, невозможно. Если вы хотите найти кратчайший путь в графе, содержащем ребра с отрицательным весом, для этого существует специальный алгоритм, называемый алгоритмом Беллмана—Форда. Рассмотрение этого алгоритма выходит за рамки этой книги, но вы сможете найти хорошие описания в Интернете.

Реализация

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

Для реализации этого примера понадобятся три хеш-таблицы.

Хеш-таблицы стоимостей и родителей будут обновляться по ходу работы алгоритма. Сначала необходимо реализовать граф. Как и в главе 6, для этого будет использована хеш-таблица:

graph = {}

В предыдущей главе все соседи узла были сохранены в хеш-таблице:

graph["you"] = ["alice", "bob", "claire"]

Но на этот раз необходимо сохранить как соседей, так и стоимость перехода к соседу. Предположим, у начального узла есть два соседа, A и B.

Как представить веса этих ребер? Почему бы не воспользоваться другой хеш-таблицей?

graph["start"] = {}

graph["start"]["a"] = 6

graph["start"]["b"] = 2

Итак, graph["start"] является хеш-таблицей. Для получения всех соседей начального узла можно воспользоваться следующим выражением:

>>> print graph["start"].keys()

["a", "b"]

Одно ребро ведет из начального узла в A, а другое — из начального узла в B. А если вы захотите узнать веса этих ребер?

>>> print graph["start"]["a"]

2

>>> print graph["start"]["b"]

6

Включим в граф остальные узлы и их соседей:

graph["a"] = {}

graph["a"]["fin"] = 1

graph["b"] = {}

graph["b"]["a"] = 3

graph["b"]["fin"] = 5

graph["fin"] = {} У конечного узла нет соседей

Полная хеш-таблица графа выглядит так:

Также понадобится хеш-таблица для хранения стоимостей всех узлов.

Стоимость узла определяет, сколько времени потребуется для перехода к этому узлу от начального узла. Вы знаете, что переход от начального узла к узлу B занимает 2 минуты. Вы знаете, что для перехода к узлу A требуется 6 минут (хотя, возможно, вы найдете более быстрый путь). Вы не знаете, сколько времени потребуется для достижения конечного узла. Если стоимость еще неизвестна, она считается бесконечной. Можно ли представить бесконечность в Python? Оказывается, можно:

infinity = float("inf")

Код создания таблицы стоимостей costs:

infinity = float("inf")

costs = {}

costs["a"] = 6

costs["b"] = 2

costs["fin"] = infinity

Для родителей также создается отдельная таблица:

Код создания хеш-таблицы родителей:

parents = {}

parents["a"] = "start"

parents["b"] = "start"

parents["fin"] = None

Наконец, вам нужен массив для отслеживания всех уже обработанных узлов, так как один узел не должен обрабатываться многократно:

processed = []

На этом подготовка завершается. Теперь обратимся к алгоритму.

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

node = find_lowest_cost_node(costs) Найти узел с наименьшей стои­мостью среди необработанных

while node is not None: Если обработаны все узлы, цикл while завершен

cost = costs[node]

neighbors = graph[node]

for n in neighbors.keys(): Перебрать всех соседей текущего узла

new_cost = cost + neighbors[n]

if costs[n] > new_cost: Если к соседу можно быстрее добраться через текущий узел…

costs[n] = new_cost …обновить стоимость для этого узла

parents[n] = node Этот узел становится новым родителем для соседа

processed.append(node) Узел помечается как обработанный

node = find_lowest_cost_node(costs) Найти следующий узел для обработки и повторить цикл

Так выглядит алгоритм Дейкстры на языке Python! Код функции будет приведен далее, а пока рассмотрим пример использования алгоритма в действии.

Найти узел с наименьшей стоимостью.

Получить стоимость и соседей этого узла.

Перебрать соседей.

У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла A по пути Начало > Узел B > Узел A (вместо Начало > Узел A).

Сравним эти стоимости.

Мы нашли более короткий путь к узлу A! Обновим стоимость.

Новый путь проходит через узел B, поэтому B назначается новым родителем.

Мы снова вернулись к началу цикла. Следующим соседом в цикле for является конечный узел.

Сколько времени потребуется для достижения конечного узла, если идти через узел B?

Потребуется 7 минут. Предыдущая стоимость была бесконечной, а 7 минут определенно меньше бесконечности.

Конечному узлу назначается новая стоимость и новый родитель.

Порядок, мы обновили стоимости всех соседей узла B. Узел помечается как обработанный.

Найти следующий узел для обработки.

Получить стоимость и соседей узла A.

У узла A всего один сосед: конечный узел.

Время достижения конечного узла составляет 7 минут. Сколько времени потребуется для достижения конечного узла, если идти через узел A?

Через узел A можно добраться быстрее! Обновим стоимость и родителя.

После того как все узлы будут обработаны, алгоритм завершается. Надеюсь, этот пошаговый разбор помог вам чуть лучше понять алгоритм. С функцией find_lowest_cost_node узел с наименьшей стоимостью находится проще простого. Код выглядит так:

def ind_lowest_cost_node(costs):

lowest_cost = loat("inf")

lowest_cost_node = None

for node in costs: Перебрать все узлы

cost = costs[node]

if cost < lowest_cost and node not in processed: Если это узел с наименьшей стоимостью из уже виденных и он еще не был обработан…

lowest_cost = cost …он назначается новым узлом с наименьшей стоимостью

lowest_cost_node = node

return lowest_cost_node

Упражнения

7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?

Шпаргалка

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

• Алгоритм Дейкстры вычисляет кратчайший путь во взвешенном графе.

• Алгоритм Дейкстры работает только в том случае, если все веса положительны.

• При наличии отрицательных весов используйте алгоритм Беллмана—Форда.