Алгоритмы поиска

== Введение ==
Данная статья не претендует на полное описание всех существующих методов поиска и посвящена именно обзору классических решений, довольно простой на вид, поисковой задачи. Мне хотелось рассказать об алгоритмах поиска, о том что это такое и каким образом их следует применять в конкретных задачах. Я постаралась минимизировать количество математических выкладок и сухих определений, чтобы облегчить восприятие именно логики алгоритмов, не требуя при этом специальной математической подготовки.
Говоря о поиске, мы будем иметь в виду некий массив данных, а искать будем определенный элемент в этом массиве. Оптимальность поиска для простоты определим очень конкретно - это скорость работы алгоритма.
Казалось бы, к чему плодить много алгоритмов, давайте найдем один, самый оптимальный и успокоимся на этом. Это ошибочное мнение. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи - это иллюзия.
Какой алгоритм , из множества известных сейчас, самый быстрый?
Ответа на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи, которую нам придется решать. Именно на этот факт мне и хотелось бы обратить особенное внимание.
Маленькое лирическое отступление...
Судя по литературе, подъем интереса к математическим исследованиям методов поиска начался в 60-х годах. Очевидно, что на заре развития вычислительной техники, небольшой (по нашим меркам просто никакой) объем оперативной памяти и наличие только внешних устройств последовательного доступа (магнитная лента), делало задачу поиска или слишком тривиальной или абсолютно нерешаемой.
== Общая классификация алгоритмов поиска ==
* Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность.
Представьте себе, что Вы ищете слово в словаре. Как бы Вы его не искали, Ваш алгоритм обязательно будет статическим, так как сам словарь (массив слов) не будет изменяться во время поиска. Если конечно не выдирать из него страницы. Примером динамического поиска может служить попытка найти определенную карту в колоде. Откладывая в сторону ненужные карты, Вы облегчаете себе задачу поиска, уменьшая количества оставшихся карт в колоде, которые еще нужно перебрать, тем самым перестраивая массив значений во время поиска!
* Так же методы поиска можно разделить на методы, использующие истинные ключи и на методы, работающие по преобразованным ключам. В данном случае "ключом" называют то значение, которое мы ищем.
Поиск в колоде карт - поиск по истинным ключам, то есть имеете дело с тем, что есть. Поиск в словаре - поиск по преобразованным ключам, так как все слова отсортированы в алфавитном порядке, то есть массив значений изменен перед началом поиска. Этот порядок создан специально для облегчения поиска и вовсе не является естественным для списка слов!
Кстати, привычный нам алфавитный порядок слов, не всегда казался людям естественным и является изобретением не очень древним.
* Ну и еще вариант классификации - методы основанные на сравнении самих значений и методы, основанные на их цифровых свойствах. Так называемые методы хэширования.
Рассматриваемые в данном обзоре алгоритмы являются комбинациями первых двух способов классификации. О методе хэширования я лишь упомяну исключительно из академического интереса, так как он не входит в круг рассматриваемых здесь задач.
Представьте себе, что нам надо найти определенную карту в колоде. Для этого мы выбрали довольно нестандартный способ, мы придумали такую функцию, которая вычисляет номер нужной карты в колоде. 
Например
 f("крестовая дама") = 5
 f("туз пик") = 12
