Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

ПОИСК 63
позиции равновероятны, поэтому продвижение сверху вниз ничем не хуже любой другой стратегии (при условии, что каждый элемент проверяется ровно один раз). Тем не менее выбор определенного порядка помогает от- слеживать уже выполненные действия, поэтому мы предпочитаем придержи- ваться последовательного поиска.
Но все это верно только в том случае, если у нас нет причин полагать, что искомый элемент находится в какой-то определенной позиции. Если ж такие причины есть, мы можем воспользоваться любой дополнительной информа- цией для ускорения поиска.
Эффект Матфея и поиск
Вы, наверное, замечали, что на плохо организованном рабочем столе некото- рые вещи «всплывают» наверх, а другие оказываются в самом низу. Автор был приятно удивлен, когда в процессе наведения порядка обнаружил вещи, кото- рые считал давно утерянными. Это, наверное, случалось со всеми. Мы обычно держим ближе к себе вещи, которые часто используем, а то, что используется редко, постепенно пропадает из нашего поля зрения.
Представьте, что у вас есть кипа документов, над которыми вам нужно работать. Эти документы никак не упорядочены. Когда мы заканчиваем ра- боту с документом, мы кладем его не туда, где он был найден, а наверх. И это повторяется раз за разом.
Может случиться так, что некоторые документы нам требуются чаще дру- гих. К некоторым из них мы можем возвращаться снова и снова, а к другим — лишь изредка. Если продолжить откладывать документы, с которыми мы уже поработали, наверх, через некоторое время обнаружится, что самые популяр- ные из них находятся сверху, а те, которые требуются нам реже всего, оказа- лись где-то внизу. Это удобно, поскольку часто используемые документы все- гда под рукой, что экономит время.
Вырисовывается общая стратегия поиска, согласно которой одни и те же элементы ищутся многократно, и некоторые из них более востребованы, чем другие. Найдя нужный документ, мы откладываем его наверх, чтобы в сле- дующий раз его было проще искать.
Насколько практичной была бы такая стратегия? Это зависит от того, на- сколько часто наблюдаются подобные расхождения в популярности элемен- тов. В реальности это случается повсеместно. Вы, наверное, слышали посло- вицу: «Богатый богатеет, а бедный беднеет». Она касается не только богатых

64 ГЛАВА 3
и бедных людей. Эта тенденция встречается в удивительно большом количе- стве ситуаций в разных сферах деятельности. У нее даже есть название, эф-
фект Матфея, данное в честь следующей цитаты из Евангелия от Матфея
(25:29): «…ибо всякому имеющему дастся и приумножится, а у неимеющего отнимется и то, что имеет».
В этом стихе речь идет о материальных благах, поэтому давайте задума- емся на минуту о богатстве. Представьте, что у вас есть большой стадион, спо- собный вместить 80 000 человек. Вы можете измерить средний рост посети- теля стадиона. Пусть это будет около 1,7 метра. Представьте, что вы выбрали случайного болельщика и посадили на его место самого высокого человека в мире. Изменится ли средний рост? Даже если найти трехметрового гиганта
(такой рост никогда не был зафиксирован), средний рост останется практи- чески неизменным — разница с предыдущим показателем составит десятые доли миллиметра.
Теперь представьте, что вместо среднего роста мы замеряем среднее бла- госостояние. Допустим, для наших 80 000 человек это будет $1 миллион (к нам на стадион ходит небедная публика). Теперь опять посадим на место случай- ного посетителя самого богатого человека в мире, владеющего $100 милли- ардами. Имело ли бы это какое-то влияние? Да, и существенное. Средний показатель вырос бы с $1 миллиона до $2 249 987,5 — более чем в два раза.
Мы знаем, что богатство распределено неравномерно, но такая разница все равно может удивить. Она намного превышает расхождения естественных величин, таких как рост.
То же самое можно наблюдать во многих других сферах жизни. Есть мно- жество актеров, о которых вы никогда не слышали. А есть горстка звезд, ко- торые постоянно снимаются в фильмах и зарабатывают миллионы долларов.
Термин «эффект Матфея» в 1968 году предложил социолог Роберт Мертон, ко- торый заметил, что известные ученые получают большее признание за свою работу, чем их менее популярные коллеги, даже если делают аналогичный вклад. Чем известнее ученый, тем больше внимания он получает.
По тому же принципу распределяются слова в языке: некоторые из них используются куда чаще других. Такое очевидное неравенство присуще раз- мерам городов (мегаполисы намного больше среднего города) и количеству/
популярности веб-сайтов (на большинство сайтов заходят лишь время от вре- мени, а у некоторых есть миллионы посетителей). За последние несколько лет распространенность таких неравномерных распределений, когда небольшая часть населения владеет непропорционально большим объемом ресурсов,

