Грокаем алгоритмы

        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!

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