То есть, подставив в функцию искомое значение, мы получаем местоположение этого значения в нашем массиве. Вот здорово! Это же самый что ни на есть ПРЯМОЙ доступ , по сравнению с ПОСЛЕДОВАТЕЛЬНЫМ перебором всех (или некоторых) значений в искомом массиве.
Этот метод и называется методом хэширования. Все бы хорошо, но вот беда, функция f(К) должна определять ОДНОЗНАЧНОЕ соответствие для каждого значения в массиве, а находить подобные функции довольно сложно.
== Подробное рассмотрение алгоритмов ==
Попытаемся решить простейшую задачу - найти нужное значение в массиве. На этом первом примере мне хочется показать, как оптимальность решения зависит от того, в каком массиве мы будем искать.
Перед Вами колода игральных карт, в ней, как правило, 54 карты (ну или 36). Карты лежат в беспорядке. Необходимо найти определенную карту, например пикового короля. Что Вы предпримете? Думаю, что догадаться нетрудно, первое, что приходит в голову, это последовательно перебирать все карты, до тех пор пока нужная не найдется. При самом плохом стечении обстоятельств Вам придется перебрать все карты в колоде , что на самом деле не так долго, если честно.
Попробуем немного изменить условие. Искать нам надо не карту, а конверт с определенным адресом. Конвертов этих перед Вами лежит немеряное количество, если окинуть взглядом заваленные столы, ну несколько сотен как минимум. Нет, нет, не пожимайте удивленно плечами, задача не надуманная, а самая что ни на есть реальная. Если вдруг кто-нибудь (а мир так удивительно тесен!) знаком с Константиновым Николаем Николаевичем, тот скорее всего знаком с этой задачей не понаслышке. Итак, я отвлеклась, перед нами несколько сотен конвертов с именами, нужно найти вполне определенный конверт. Способ, только что опробованный на колоде карт, очень скоро утомит. Вряд ли кто в этом сомневается, не правда ли? :о)
А вот если предварительно все эти конверты разложить в алфавитном порядке, то дальнейшая работа по нахождению вполне определенного имени уже не представляется такой ужасной! Конечно, на сортировку необходимо затратить вполне определенные силы и время, но они окупятся при многоразовом поиске, вот что самое главное
Вспомнив пример с картами, отметим, что в том случае тратить время на предварительную сортировку колоды вряд ли стоит...
Итак, мы можем сделать первый и очень важный вывод - оптимальность метода поиска зависит от размера массива, в котором мы ищем! Прямой перебор всех значений прост в понимании, легок в исполнении и достаточно быстр на малых массивах данных. Насчет легкости и простоты , это не лирика, это весомый аргумент, ведь Вам после того, как будет выбран определенный метод, необходимо еще формализовать его и закодировать. В итоге программиста интересует код. Не будем об этом забывать.
Итак, все это в совокупности позволяет сказать, что метод прямого перебора оптимален для малых массивов.
Если же массив данных достаточно велик, то оптимальность поиска достигается предварительной сортировкой значений в массиве.
Ну что же, с задачей поиска при малом количестве значений мы разобрались, она достаточно тривиальна. Давайте займемся поиском в о-о-очень длинном массиве... Это гораздо интереснее. Итак, приняв все вышесказанное за истину, мы отсортировали наш массив. Все значения лежат в некотором порядке. Можно искать! И, собственно, что?... Как искать-то?
Существует несколько классических способов поиска значения в отсортированном массиве. Мы рассмотрим три способа. Они были предложены в 60-х годах и мало изменились в наше время. Один из них очень известный, ведь Вам наверняка приходилось слышать такие названия как "метод дихотомии", "бинарного дерева" или "метод половинного деления", что собственно одно и тоже. Вот с него и начнем.
== 1. Алгоритм поиска по бинарному дереву. ==
Суть этого алгоритма достаточно проста. Представим себе, что у нас есть набор карточек с телефонными номерами и адресами людей. Карточки отсортированы в порядке возрастания телефонных номеров. Необходимо найти адрес человека, если мы знаем, что его номер телефона 222-22-22. Наши действия? Берем карточку из середины пачки, номер карточки 444-44-44. Сравнивая его с искомым номером, мы видим, что наш меньше и , значит, находится точно в первой половине пачки. Смело откладываем вторую часть пачки в сторону, она нам не нужна, массив поиска мы сузили ровно в два раза. Теперь берем карточку из середины оставшейся пачки, на ней номер 123-45-67. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки... Таким образом , при каждом сравнении , мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.
Не буду приводить математического доказательства, так как это не является целью данной статьи, а просто отмечу, что скорость сходимости этого алгоритма пропорциональна Log(2)N ?. Это означает буквально то, что не более, чем через Log(2)N сравнений , мы либо найдем нужное значение, либо убедимся в его отсутствии.
Другое название этого алгоритма - «метод бинарного дерева» происходит из представления "пути" поиска в виде дерева (у которого каждая следующая ветвь разделяется на две, по одной из которых мы и движемся в дальнейшем)..
Способ очень распространенный в наше время, возможно по причине его эффективности вкупе с простотой программирования этого алгоритма. Именно бинарный поиск используется при поиске в индексах таблиц.
Есть еще один алгоритм, основанный на делении искомого массива на части, аналогичный предыдущему. Я упомяну о нем скорее из-за некоторой его экзотичности.
== 2. Поиск по "дереву Фибоначчи". ==
Рассмотрим его исключительно из академического интереса. Для тех, кто пожелает разобраться в методе более детально, список литературы в конце статьи.
Трудноватый для восприятия метод, но эффективность его немного выше, чем у поиска по Бинарному дереву, хотя так же пропорциональна Log(2)N.
В дереве Фибоначчи числа в дочерних узлах, отличаются от числа в родительском узле на одну и ту же величину, а именно на число Фибоначчи. Суть метода в том, что сравнивая наше искомое значение с очередным значением в массиве , мы не делим пополам новую зону поиска , как в бинарном поиске, а отступаем от предыдущего значения, с которым сравнивали, в нужную сторону на число Фибоначчи.
Почему этот способ считается более эффективным, чем предыдущий?
 