ПОИСК 65
стала предметом обширных исследований. Ученые пытаются найти причины и законы, которые лежат в основе этого явления.
Возможно, элементам, по которым мы ищем, тоже присуща подобная раз- ница в популярности. Если это так, то поисковый алгоритм, пользующийся этим, может работать по тому же принципу, который мы описывали ранее: каждый найденный документ ложится сверху.
1. Ищем элемент последовательным способом.
2. Если элемент найден, сообщаем о его нахождении, помещаем его в на- чало списка (делаем головным) и останавливаемся.
3. В противном случае сообщаем о том, что элемент не найден, и останав- ливаемся.
На следующей диаграмме найденный элемент E переносится в начало списка.
U
R
L
A
E
K
D
E
U
R
L
A
K
D
Потенциальный недостаток этого алгоритма в том, что в начало списка станут попадать даже те элементы, которые редко ищутся. Это правда, но, если элемент не популярный, он постепенно будет вытеснен ближе к концу при поиске других элементов. Тем не менее мы можем принять определенные меры и сделать нашу стратегию не такой кардинальной. Найденный элемент можно переносить не в самое начало, а лишь на одну позицию вперед. Этот подход называется методом перегруппировки.
1. Ищем элемент последовательным способом.
2. Если элемент найден, сообщаем о его нахождении, меняем его местами с предыдущим (если он не первый) и останавливаемся.
3. В противном случае сообщаем о том, что элемент не найден, и останав- ливаемся.
Таким образом популярные элементы постепенно перейдут в начало списка, а остальные окажутся ближе к концу, без внезапных скачков.

66 ГЛАВА 3
U
R
L
A
E
K
D
U
R
L
E
A
K
D
Перемещение в начало и метод перегруппировки являются разновидно- стями самоорганизующегося поиска; этот термин выбран потому, что список организуется по мере выполнения операций поиска и отражает популяр- ность его элементов. Экономия времени зависит от того, насколько сильно варьируется эта популярность. Если от последовательного поиска можно ожидать производительности вида O(n), то самоорганизующийся поиск с перемещением в начало может демонстрировать скорость порядка O(n/
lgn). Если у нас есть миллион элементов, это позволит обработать их так же быстро, как если бы их было около 50 000. Метод перегруппировки может давать еще лучшие результаты, но для их достижения ему нужно больше времени. Это обусловлено тем, что оба метода требуют «прогрева», в тече- ние которого выявляются популярные элементы. В алгоритмах с переме- щением в начало этот период короткий; при использовании метода пере- группировки прогрев занимает больше времени, но зато потом получаются лучшие результаты.
Кеплер, автомобили и невесты
В 1611 году прославленный астроном Иоганн Кеплер (1571–1630) овдовел — его жена умерла от холеры. Он решил жениться повторно, но, будучи мето- дическим человеком, не захотел полагаться на волю случая. Свой подход он описал в письме барону Страхлендорфу. Прежде чем делать выбор, Кеплер планировал провести собеседования с 11 потенциальными невестами. Ему очень понравилась кандидатура под номером пять, но друзья его переубе- дили, указав на ее низкое положение в обществе. Вместо нее они посовето- вали еще раз присмотреться к четвертой кандидатке, но она ему отказала.
В итоге после знакомства со всеми 11 претендентками, Кеплер все же же- нился на пятой, 24-летней Сюзанне Рюттингер.
Эта небольшая история является немного притянутым за уши приме- ром поиска; Кеплер искал идеальную пару среди потенциальных кандида- тур. Но у этого процесса была одна особенность, которую он мог сначала

