Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 20)
Получить стоимость и соседей этого узла.
Перебрать соседей.
У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла 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 и завершается раньше остальных.
Английский язык отпадает — он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.
Итак, эти три урока должны проводиться в классе.
Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В технической терминологии: на каждом шаге выбирается
Конечно, жадные алгоритмы работают не всегда. Но они так просто реализуются! Рассмотрим другой пример.
Задача о рюкзаке
Представьте, что вы жадный воришка. Вы забрались в магазин с рюкзаком, и перед вами множество товаров, которые вы можете украсть. Однако емкость рюкзака не бесконечна: он выдержит не более 35 фунтов.
Требуется подобрать набор товаров максимальной стоимости, которые можно сложить в рюкзак. Какой алгоритм вы будете использовать?
И снова жадная стратегия выглядит очень просто:
1. Выбрать самый дорогой предмет, который поместится в рюкзаке.
2. Выбрать следующий по стоимости предмет, который поместится в рюкзаке… И так далее.
Вот только на этот раз она не работает! Предположим, есть три предмета.
В рюкзаке поместятся товары общим весом не более 35 фунтов. Самый дорогой товар — магнитофон, вы выбираете его. Теперь ни для чего другого места уже не осталось.
Вы набрали товаров на $3000. Погодите-ка! Если бы вместо магнитофона вы выбрали ноутбук и гитару, то стоимость добычи составила бы $3500!
Очевидно, жадная стратегия не дает оптимального решения. Впрочем, результат не так уж далек от оптимума. В следующей главе я расскажу, как вычислить правильное решение. Но вор, забравшийся в магазин, вряд ли станет стремиться к идеалу. «Достаточно хорошего» решения должно хватить.
Второй пример приводит нас к следующему выводу: иногда идеальное — враг хорошего. В некоторых случаях достаточно алгоритма, способного решить задачу достаточно хорошо. И в таких областях жадные алгоритмы работают просто отлично, потому что они просто реализуются, а полученное решение обычно близко к оптимуму.
Упражнения
8.1 Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?