Ответ достаточно неожиданный и боюсь , что нам с Вами оценить его должным образом вряд ли удастся. Дело в том, что метод Фибоначчи включает в себя только такие арифметические операции, как сложение и вычитание, нет необходимости в делении на 2, тем самым экономится процессорное время!
Хочется напомнить, что речь идет о том времени, когда был изобретен метод, а именно - о 60-х годах. В то время процессорное время можно было экономить на подобных подходах.
== 3. Метод экстраполяций. ==
Переходя к следующему методу, давайте представим, что Вам срочно понадобилось узнать, как переводится на русский язык английское слово treasure. То есть перед нами задача - найти это слово в словаре.
По сути все наши дальнейшие действия будут ничем иным, как реализацией некоторого алгоритма поиска. Массив значений - это словарь, все значения в нем отсортированы по алфавиту. Искомое слово нам известно. Значит сейчас мы будем искать в отсортированном массиве.
Если честно, то я с трудом представляю себе, что Вы станете делить все страницы книги пополам, смотреть что там в середине и отлистывать в одну или другую сторону ровно ? страниц словаря и так далее... То есть метод дихотомии Вы проигнорируете. И уж совсем неожиданно предположить, что Вы воспользуетесь деревом Фибоначчи.
Вы просто возьмете и ... и найдете нужное слово, не правда ли? 
А теперь остановимся и еще раз повторим поиск , при этом очень внимательно проанализируем наши действия. Итак, искомое слово начинается на букву T , открываем словарь немного дальше, чем на середине. Нам попалась буква R, ясно , что искать надо во второй части словаря, а на сколько отступить? На половину? "Ну зачем же на половину, это больше, чем надо", скажете Вы и будете правы. Ведь нам не просто известно, в какой части массива искомое значение, мы владеем еще и информацией о том, насколько далеко надо шагнуть!
Вот мы и подошли к сути рассматриваемого метода. В отличии от первых двух , он не просто определяет зону нового поиска, но и оценивает величину нового шага.
Алгоритм носит название экстраполяционного метода и имеет скорость сходимости большую, чем первые два метода.
Примечание:
Если при поиске по бинарному дереву за каждый шаг массив поиска уменьшался с N значений до N/2 , то при этом методе за каждый шаг зона поиска уменьшается с N значений до корня квадратного из N. Если К лежит между Kn и Km , то следующий шаг делаем от n на величину
 (n - m)*(K - Kn)/(Km - Kn)
Скорость экстраполяционнго метода начинает существенно превышать скорость метода половинного деления при больших значениях N.
Итак, мы рассмотрели конкретные алгоритмы поиска в отсортированном массиве. Таким образом можно подвести итоги:
* Если необходимо искать в небольшом массиве и искать нужно нечасто, проще воспользоваться методом перебора всех значений массива; 
* Если массив значений большой и искать нужно часто, отсортируйте массив и воспользуйтесь методом половинного деления или интерполяционным методом.
Каким из них именно, выбирайте исходя из того, насколько велик массив и какой метод Вам самим легче реализовать в коде. При предложенном выборе возникает резонный вопрос , а "большой массив" это какой? При оценке времени, которое затрачивает алгорит на поиск имеют значение две величины. Во-первых, это размерность массива (количество элементов) и, во-вторых, это количество обращений (то есть, сколько раз нам нужно в нем искать).
Итак, имеем массив размерностью N и проводим М раз в нем поиск.
Количество операций, которые выполнит алгоритм прямого перебора, пропорционально M*N. Метод дихотомии совершит 2М*Log(2)N операции, да еще и время на сортировку надо прибавить - N*Log(2)N
Итак, имеем два выражения:
 T1 = M*N;
 T2 = 2М*Log(2)N + N*Log(2)N
