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

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

1. Проснуться.

2. Принять душ.

3. Почистить зубы.

4. Позавтракать.

Следует заметить, что действие «Принять душ» может перемещаться в списке, поэтому следующий список тоже действителен:

1. Проснуться.

2. Почистить зубы.

3. Принять душ.

4. Позавтракать.

6.3 Для каждого из следующих трех списков укажите, действителен он или недействителен.

А

б

в

1. Проснуться

2. Принять душ

3. Позавтракать

4. Почистить зубы

1. Проснуться

2. Почистить зубы

3. Позавтракать

4. Принять душ

1. Принять душ

2. Проснуться

3. Почистить зубы

4. Позавтракать

6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.

Можно сказать, что этот список в некотором смысле отсортирован. Если задача A зависит от задачи B, то задача A находится в более поздней позиции списка. Такая сортировка называется топологической; фактически она предоставляет способ построения упорядоченного списка на основе графа. Предположим, вы планируете свадьбу и у вас составлен большой граф с множеством задач, но вы не знаете, с чего начать. Проведите топологическую сортировку графа — и получите список задач, которые можно выполнять одну за другой.

Допустим, имеется генеалогическое древо.

Генеалогическое древо — тоже граф, потому что в нем есть узлы (люди) и ребра. Ребра указывают на родителей человека. Естественно, все ребра направлены вниз — в генеалогическом дереве ребро, указывающее вверх, не имеет смысла. Ведь ваш отец никак не может быть дедушкой вашего дедушки!

Такая особая разновидность графа, в которой нет ребер, указывающих в обратном направлении, называется деревом.

6.5 Какие из следующих графов также являются деревьями?

Шпаргалка

• Поиск в ширину позволяет определить, существует ли путь из A в B.

• Если путь существует, то поиск в ширину находит кратчайший путь.

• Если в вашей задаче требуется найти «кратчайшее X», попробуйте смоделировать свою задачу графом и воспользуйтесь поиском в ширину для ее решения.

• В направленном графе есть стрелки, а отношения действуют в направлении стрелки (Рама —> Адит означает «Рама должен Адиту»).

• В ненаправленных графах стрелок нет, а отношение идет в обе стороны (Росс – Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встречается с Россом».)

• Очереди относятся к категории FIFO («первым вошел, первым вышел»).

• Стек относится к категории LIFO («последним пришел, первым вышел»).

• Людей следует проверять в порядке их добавления в список поиска, поэтому список поиска должен быть оформлен в виде очереди, иначе найденный путь не будет кратчайшим.

• Позаботьтесь о том, чтобы уже проверенный человек не проверялся заново, иначе может возникнуть бесконечный цикл.

7. Алгоритм Дейкстры

В этой главе

• Мы продолжим изучение графов и познакомимся со взвешенными графами, в которых некоторым ребрам назначаются большие или меньшие веса.

• Вы изучите алгоритм Дейкстры, который позволяет получить ответ на вопрос «Как выглядит кратчайший путь к X?» для взвешенных графов.

• Вы узнаете о циклах в графах, для которых алгоритм Дейкстры не работает.

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

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

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

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

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

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

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

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

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

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

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

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

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