ПОИСК 67
не заметить: у нас не всегда есть возможность вернутся к варианту, который мы уже отклонили.
Эту задачу можно переформулировать с учетом современных реалий.
Представьте, что мы ищем лучший способ определения того, какой автомо- биль следует покупать. Мы заранее составили список автосалонов, которые хотим посетить. Кроме того, наше самолюбие не позволит нам вернуться в са- лон, из которого мы уже вышли с пустыми руками. Отклонив предложение, мы обязательно должны сохранить лицо; мы не можем снова прийти в то же место и сказать, что мы передумали. Так или иначе, в каждом автосалоне придется принимать окончательное решение: либо покупать, либо никогда больше не возвращаться.
Это разновидность задачи оптимальной остановки. Мы должны принять решение, пытаясь максимизировать награду или минимизировать расходы.
В нашем примере нам нужно выбрать лучший автомобиль, который только можно купить. Если принять решение слишком рано, может оказаться, что впереди нас ждал более оптимальный вариант. А запоздавшее решение мо- жет означать, что мы уже видели лучший автомобиль, но не решились его ку- пить. Так когда следует остановиться и сделать покупку?
Более формальное описание этой проблемы называется задачей о секре-
таре (или о разборчивой невесте). Мы хотим выбрать секретаря из группы кандидатов. Вы можете по очереди проводить собеседования с каждым кан- дидатом. В конце каждого собеседования необходимо принять решение: на- нимать или нет. Если кандидат отклонен, вы уже не сможете к нему вернуться
(его может перехватить кто-то другой, так как он слишком хорош). Как же сделать правильный выбор?
Ответ на удивление прост. Мы интервьюируем первые 37% кандидатов, отклоняем их всех, но отмечаем для себя лучшего из них. Число 37 может показаться случайным, но это результат деления 1 / e ≈ 37%, где e — это по- стоянная Эйлера, которая равна примерно 2,7182 (мы уже упоминали о ней в главе 1). Затем мы встречаемся с остальными кандидатами и останавли- ваем свой выбор на том, который лучше отмеченного нами ранее. Запишем это в виде алгоритма для n кандидатов.
1. Вычисляем n / e, чтобы получить 37% от n кандидатов.
2. Проверяем и отклоняем первые n / e кандидатов. Выбираем лучшего из них в качестве эталона.
3. Проверяем остальных кандидатов. Выбираем того, который оказыва- ется лучше эталона, и останавливаемся.

68 ГЛАВА 3
Этот алгоритм не всегда находит лучшего кандидата; в конце концов, это может быть тот самый эталон, который выбран среди первых 37% и за- тем отклонен. Но мы можем доказать, что он выбирает лучшего кандидата в 37% случаев (опять же, 1 / e); более того, не существует другого алгоритма, который способен превзойти этот показатель. Иными словами, это лучший алгоритм из всех имеющихся: он может не дать оптимального результата в 63% случаев, но любая другая стратегия будет проваливаться еще чаще.
Возвращаясь к автомобилям, представим, что мы составили список из 10 автосалонов. Мы должны посетить первые четыре и найти лучшее пред- ложение, не делая покупку. Затем мы начинаем посещать другие шесть авто- салонов и принимаем то предложение, которое превзойдет отмеченное нами ранее (остальные отклоняем). Возможно, ни один из шести салонов не сде- лает лучшего предложения. Но никакая другая стратегия не даст более высо- ких шансов на оптимальную покупку.
Нам нужен был лучший кандидат из возможных, и мы не хотели согла- шаться на меньшее. Но что, если эти высокие требования можно немного за- низить? Конечно, в идеале мы хотели бы сделать лучший выбор, будь то се- кретарь или автомобиль, но нас может удовлетворить и другой вариант (хотя и не так сильно). Если поставить вопрос таким образом, то поиск лучше про- водить с помощью того же алгоритма, но вместо 37% взять и отклонить
n
кандидатов. В этом случае вероятность принятия оптимального решения ра- стет вместе с количеством кандидатов, n, стремясь к 1 (то есть к 100%).
Мы рассмотрели разные способы выполнения поиска, рассчитанные на разные сценарии. Общим во всех этих примерах было то, что перебирае- мые нами элементы не находятся в каком-то определенном порядке; в лучшем случае мы постепенно упорядочиваем их по популярности (самоорганизую- щийся поиск). Совсем другое дело, когда элементы изначально упорядочены.
Представьте, что у нас есть стопка папок, каждой из которых присвоен от- дельный номер. Документы в стопке упорядочены согласно этим номерам, по их возрастанию (номера могут не быть последовательными). Если нам нужно найти документ с определенным номером, было бы глупо начинать с начала и просто двигаться в конец. Намного лучше перейти сразу в середину и сравнить иденти- фикатор документа с искомым номером. Здесь может произойти одно из трех.
1. Если нам повезет, мы попадем сразу на нужный нам документ. В этом случае мы закончили, поиск останавливается.
2. Номер искомого документа превышает номер, который нам попался.
Это означает, что мы можем отклонить как этот, так и все предыдущие