При Т1 = Т2 мы находимся на границе, на которой одинаково оптимальны оба алгоритма. Из этого равенства можно получить области в системе координат "Количество обращений - Размерность массива", определяющие оптимальность одного алгоритма относительно другого (см. рисунок).
== Способы коррекции алгоритмов поиска. ==
Основным критерием выбора оптимального метода был размер массива, в котором мы ищем. А более конкретные условия задачи могут существенно повысить скорость уже выбранного метода.
До сих пор мы считали, что каждое значение массива с одинаковой вероятностью может оказаться искомым.
Но это утверждение не для всех задач верно.
Предположим, что у нас есть конверты с адресами учеников. Конвертов немного и сортировать мы их не стали. Ученики эти принимали участие в различных конкурсах и заняли там призовые места. Причем один человек мог отличиться не в одном , а во многих конкурсах. Перед нами задача: по спискам каждого конкурса найти отличившихся и вложить в его конверт соответствующее уведомление. Естественно, что уведомлений будет столько , сколько состязаний ученик выиграл. Через некоторое время, вкладывая очередное n-ое уведомление в конверт очередного юного гения и в глубине души догадываясь, что это не последний выигранный им конкурс, Вам вдруг захочется, чтобы его конверт лежал где-то в начале пачки.... И совершенно не важно, каким методом поиска Вы пользуетесь, Важно другое - исходя из условий конкретной задачи этот метод нуждается в коррекции.
Вот тут нам поможет довольно простая схема динамического метода коррекции поиска или метод "Самоорганизующегося" списка. Идея метода проста - когда мы находим нужный конверт, мы кладем его в начало пачки. То есть перемещаем значение в начало массива, помните перестраиваемый массив при динамическом поиске?
В итоге, часто используемые элементы будут расположены довольно близко к началу массива. Таким образом, количество сравнений до удачного поиска будет минимизироваться "само-собой". И через несколько иттераций в начале пачки автоматически окажутся конверты будущих ломоносовых.
Математически это можно объяснить так: предположим, что значение Ki будет разыскиваться с вероятностью Pi, причем
 P1 + P2 + ... Pn = 1
Время удачного поиска пропорционально С, среднее значение которого:
 С = P1 + 2*P2 + .... N*Pn.
Минимального значения С достигнет при :
 P1 > P2 > ... > Pn
То есть тогда, когда наиболее часто используемые записи находятся в НАЧАЛЕ таблицы.
Данный способ, естественно, стоит применять в случае наибольшей вероятности именно удачного поиска.
Не будем загромождать статью математическими выкладками, ибо тема несколько иная, но в результате оказывается, что оптимальное (с точки зрения частоты обращений) расположение значений экономит около трети поискового времени!
Возможно этот метод кому-то покажется экзотическим ( опять же, вероятности какие-то, это вам не Ctrl-C & Ctrl-V , ужас просто) , но, в зависимости от условия задачи, метод может быть очень эффективным.
Менее экзотический, но тоже сильно зависящий от конкретных условий задачи, динамический метод "очищаемого" списка. Это не самостоятельный метод поиска, а именно коррекция одного из методов описанных выше. Когда при удачном поиске значения, запись ему соответствующая, удаляется из массива, уменьшая такми образом его размерность.
И еще один момент. До сих пор мы считали, что в рассматриваемых задачах вероятность удачного поиска достаточно велика. Представим себе, что поиск поисходит в неком массиве, про который мы точно знаем, что искомые значения скорее всего там не содержатся!
Чем же нам это помогает? А вот чем: мы можем минимизировать количество сравнений, заранее отсекая неудачный поиск, то есть значения ,которых нет в массиве. Предположим, что у нас есть большой массив отсортированных значений. Достаточно перед началом поиска очередного значения проверить, а попадает ли оно в принципе в массив?
Это совершенно просто: если (Ki < K1) или (Ki > Kn), то, собственно говоря, чего суетиться-то? Но применять этот способ коррекции алгоритма можно только в том случае, если вероятность неудачного поиска достаточно велика. Потому как при большой размерности массива еще и прибавлять сравнение на каждом шаге можно только в том случае, если очередное сравнение СКОРЕЕ ВСЕГО заменит нам очередной виток поиска.
Оценим, какова должна быть вероятность неудачного поиска, то есть отсутствие искомого значения в массиве, чтобы было выгодно применять эту модификацию алгоритма. (Приведенная ниже оценка вероятности представлена Николаевым А.)
Пусть Р - вероятность того, что искомое значение отсутствует между минимальным и максимальным значением массива. Тогда мы, отсекая сверхэкстремальные значения, в среднем не производим Р*(С - 2) операций, где С - среднее число операций при проведении немодифицированного поиска. В то же время мы вынуждены впустую совершить 2*(1 - Р) операций для сравнения значения с минимальным и максимальным в массиве. Так как мы должны быть в выигрыше, то
 Р*(С - 2) > 2*(1 - Р)
следовательно
 PC -2P + 2P - 2 > 0
 РС > 2
ну и наконец:
 P > 2/C
Таким образом, при P > 2/C мы будем в выигрыше. Например, для поиска по бинарному дереву в случае массива с 32 элементами достаточно один раз из четырех задавать сверхэкстремальное значение для поиска, чтобы модифицированный алгоритм работал быстрее.
Author: Елена Филиппова
Source: http://delphiworld.narod.ru/
ID: 04261
Category:Алгоритмы
Category:Статьи