Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 12
Текст из файла (страница 12)
[МЯ8) Продолжая выполнять упр, 10, найдите оптимальное расположение для сцепленного поиска в случае, когда а(й,у) = ш)п(йн, и а„н, ~ ) и А < ат < - .. (Эта ситуация встречается, например, в двусвязном циклическом списке или в запоминающем устройстве с возможностью перемещения в обе стороны.) 21. (М28) Рассмотрим и-мерный куб с координатами вершин (а„..., а„), где и" = О или 1; две вершины называются соседка,мк„если они различаются только одной координатой. Предположим, что набор из 2" чисел хо < хв « " хт в должен быть сопосгавлеи 2" вершинам таким образом, чтобы минимизировать сумму 1 (х, — х1); сумма берется по всем 1 и 1, таким, что х; и х, сопоставлены соседним вершинам. Докажите, что этот минимум достигается тогда, когда для всяку хз сопоставлено вершине, координаты которой являются двоичным представлением числа 11 и 22.
(хр) Предположиид что в большом файле вам необходимо найти 1 000 блихсайших к данному ключу записей, т. е. записей, для которых функция расстояния в((КП К) принимает наименьшие значения. Какая структура данных будет самой подходящей для такого последовательного лонскау Пытайся до конца, сомнений прочь оскал, И. есе преодолев, найдешь тм, что искал*.
— РОБЕРТ ХЕРРИК (РОБЕРТ НЕЙЙ!СК), ищите и обрящете 15ееке апо йоде) (1бай) * Перевод Сеетлаиы Тригуб. 6.2. ПОИСК ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ В этом глздклк мы обсудим методы поиска, основанные на линейном упорядочении ключей [таком, как числовое или алфавитное). После сравнения данного аргумента К с ключом К; из таблицы поиск продолжается одним из трех путей, в зависимости от того, какое из условий — К ( К„К = К; нли К > К— истинно. Последовательные методы поиска, рассмотренные в разделе 6.1, по сути, имели только два варианта ветвления поиска — в зависимости от выполнения или не выполнения условия К = Кб при отказе от исключительно последовательного доступа к таблице можно организовать более эффективный поиск с использованием отношения порядка. и в которой мы имеем простой и быстрый доступ к ключу в любой заданной позиции.
После сравнения в такой таблице К и К, мы получим один из трех результатов: [В„В;~.м..., г4 исключаются нз рассмотрения[; [поиск завершен]; [Вм лз,..., л; исключаются из рассмотрения), еК < К; еК=К; еК>К; В каждом из них в процессе поиска достигается существенный прогресс — за исключением тех случаев, когда 1 близко к одному из концов таблицы (более корректно было бы сказать "к одному нз концов рассматриваемой части таблицы". — Прим. перев.). Таким образом, с помощью упорядочения можно построить эффективные алгоритмы поиска.
Бинарный поиск. Вероятно, первым методом, который приходит в голову, явлнетси следующий: сравнить К со средним ключом в таблице, в результате этого сравнения определить, в какой половине таблицы находится искомый ключ, и снова 6.2.1. Поиск в упорядоченной таблице Что вы станете делать, если вам вручат большой телефонный справочник н попросят найти владельца телефона 444-3522? Вряд ли вы сможете предложить чтото лучшее, чем метод последонательного поиска из раздела 6.1 [методы наподобие "позвонить н спросить, кто это" и "купить компакт-диск с телефонной базой данных службы '09'" не рассматриваются). Веда в том, что, хоти в справочнике и содержитси вся необходимая информация для поиска как по имени абонента, так и по его номеру, поиск по имени владельца гораздо проще именно благодаря упорядочению записей в телефонном справочнике.
Последовательный поиск в огромном файле— это почти всегда безумие и пустая трата времени, но если файл упорядочен, решить задачу намного проще. Вопросы сортировки рассматривались в главе о, а потому нам не сложно выбрать подходящий метод сортировки, упорядочить данные и тем самым существенно облегчить задачу поиска. Само собой, выполнить однократный поиск в некоторой таблице проще последовательным методом, безо всякой сортировки; однако, если необходим многократный поиск, затраты на сортировку окупятся очень быстро, Таким образом, в этом разделе мы рассмотрим методы, обеспечивающие эффективный поиск в таблице, в которой ключи удовлетворяют условию чича зеварввмм Успение завврвевив Рис.
3. Бинарный поиск. применить ту же процедуру к половине таблицы. Максимум за величину порядка 1я К сравнений мы найдем искомый ключ (либо установим, что его нет в таблице). Эта процедура известна как "логарифмический поиск" или "метод деления пополам" но чаще всего употребляется термин бпнарнмй поиск. Хотя основная идея бинарного поиска сравнительно проста, детали его реализации нетривиальны н много неплохих программистов ошибались прн первых попьпках написать соответствующую программу.
В одной из наиболее популярных форм реализации метода используются два указателя, 1 и и, которые указывают верхнюю н нижнюю границы поиска. Алгоритм В (Бннщ~нмй поиск (81пагу зеагсй)). Дана таблица записей Л~ Нз... Вл, ключи которых расположены в порядке возрастания: К~ < Кз < ° ° < К,ч; алгоритм используется для поиска в таблице заданного аргумента К, В1. (Инициализация.) Установить 1 <- 1, и <- Ф. В2.
(Получение средины.) (На зтом шаге мы знаем, что если К имеется в таблице, то справедливо условие К~ < К < К„. Более точное описание ситуации можно найти в приведенном ниже упр. Ц Если и < 1, алгоритм завершается неудачно; в противном случае следует установиты <- '1(1+ и)(2~, чтобы 1 соответствовало примерно средине рассматриваемой части таблицы.
В3. (Сравнение.] Если К < Кп перейти к шагу В4; если К > Кп перейти к шагу В5; если К = Ко алгоритм успешно завершается. В4. [Изменение и.) Установить и ь- 1 — 1 и перейти к шагу В2. В5. (Изменение Ц Установить 1 е- 1+ 1 и перейти к шагу В2. $ На рис, 3 приведена блок-схема алгоритма, а на рис. 4 показаны два случая проведения бинарного поиска: в первом разыскивается число 653, имеющееся в таблице, а во втором — число 400, отсутствующее в таблице. Скобки показывают положение указателей 1 и н, а подчеркнутое число — Кь В обоих случаях поиск завершается после выполнения четырех сравнений.
а) Поиск 653: [061 087 154 170 061 087 154 170 061 087 154 170 061 087 154 170 275 426 503 Ы9 $!2 612 653 677 703 765 897 908) 275 426 $03 509[512 612 653 677 703 765 897 908) 275 426 503 509[512 612 653) 677 703 765 897 908 275 426 $03 509 $12 612[655] 677 703 765 897 908 Ь) Поиск 400: [061 087 154 170 275 426 503 $09 512 612 653 677 703 76Ь 897 908] [061 087 154 170 27$ 426 503] 509 512 612 653 677 703 765 897 908 061 087 154 170(275 426 503) $09 512 612 6$3 677 703 765 897 908 061 087 1$4 170[275] 426 503 509 512 612 653 677 703 76$ 897 908 061 087 154 170 27$][426 503 509 $12 612 6$3 677 703 765 897 908 Рис. 4. Примеры бинарного пояска.
Программа В (Бинарный поиск). Как н в программах нз раздела 6.1, полагаем, что К; представляет собой полное слово, находящееся по адресу КЕУ+ А В приведенном коде гП ьл 1, г12 №$ и, г13 аз ь О1 ВТАЩЕТ ЕМТ1 1 1 Я~8~!. ,№ №~~щ, ~ 1. 08 ЕМТ2 М 1 и+-А! 03 $МР 2Р 1 Переход к влагу В2. 04 бй ЮЕ БУССЕББ С1 Переход, если К = К..
0$ ЕМТ1 1,3 СЬ вЂ” Ы В,И~№~З ~ ° Ц Об 2Н ЕМТА 0,1 С+ 1 — Я В2. Пол челне с нны. 07 1МСА 0,2 С+1 — Я гА <-!+и. Об БВВ 1 С + 1 — Я гА +- (гА/2). (Изменяется также гХ.) 09 БТА ТЕМР С + 1 — Б 10 СМР1 ТЕМР С+ 1 — Я 11 30 ГАНЛВЕ С+ 1 — Я Переход, если и < 1. 18 ЖЗ ТЕМР С 1+- гагбро!ак 13 ЗН ЬВА К с вз. с№ Ц СИРА КЕТ,З С 15 ЮОЕ ЬВ С 1б ВМТ2 -1,3 С2 17 ЛМР 2В С2 Переход, олн К > Кь В4. Изменение н, и+-1 — 1 Переход к шву В2.
5 Представление в виде дерева. Для лучшего понимания работы алгоритма В представим описанную процедуру в виде бинарного дерева принятия решения, как показано на рис. 5, при А' = 16. Эта процедура ие вполне удачно реализуется на компьютере М1Х в связи с небогатой арифметикой индексных регистров. Время работы составляет (18С- 108+ 12) и, где С = С1+ С2 — количество произведенных сравнений (колнчество выполнений шага ВЗ) и 5 = 1 при успешном (или 0 при неудачном) исходе поиска.
Обратите внимание, что операция в строке 08 — БВВ (з)МВ г(881 Ыпагу 1 — побитовый сдвиг вправо на единицу) — допустима лишь в бинарных версиях М1Х; в общем случае ее следует изменить иа МУЬ 1//2+1, что приведет к увеличению времени работы программы до (26С вЂ” 185 + 20) и. Рис. а. Дерево сравнений, соответствующее бинарному поиску,дла Х = 16. При Ф = 16 сначала согласно алгоритму сравниваются К и Ке; на рисунке вто показано корневым узлом Са).
Затем, если К < Ке, алгоритм переходит в левое поддерево и сравниваются К с К», точно так же при К > Кв будет выполняться работа с правым поддеревом, Неудачный поиск приведет в один из внешних "квадратных" узлов, пронумерованных от Н ) до Я, например узел ) е) )будет достигнут нами только при Ке < К < Кт. Бинарное дерево, соответствующее бинарному поиску по Х записям, может быть построено следующим образом: если Р1 = О, дерево представляет собой просто один узел (о). В противном случае корневой узел— При атом левое поддерево представляет собой бинарное дерево с ~Ф/2) — 1 узлами, а правое — с ~Х/2) узлами 1все числа в узлах увеличеяы иа,'Ю/2)), Точно так в виде бинарного дерева с Х узлами, в котором все узлы пронумерованы от 1 до Х, может быть предсшвлеи любой алгоритм поиска в упорядоченной таблице длиной )т' 1если только алгоритм не выполняя г излишние сравнения).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
