Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава Страница 28

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

У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла 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 и завершается раньше остальных.

Английский язык отпадает — он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.

Итак, эти три урока должны проводиться в классе.

Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное решение задачи составления расписания!

Конечно, жадные алгоритмы работают не всегда. Но они так просто реализуются! Рассмотрим другой пример.