Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 186
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
52 ГЛАВА 2
турнира, у задачи поиска кратчайшего пути существует эффективный алго- ритм, поэтому нет никакого смысла использовать жадную эвристику.
A
B
C
D
E
F
3 1
3 4
6 2
5 1
2
В 1956 году молодой голландский информатик, Эдсгер Дейкстра, делал покупки в амстердамских магазинах вместе со своей невестой. Устав, они присели на террасе кафе, чтобы выпить чашечку кофе. Дейкстра начал обду- мывать задачу поиска лучшего пути из одного города в другой. Он набросал решение за 20 минут, хотя сам алгоритм был опубликован лишь спустя три года. Дейкстра имел блестящую карьеру, но, к его удивлению, именно это
20-минутное озарение сделало его знаменитым.
Так как же выглядит этот алгоритм? Мы хотим найти кратчайшие пути из одного узла графа ко всем другим. В этом алгоритме используется прин- цип релаксации: значениям, которые нужно найти (в данном случае расстоя- ниям), дается приблизительная оценка. Вначале наши оценки максимально плохие. Затем по мере работы алгоритма они постепенно улучшаются, пока мы не получим правильные значения.
В алгоритме Дейкстры релаксация происходит следующим образом. Вна- чале мы присваиваем расстояниям от одного узла ко всем остальным наихуд- шее из возможных значений: бесконечность; очевидно, что длиннее ничего быть не может! На следующем рисунке мы указали рядом с узлами началь- ную оценку кратчайшего пути и предыдущего узла в нем. Для узла A это 0/–, поскольку расстояние от A к A равно нолю, и у A нет предыдущего узла. Рядом со всеми остальными узлами указано ∞/–, потому что расстояние бесконечно, и мы не знаем, какой путь к ним является кратчайшим.
ГРАФЫ 53
A
0/−
B
C
D
E
F
3 1
3 4
6 2
5 1
2
Мы берем узел с кратчайшим расстоянием от A (о котором нам известно).
Это сам узел A. Он текущий, поэтому выделим его серым.
A
0/−
B
C
D
E
F
3 1
3 4
6 2
5 1
2
Дальше мы можем проверить оценочное расстояние от узла A к его сосе- дям, B и C. Изначально мы сделали их бесконечно удаленными, но теперь ока- зывается, что путь к B равен 3, а к C — 1. Обновим наши оценки и выразим их через A: укажем 3/A над B и 1/A под C. К узлу A мы больше не вернемся. Обно- вим нашу диаграмму соответствующим образом, выделив A черным цветом.
Перейдем к узлу с лучшей оценкой, который еще не посещался, то есть к C.
54 ГЛАВА 2 0/−
B
3/A
C
1/A
D
E
F
3 1
3 4
6 2
5 1
2
Находясь в узле C, проверяем оценки кратчайших путей к его соседям,
D и E. Обе они бесконечные, но теперь мы видим, к каждому из этих узлов можно добраться через C. Путь от A до D через C имеет общую длину 5, по- этому записываем 5/C над D. Общая длина пути от A к E через C равна 3, по- этому указываем 3/C под E. С узлом C мы закончили, поэтому выделяем его черным и переходим к еще не посещенному узлу с лучшей текущей оценкой.
Оценки узлов B и E одинаково хороши — 3. Мы можем выбрать любой из них.
Пусть это будет B.
A
0/0
B
3/A
C
1/A
D
5/C
E
3/C
F
3 1
3 4
6 2
5 1
2
Продолжаем в том же духе. Находясь в узле B, проверяем оценки крат- чайших путей к его соседям, D и F. Мы уже знаем, что путь к D из C равен 5; это лучше, чем если бы мы начинали из B (6). Поэтому оценка удаленности
D остается без изменений. Путь к F сейчас считается бесконечно длинным,
ГРАФЫ 55
поэтому мы обновляем эту оценку до 9. Помечаем узел B как посещенный и переходим к узлу с лучшей оценкой, который мы еще не проверяли, то есть к E.
0/0 3/A
1/A
D
5/C
E
3/C
F
9/B
3 1
3 4
6 2
5 1
2
E соседствует с F. Путь к F из E имеет длину 8; это лучше, чем путь, про- легающий через B. Обновим нашу оценку, пометим узел E как посещенный и перейдем к следующему узлу с лучшей оценкой, который мы еще не посе- щали, то есть к D.
A
0/0
B
3/A
C
1/A
D
5/C
E
3/C
F
8/E
3 1
3 4
6 2
5 1
2
D соседствует с узлом F, к которому, как мы обнаружили, можно добраться через E по пути длиной 8. Путь к F через D равен 6, поэтому мы обновляем нашу предыдущую оценку. Как и прежде, переходим к узлу с лучшей оценкой, который мы еще не проверяли, то есть к F.
56 ГЛАВА 2 0/0 3/A
1/A
5/C
3/C
F
6/D
3 1
3 4
6 2
5 1
2
Находясь в узле F, проверяем, нужно ли обновить оценку для его соседа, E.
Текущий путь к E имеет длину 3, тогда как путь через F равен 10. Оставляем E без исправлений. Посещение F ничего не изменило, но мы не могли знать это заранее. Мы посетили все узлы, поэтому алгоритм завершается.
0/0 3/A
1/A
5/C
3/C
6/D
3 1
3 4
6 2
5 1
2
Выполняя алгоритм, мы записывали длину путей и предшественника каждого узла. Мы делали это для того, чтобы по окончании алгоритма можно было найти кратчайший путь из A в любой другой узел графа; например, если взять F, мы начинаем с конца и двигаемся в начало. Узнаем предыдущий узел:
D. Потом узнаем предшественника D, C, затем предшественника C, A. Крат- чайший путь из A в F выглядит как A, C, D, F и имеет общую длину 6; мы уже упоминали об этом в начале нашего обсуждения.
В конце алгоритм Дейкстры нашел все кратчайшие пути из начального узла графа во все остальные. Он эффективен, так как его сложность равна
O((m + n)logn), где m — количество ребер в графе, а n — количество узлов.
Вот из каких шагов он состоит:
ГРАФЫ 57 1. Назначить бесконечное расстояние всем узлам, кроме начального; на- значить начальному узлу нулевое расстояние.
2. Найти узел на минимальном расстоянии, который еще не посещали.
Это будет наш текущий узел. Если все узлы уже посещались, останав- ливаемся.
3. Проверяем всех соседей текущего узла. Если расстояние к соседу больше того, которое получилось бы при прохождении к нему через текущий узел, мы уменьшаем расстояние и обновляем путь, ведущий к соседу.
Переходим к шагу 2.
Если нас интересует кратчайший путь только к одному конкретному узлу, мы можем остановиться после того, как этот узел будет выбран для посеще- ния в шаге 2. На этом этапе мы уже знаем кратчайший путь к этому узлу, и он не поменяется в ходе дальнейшей работы алгоритма.
Алгоритм Дейкстры можно использовать в любом графе, независимо от того, направленный он или нет, даже если в нем есть циклы; главное, чтобы у него не было отрицательных весов. Это может произойти, если ребра между узлами представляют какого-то рода награды и штрафы. Хорошая новость в том, что для работы с отрицательными весами есть другие эффективные алгоритмы, но это подчеркивает, что у алгоритма может быть ограниченное применение. При подборе алгоритма для решения задачи необходимо убе- диться в том, что наша задача удовлетворяет его требованиям. В противном случае он не будет работать; но имейте в виду, что сам алгоритм не может со- общить о том, что он не подходит. Если мы реализуем его на компьютере, он будет выполнять свои шаги, даже если в этом нет никакого смысла. Это даст бредовый результат. Мы сами должны заботиться о выборе подходящих ин- струментов для наших задач.
Давайте возьмем крайний случай: граф, у которого есть не только отри- цательные веса, но и цикл с отрицательной суммой ребер (отрицательный цикл). У такого графа нет алгоритма для поиска кратчайших путей, по- скольку их не существует. Если у нас есть отрицательный цикл, мы можем проходить по его ребрам раз за разом, и на каждой итерации длина пути бу- дет уменьшаться. Это может продолжаться сколько угодно, и путь вдоль этого цикла получится бесконечно отрицательным.
При подборе алгоритма для решения задачи необходимо убедиться в том, что наша за- дача удовлетворяет его требо- ваниям. В противном случае он не будет работать; но сам он не может об этом сооб- щить. Среди программистов и специалистов в компьютер- ных науках бессмысленные программы принято называть
«мусор на входе — мусор на выходе». Люди должны сами выявлять такой мусор и понимать, что и в каких си- туациях использовать. Это яв- ляется важной частью университетских курсов по алгоритмам.
ПОИСК 59
ГЛАВА 3
ПОИСК
Тот факт, что алгоритмы могут делать все, что угодно, от перевода текста до вождения автомобиля, создает обманчивое впечатление о том, для чего их в основном применяют. Реальность оказывается прозаичной. Сложно найти компьютерную программу, которая делает что-либо полезное без использо- вания алгоритмов поиска по данным.
Это вызвано тем, что поиск в том или ином виде присутствует почти в лю- бом контексте. Программе, принимающей данные, зачастую нужно что-то в них найти, и для этого почти наверняка используется поисковый алгоритм.
Поиск — это не только очень распространенная, но и трудоемкая операция, которую необходимо выполнять постоянно. Хороший поисковый алгоритм может кардинально повысить скорость работы программы.
Поиск подразумевает выбор определенного элемента из группы элемен- тов. Это общее определение включает в себя несколько разновидностей по- иска. Большую роль играет то, упорядочены ли элементы, по которым мы ищем. Совсем другая ситуация возникает, когда мы получаем элементы один за другим и должны сразу же распознать тот, который ищем, без возможно- сти пересмотреть наше решение. Если мы неоднократно выполняем поиск по множеству элементов, важно знать, являются ли какие-либо из них по- пулярнее других. Мы исследуем все эти разновидности поиска в данной главе, но имейте в виду, что существуют и другие. Например, мы будем рассматри- вать только задачи с точным поиском, но во многих приложениях требуется
приблизительный поиск. Возьмем, к примеру, проверку орфографии: когда вы делаете опечатку, программа должна найти слова, похожие на те, которые ей не удалось распознать.
По мере увеличения объемов данных все важнее становится возмож- ность эффективного поиска по огромному количеству элементов. Вы уви- дите, что поиск масштабируется чрезвычайно хорошо, если наши элементы упорядочены. В главе 1 мы утверждали, что найти что-то среди миллиарда
Поиск в том или ином виде присутствует почти в любом контексте… Хороший поисковый алгоритм может кардинально повысить скорость работы программы.
ПОИСК 61
отсортированных элементов можно примерно за 30 шагов; теперь же мы по- кажем, как этого добиться.
Эта глава даст нам представление об опасностях, которые поджидают нас при реализации алгоритма в виде компьютерной программы, рассчитанной на работу в рамках определенного устройства.
1 2 3 4 5 6 7 8 9 ... 14
Иголка в стоге сена
Простейший пример поиска — это попытка найти иголку в стоге сена из из- вестной пословицы. Если мы хотим найти что-то в группе объектов, которые никак не структурированы, нам остается только проверить их один за другим, пока не будет найдено то, что мы ищем, или пока закончатся все элементы.
Если вы ищете определенную игральную карту в колоде, вы можете на- чать сверху и двигаться вниз, пока вам не попадется нужная карта или пока колода не исчерпается. Вы также можете продвигаться снизу вверх или вы- тягивать карты из колоды случайным образом. Это ничего принципиально не изменит.
При работе с компьютерами мы обычно имеем дело не с физическими объектами, а с их цифровым представлением. Набор данных на компьютере часто представляют в виде списка. Список — это структура данных, содержа- щая группу элементов, которые следуют один за другим. Обычно считается, что элементы в списке связаны, то есть каждый элемент указывает на сле- дующий, и так до самого конца; последний элемент указывает в никуда. Эта метафора недалека от реальности, поскольку для хранения элементов ком- пьютер использует адреса памяти. В связном списке каждый элемент содер- жит две вещи: собственно данные и адрес следующего элемента. Участок памяти, который хранит адрес другого участка, называется указателем. По- этому в связном списке каждый элемент содержит указатель на следующий элемент. Начальный элемент списка называется головным. Элементы списка иногда называют узлами. Последний узел никуда не указывает (или указы- вает на null: ничто в компьютерной терминологии).
Список — это последовательность элементов, но он не всегда упорядочен по какому-то определенному критерию. Например, следующий список содер- жит несколько букв из алфавита:
U
R
L
A
E
K
D
62 ГЛАВА 3
Если список неупорядоченный, поиск элемента в нем будет проходить так.
1. Переходим к головному элементу списка.
2. Если это искомый элемент, сообщаем о его нахождении и останавли- ваемся.
3. Переходим к следующему элементу списка.
4. Если мы перешли в null, сообщает о том, что искомый элемент не най- ден, и останавливаемся. В противном случае повторяем шаг 2.
Это называется линейным, или последовательным, поиском. В нем нет ни- чего особенного; это реализация простого перебора элементов, который про- исходит до тех пор, пока мы не найдем то, что нам нужно. В реальности алго- ритм заставляет компьютер переходить от одного указателя к другому, пока не будет обнаружен искомый элемент или null. Ниже показано, как происхо- дит поиск букв E и X.
U
R
L
A
E
K
D
U
R
L
A
E
K
D
Если искать среди n элементов, лучшее, что может случиться, — это ко- гда нам сразу же попадется искомый элемент (то есть если он является голов- ным). В худшем случае он находится в самом конце или вообще отсутствует в списке. В таком сценарии придется перебрать все n элементов. Таким обра- зом производительность последовательного поиска равна O(n).
С этим ничего нельзя поделать, если элементы собраны в случайную по- следовательность. Это видно на примере колоды карт: если она как следует перетасована, мы не можем заранее знать, где именно находится та или иная карта.
Иногда это создает проблемы в реальной жизни. Если нам нужно найти что-то конкретное в большой кипе бумаг, этот процесс может оказаться уто- мительным. Мы даже можем подумать, что из-за нашей невезучести искомый документ находится в самом низу. Поэтому мы прекращаем последователь- ный перебор и начинаем искать снизу. В этом нет ничего плохого, но не сле- дует надеяться на то, что это как-то улучшит наши шансы и поможет быстрее завершить поиск. Если кипа бумаг никак не упорядочена, искомый документ может находиться где угодно: в начале, в конце или ровно посередине. Все