Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава
Книгу Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава читаем онлайн бесплатно полную версию! Чтобы начать читать не надо регистрации. Напомним, что читать онлайн вы можете не только на компьютере, но и на андроид (Android), iPhone и iPad. Приятного чтения!
Шрифт:
Интервал:
Закладка:
Каждый раз, когда вы проверяете кого-то из списка, вы добавляете в список всех его друзей.
В таком случае поиск ведется не только среди друзей, но и среди друзей друзей тоже. Напомним: нужно найти в сети хотя бы одного продавца манго. Если Алиса не продает манго, то в список добавляются ее друзья. Это означает, что со временем вы проверите всех ее друзей, а потом их друзей и т.д. С этим алгоритмом поиск рано или поздно пройдет по всей сети, пока вы все-таки не наткнетесь на продавца манго. Такой алгоритм и называется поиском в ширину.
Поиск кратчайшего пути
На всякий случай напомню два вопроса, на которые может ответить алгоритм поиска в ширину:
• тип 1: существует ли путь от узла A к узлу B? (Есть ли продавец манго в вашей сети?)
• тип 2: как выглядит кратчайший путь от узла A к узлу B? (Кто из продавцов манго находится ближе всего к вам?)
Вы уже знаете, как ответить на вопрос 1; теперь попробуем ответить на вопрос 2. Удастся ли вам найти ближайшего продавца манго? Будем считать, что ваши друзья — это связи первого уровня, а друзья друзей — связи второго уровня.
Связи первого уровня предпочтительнее связей второго уровня, связи второго уровня предпочтительнее связей третьего уровня и т.д. Отсюда следует, что поиск по контактам второго уровня не должен производиться, пока вы не будете полностью уверены в том, что среди связей первого уровня нет ни одного продавца манго. Но ведь поиск в ширину именно это и делает! Поиск в ширину распространяется от начальной точки. А это означает, что связи первого уровня будут проверены до связей второго уровня. Контрольный вопрос: кто будет проверен первым, Клэр или Анудж? Ответ: Клэр является связью первого уровня, а Анудж — связью второго уровня. Следовательно, Клэр будет проверена первой.
Также можно объяснить это иначе: связи первого уровня добавляются в список поиска раньше связей второго уровня.
Вы двигаетесь вниз по списку и проверяете каждого человека (является ли он продавцом манго). Связи первого уровня будут проверены до связей второго уровня, так что вы найдете продавца манго, ближайшего к вам. Поиск в ширину находит не только путь из A в B, но и кратчайший путь.
Обратите внимание: это условие выполняется только в том случае, если поиск осуществляется в порядке добавления людей. Другими словами, если Клэр была добавлена в список до Ануджа, то проверка Клэр должна быть выполнена до проверки Ануджа. А что произойдет, если вы проверите Ануджа раньше, чем Клэр, и оба они окажутся продавцами манго? Анудж является связью второго уровня, а Клэр — связью первого уровня. В результате будет найден продавец манго, не ближайший к вам в сети. Следовательно, проверять связи нужно в порядке их добавления. Для операций такого рода существует специальная структура данных, которая называется очередью.
Очереди
Очередь работает точно так же, как и в реальной жизни. Предположим, вы с другом стоите в очереди на автобусной остановке. Если вы стоите ближе к началу очереди, то вы первым сядете в автобус. Структура данных очереди работает аналогично. Очереди чем-то похожи на стеки: вы не можете обращаться к произвольным элементам очереди. Вместо этого поддерживаются всего две операции: постановка в очередь и извлечение из очереди.
Если вы поставите в очередь два элемента, то элемент, добавленный первым, будет извлечен из очереди раньше второго. А ведь это свойство можно использовать для реализации списка поиска! Люди, добавленные в список первыми, будут извлечены из очереди и проверены первыми.
Очередь относится к категории структур данных FIFO: First In, First Out («первым вошел, первым вышел»). А стек принадлежит к числу структур данных LIFO: Last In, First Out («последним пришел, первым вышел»).
Теперь, когда вы знаете, как работает очередь, можно переходить к реализации поиска в ширину!
Упражнения
Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.
6.1 Найдите длину кратчайшего пути от начального до конечного узла.
6.2 Найдите длину кратчайшего пути от «cab» к «bat».
Реализация графа
Для начала необходимо реализовать граф на программном уровне. Граф состоит из нескольких узлов. И каждый узел соединяется с соседними узлами. Как выразить отношение типа «вы –> боб»? К счастью, вам уже известна структура данных, способная выражать отношения: хеш-таблица!
Вспомните: хеш-таблица связывает ключ со значением. В данном случае узел должен быть связан со всеми его соседями.
А вот как это записывается на Python:
graph = {}
graph["you"] = ["alice", "bob", "claire"]
Обратите внимание: элемент «вы» (you) отображается на массив. Следовательно, результатом выражения graph["you"] является массив всех ваших соседей.
Граф — всего лишь набор узлов и ребер, поэтому для представления графа на Python ничего больше не потребуется. А как насчет большего графа, например такого?
Код на языке Python выглядит так:
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
Прочитали книгу? Предлагаем вам поделится своим отзывом от прочитанного(прослушанного)! Ваш отзыв будет полезен читателям, которые еще только собираются познакомиться с произведением.
Уважаемые читатели, слушатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.
- 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
- 2. Просьба отказаться от оскорблений, угроз и запугиваний.
- 3. Просьба отказаться от нецензурной лексики.
- 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.
Надеемся на Ваше понимание и благоразумие. С уважением, администратор knigkindom.ru.
Оставить комментарий
-
ANDREY07 июль 21:04 Прекрасное произведение с первой книги!... Роботам вход воспрещен. Том 7 - Дмитрий Дорничев
-
Гость Татьяна05 июль 08:35 Спасибо. Очень интересно ... В плену Гора - Мария Зайцева
-
Фарида02 июль 14:00 Замечательная книга!!! Спасибо автору за замечательные книги, до этого читала книгу"Странная", "Сосед", просто в восторге.... Одна ошибка - Татьяна Александровна Шумкова