Да, это продавец манго
return True
else:
search_queue += graph[person] Нет, не является. Все друзья этого человека добавляются в очередь поиска
return False Если выполнение дошло до этой строки, значит, в очереди нет продавца манго
И последнее: нужно определить функцию person_is_seller, которая сообщает, является ли человек продавцом манго. Например, функция может выглядеть так:
def person_is_seller(name):
return name[-1] == 'm'
Эта функция проверяет, заканчивается ли имя на букву «m», и если заканчивается, этот человек считается продавцом манго. Проверка довольно глупая, но для нашего примера сойдет. А теперь посмотрим, как работает поиск в ширину.
И так далее. Алгоритм продолжает работать до тех пор, пока:
• не будет найден продавец манго,
или
• очередь не опустеет (в этом случае продавца манго нет).
У Алисы и Боба есть один общий друг: Пегги. Следовательно, Пегги будет добавлена в очередь дважды: при добавлении друзей Алисы и при добавлении друзей Боба. В результате Пегги появится в очереди поиска в двух экземплярах.
Но проверить, является ли Пегги продавцом манго, достаточно всего один раз. Проверяя ее дважды, вы выполняете лишнюю, ненужную работу. Следовательно, после проверки человека нужно пометить как проверенного, чтобы не проверять его снова.
Если этого не сделать, может возникнуть бесконечный цикл. Предположим, граф выглядит так:
В начале очередь поиска содержит всех ваших соседей.
Теперь вы проверяете Пегги. Она не является продавцом манго, поэтому все ее соседи добавляются в очередь поиска.
Вы проверяете себя. Вы не являетесь продавцом манго, поэтому все ваши соседи добавляются в очередь поиска.
И так далее. Возникает бесконечный цикл, потому что очередь поиска будет поочередно переходить от вас к Пегги.
Прежде чем проверять человека, следует убедиться в том, что он не был проверен ранее. Для этого мы будем вести список уже проверенных людей.
А вот окончательная версия кода поиска в ширину, в которой учтено это обстоятельство:
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] Этот массив используется для отслеживания уже проверенных людей
while search_queue:
person = search_queue.popleft()
if not person in searched: Человек проверяется только в том случае, если он не проверялся ранее
if person_is_seller(person):
print person + " is a mango seller!"
return True
else:
search_queue += graph[person]
searched.append(person) Человек помечается как уже проверенный
return False
search("you")
Попробуйте выполнить этот код самостоятельно. Замените функцию person_is_seller чем-то более содержательным и посмотрите, выведет ли она то, что вы ожидали.
Время выполнения
Если поиск продавца манго был выполнен по всей сети, значит, вы прошли по каждому ребру (напомню: ребром называется соединительная линия или линия со стрелкой, ведущая от одного человека к другому). Таким образом, время выполнения составляет как минимум O(количество ребер).
Также в программе должна храниться очередь поиска. Добавление одного человека в очередь выполняется за постоянное время: O(1). Выполнение операции для каждого человека потребует суммарного времени O(количество людей). Поиск в ширину выполняется за время O(количество людей + количество ребер), что обычно записывается в форме O(V+E) (V — количество вершин, E — количество ребер).
Упражнения
Перед вами небольшой граф моего утреннего распорядка.
Из графа видно, что я завтракаю только после того, как почищу зубы. Таким образом, узел «Позавтракать» зависит от узла «Почистить зубы».
С другой стороны, душ не зависит от чистки зубов, потому что я могу сначала принять душ, а потом почистить зубы. На основании графа можно сформулировать порядок, в котором я действую утром:
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. Сколько времени понадобится, чтобы добраться до каждого из этих узлов?
До узла A вы будете добираться 6 минут, а до узла B — 2 минуты. Что касается остальных узлов, мы о них пока ничего не знаем.
Так как время достижения конечного узла остается неизвестным, мы считаем, что оно бесконечно (вскоре вы увидите почему.) Узел B — ближайший… он находится всего в 2 минутах.
Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей B при переходе по ребру из B.
Ого, да мы обнаружили более короткий путь к узлу A! Раньше для перехода к нему требовалось 6 минут.
А если идти через узел B, то существует путь, который занимает всего 5 минут!
Если вы нашли более короткий путь д