Елена Филиппова
дата публикации 01-10-1999 00:00 Алгоритмы поиска. Введение
Данная статья не претендует на полное описание всех существующих методов поиска и
посвящена именно обзору классических решений, довольно простой на вид, поисковой задачи.
Мне хотелось рассказать об алгоритмах поиска, о том что это такое и каким образом их следует применять в конкретных задачах.
Я постаралась минимизировать количество математических выкладок и сухих определений, чтобы облегчить восприятие именно логики алгоритмов, не требуя при этом специальной математической подготовки.
Говоря о поиске, мы будем иметь в виду некий массив данных, а искать будем определенный элемент в этом массиве.
Оптимальность поиска для простоты определим очень конкретно - это
скорость работы алгоритма.
Казалось бы, к чему плодить много алгоритмов, давайте найдем один, самый оптимальный и
успокоимся на этом. Это ошибочное мнение. Найти оптимальный алгоритм, не привязываясь при его выборе к
условию задачи - это иллюзия.
Какой алгоритм , из множества известных сейчас, самый быстрый?
Ответа на этот вопрос не существует.
Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи,
которую нам придется решать. Именно на этот факт мне и хотелось бы обратить особенное внимание.
Маленькое лирическое отступление...
Судя по литературе, подъем интереса к математическим исследованиям
методов поиска начался в 60-х годах. Очевидно, что на заре развития вычислительной
техники, небольшой ( по нашим меркам просто никакой ) объем оперативной памяти и наличие
только внешних устройств последовательного доступа (магнитная лента), делало
задачу поиска или слишком тривиальной или абсолютно нерешаемой.
Общая классификация алгоритмов поиска
Подробное рассмотрение алгоритмов
Попытаемся решить простейшую задачу - найти нужное значение в массиве. На этом первом примере
мне хочется показать, как оптимальность решения зависит от того, в каком массиве мы будем искать.
Перед Вами колода игральных карт, в ней , как правило, 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 элементами
достаточно один раз из четырех задавать сверхэкстремальное значение для поиска, чтобы модифицированный
алгоритм работал быстрее.
Вот, пожалуй, и все.
Историческая справка:
- Бинарный поиск впервые упомянут Джоном Мочли в 1946г.
- Экстраполяционный поиск предложен У.Петерсоном 1957.
- Фибоначчиев поиск изобретен Д.Фергюсоном в 1960.
Для тех, кто интересуется математической основой упомянутых методов:
- Д.Кнут "Искусство программирования для ЭВМ", 1978г, издательство "МИР", том 3 "Сортировка и поиск".
- Популярные лекции по математике, выпуск №6. 1969г. Издательство "Наука" Н.Н. Воробьев. "Числа Фибоначчи"
- Р.Альсведе, И.Вегенер "Задачи поиска" , 1982г, Издательство "Мир"
¹ Log(2)N - логарифм от N по основанию 2.
Специально для Королевства Delphi © 1999
[Поиск и сортировка]
 Обсуждение материала [ 01-07-2005 05:47 ] 12 сообщений |