ПОИСК 69
документы. Они упорядочены, поэтому у всех у них будут меньшие но- мера. У нас получился «недолет».
3. Происходит противоположное: номер искомого документа меньше того, который нам попался. Мы можем спокойно отклонить как этот,
так и все последующие документы. Наша цель находится позади.
В двух последних случаях у нас остается стопка, которая как минимум вдвое меньше исходной. Если начать с нечетного количества докумен- тов (скажем, с n) и разделить их посередине, получится две равные части по n / 2 элемен тов в каждой (игнорируем дробную часть).
○ ○
○ ○
×
Если у нас четное количество элементов, в результате их разделения по- лучится две части: в одной n / 2–1, а в другой n / 2.
○
○ ○
×
Мы все еще не нашли то, что искали, но мы находимся в куда лучшей пози- ции, чем прежде; у нас осталось намного меньше элементов, которые нужно перебрать. Итак, продолжаем. Проверяем средний документ в оставшейся
стопке и повторяем ту же процедуру.
На диаграмме, показанной на следующей странице, можно видеть, как этот процесс работает в случае с 16 элементами, среди которых нужно найти элемент 135. Мы выделяем серым цветом рамки, в которых происходит по- иск, и средний элемент.
Вначале область поиска охватывает весь список. Мы переходим к сред- нему элементу и узнаем, что он имеет номер 384. Это больше, чем 135, по- этому мы отбрасываем его и все элементы справа от него. Берем средний эле- мент в оставшемся списке; он имеет номер 72. Это меньше, чем 135, поэтому мы отбрасываем его вместе со всеми элементами, которые находятся слева от него. Область поиска сократилась до всего лишь трех элементов. Мы бе- рем средний из них и обнаруживаем, что это тот, который нам нужен. На вы- полнение поиска ушло всего три шага, и нам даже не пришлось проверять
13 элементов из 16.
6 11 31 72 114 135 244 384 503 507 541 613 680 742 871 957 6
11 31 72 114 135 244 384 503 507 541 613 680 742 871 957 6
11 31 72 114 135 244 384 503 507 541 613 680 742 871 957

70 ГЛАВА 3
Этот процесс будет работать и в ситуации, когда искомого элемента не су- ществует. Это можно наблюдать на следующей диаграмме, где в том же списке ищется элемент 520.
6 11 31 72 114 135 244 384 503 507 541 613 680 742 871 957 6
11 31 72 114 135 244 384 503 507 541 613 680 742 871 957 6
11 31 72 114 135 244 384 503 507 541 613 680 742 871 957 6
11 31 72 114 135 244 384 503 507 541 613 680 742 871 957
×
На этот раз 520 больше, чем 384, поэтому мы ограничиваем область по- иска правой половиной списка. В ней посередине находится элемент 613, ко- торый больше, чем 520. У нас остается всего три элемента, средний из кото- рых 507. Он меньше 520. Мы его отбрасываем и проверяем оставшиеся два элемента, ни один из которых не имеет искомый номер. Мы можем завер- шить поиск, сообщив о том, что он оказался безрезультатным. Для этого по- требовалось всего четыре шага.
Описанный нами метод называется двоичным поиском, потому что на каж- дом этапе область поиска уменьшается вдвое. Этот принцип можно оформить в виде алгоритма, состоящего из следующих шагов.
1. Если область поиска пустая, нам нечего проверять, поэтому сообщаем о неудаче и останавливаемся. В противном случае находим средний элемент.
2. Если средний элемент меньше искомого, ограничиваем область поиска элементами, которые идут за ним, и возвращаемся к пункту 1.
3. В противном случае, если средний элемент больше искомого, ограни- чиваем область поиска элементами, которые идут перед ним, и возвра- щаемся к пункту 1.
4. Если средний элемент равен искомому, сообщаем об успехе и останав- ливаемся.
Таким образом мы сокращаем вдвое количество элементов, по которым нам нужно искать. Это метод типа «разделяй и властвуй». Он состоит в мно- гократном делении, которое, как мы видели в главе 1, дает нам логарифм.
Многократное деление на два — это логарифм по основанию 2. В худшем случае двоичный поиск продолжит разделять список элементов, пока ничего