невозможно перейти более дешевым способом, чем с оплатой $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 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Шпаргалка
• Поиск в ширину вычисляет кратчайший путь в невзвешенном графе.
• Алгоритм Дейкстры вычисляет кратчайший путь во взвешенном графе.
• Алгоритм Дейкстры работает только в том случае, если все веса положительны.
• При наличии отрицательных весов используйте алгоритм Беллмана—Форда.
8. Жадные алгоритмы
В этой главе
• Вы узнаете, как браться за невозможные задачи, не имеющие быстрого алгоритмического решения (NP-полные задачи).
• Вы научитесь узнавать такие задачи и не терять время на поиски быстрого алгоритма (которого все равно нет).
• Вы познакомитесь с приближенными алгоритмами, которые могут использоваться для быстрого нахождения приближенного решения NP-полных задач.
• Вы узнаете о жадной стратегии — очень простой стратегии решения задач
Задача составления расписания
Допустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков.
Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.
Требуется провести в классе как можно больше уроков. Как отобрать уроки, чтобы полученный набор оказался самым большим из возможных?
Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:
1. Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.
2. Затем выбирается урок, начинающийся после завершения первого урока. И снова следует выбрать урок, который завершается раньше всех остальных. Он становится вторым уроком в расписании.
Продолжайте действовать по тому же принципу — и вы получите ответ! Давайте попробуем. Рисование заканчивается раньше всех уроков (в 10:00), поэтому мы выбираем именно его.
Теперь нужно найти следующий урок, который начинается после 10:00 и завершается раньше остальных.
Английский язык отпадает — он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.
Итак, эти три урока должны проводиться в классе.
Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В технической терминологии: на каждом шаге выбирается