Калайда В.Т., Романенко В.В. Технология разработки программного обеспечения (2007) (1095890), страница 26
Текст из файла (страница 26)
Поиск нужного элемента в таблице является характерным примером такого алгоритма: проверить первый элемент; if заданный элемент не найден, then продолжить поиск среди оставшихся элементов.Таким образом, задача разбивается на две части: проверкупервого элемента и поиск среди оставшихся. Ясно, что такие169алгоритмы не равнозначны по сложности. Модифицированныйалгоритм — двоичный поиск — имеет вид: проверить первый элемент; if заданный элемент не найден, then продолжить поиск в верхней или нижней половине списка.В этом случае задача разбивается на две части, примерноодинаковые по сложности. Каждая из частей может иметь рекурсивное решение.7.3 Рекурсия и динамическое программирование7.3.1 РекурсияИногда возможно сформулировать решение задачи какизвестное преобразование другого, более простого, вариантатой же задачи.
Если этот процесс продолжить до тех пор, покане получится нужное значение, то подобное решение называется рекурсивным.Примером рекурсивного решения является вычислениефакториала fact(N) = 1×2×…×N. Пусть неизвестно значениеfact(460), если умножить fact(459) на 460, тогда задача сводится к вычислению fact(459). Если это преобразование далее повторить 458 раз, то можно вычислить значение факториала, поскольку fact(1) = 1. Таким образом, функция F является рекурсивной, если:1) F(N) = G(N, F(N – 1)) для некоторой известной функции G и2) F(1) равно некоторому известному значению.Функция F может быть функцией нескольких параметров.Значение N должно быть задано в явном виде.
Величина N может быть элементом во множестве, длиной интервала или некоторым другим параметром.Рекурсивное решение всегда записывается проще, чем соответствующий нерекурсивный вариант. Относительно скорости решения однозначных выводов сделать нельзя. Это зависитот сложности функции G.1707.3.2 Динамическое программированиеДинамическое программирование — это табличный метод, при котором используется одна и та же схема вычислениявсех подзадач данной задачи.
При использовании этого методаоднажды найденный результат записывается в таблицу и далееповторно не вычисляется.7.3.3 МоделированиеЧасто бывает невозможно получить точное решение задачи по соображениям стоимости, сложности или размера. Такиеситуации возникают при решении задач по управлению движением, экономическому прогнозированию и др. В этих случаяхстроится представление определенных свойств задачи, называемой моделью, а все другие свойства не учитываются.
При этомпроводится анализ поведения нужных свойств модели. Такойподход называется моделированием. Моделирование применяется во многих областях, однако при разработке программногообеспечения моделирование используется достаточно редко. Восновном моделирование используется при исследовании наЭВМ различных физических процессов, особенно когда известноматематическое описание последних. Тем не менее данный подход заслуживает пристального внимания программистов при разработке больших программных комплексов.7.4 ПоискПоиск — это процесс нахождения нужных значений в некотором множестве. Семейство элементов может быть структурированным либо нет. Если оно не структурировано, поиск обычноозначает нахождение нужного элемента в списке. Если семействоэлементов структурировано (дерево, граф и др.), то под поискомпонимают нахождение правильного пути в структуре.Обычно каждый элемент имеет три компонента: ключ — это элемент, используемый для доступа к данным (он может быть именем в справочнике, словом виндексе или названием раздела в таблице); аргумент — это числа, связанные с элементом (адрес,номер телефона и др.);171 структуру — это дополнительная информация, прини-маемая для описания данных, такая, как адрес следующего элемента в семействе и т.п.7.4.1 Поиск в спискахДанный поиск проводится четырьмя различными способами: прямым, линейным, двоичным и хешированием.Прямой поиск.
При прямом поиске местоположение элемента определяется непосредственно с помощью ключа (комната в здании). Прямой поиск применяется тогда, когда число элементов фиксировано и их сравнительно немного.Линейный поиск. Данный вид поиска наиболее простойдля программной реализации, хотя его выполнение занимаетмного времени. Элементы проверяются последовательно, по одному, пока нужный элемент не будет найден. В отличие от прямого поиска здесь нет системы в расположении элементов.Если список содержит N элементов, то каждый раз в среднембудут проверяться N/2 элементов. Линейный поиск медленный,но позволяет легко добавлять новые элементы, помещая их вконец списка.
Хорошо разработанная программа обычно имеетпростую (линейную) структуру, и, следовательно, такую жеструктуру должны иметь и данные, поэтому линейный поиск втаких структурах эффективен.Двоичный поиск. Для ведения двоичного поиска ключидолжны быть упорядочены по величине или алфавиту. В этомслучае можно добиться среднего времени поиска log2N. Придвоичном поиске ключ сравнивается с ключом среднего элемента списка. Если значение ключа больше, то та же самая процедура повторятся для второй половины списка, если же меньше, то для первой.
Таким образом, за шаг этого процесса список уменьшается наполовину.Основная трудность при двоичном поиске — как вводитьновые элементы. Так как список упорядочивается, то введениенового элемента может вызвать переписывание всех элементовдля того, чтобы новый элемент поместить в нужном месте.Хеш-поиск. Этот вид поиска является попыткой применить прямой поиск для поиска в больших наборах данных. Изизначального значения ключа вычисляется значение псев-172доключа, называемого хеш-кодом, и этот код используется какиндекс в таблице адресов элементов. Если все ключи соответствуют разным хеш-кодам, то любой элемент будет найден заодин прямой поиск.Пример.
В абстрактном компиляторе может быть отведено 1000 мест для имен переменных. В языке допускаются слова из 6 символов. Это позволяет создавать 266 имен, что гораздобольше, чем размер таблицы символов. Но если каждое число,представляющее имя, уменьшить до числа, находящегося между 0 и 999, то имена могут быть записаны в таблицу. Алгоритмы вычисления хеш-кодов различны, например имя (ключ)можно рассматривать как двоичное число.
Это число можноразделить на размер таблицы, остаток использовать как код.Другие алгоритмы предлагают сложение битов внутри числаили некоторые другие функции с ключом.Недостатком хеш-поиска является тот факт, что некоторые идентификаторы могут иметь одинаковые хеш-коды, поэтому возникает проблема обработки пересечений элементов, т.е.элементов, имеющих одинаковые хеш-коды.
Когда определенное значение хеш-кода встречается первый раз, его помещают вопределенное место в таблице. Если произошло пересечение сдругим элементом, его помещают в другое место в соответствии со следующим алгоритмом:INSERT: procedure (ключ, аргумент);declare 1 TABLE(размер),2 KEY,2 ARGUMENT;declare хеш–код;Вычислить хеш–код;/* если запись находится в таблице */if TABLE(хеш-код).KEY = ключ then return;/* обработка совпадающих хеш-кодов */do while (TABLE(хеш-код).KEY0 &TABLE(хеш-код).KEYключ);173хеш–код = новое значение, зависящее от(хеш–код, ключ);end;TABLE(хеш-код).KEY = ключ;TABLE(хеш-код).ARGUMENT = аргумент;end INSERT;Таким образом, в случае пересечения элементов имеетсяпереход к следующему месту в таблице.
Если нужное место занято, — то переход на место, расположенное на некотором расстоянии от занятого, или вычисление нового хеш-кода, исходяиз имеющегося ключа и кода.Основным недостатком хеш-поиска является тот факт,что при плотном заполнении таблицы алгоритм ввода элементов весьма трудоемок.7.4.2 Деревья поискаЕсли данные организованы как структура дерева, алгоритм поиска сводится к алгоритму, просматривающему всеузлы дерева.
Для ведения поиска существуют два основных алгоритма поиска: поиск в глубину и поиск в ширину.Поиск в глубину. При поиске в глубину каждая ветвь дерева просматривается слева направо.Для двоичных деревьев алгоритм поиска имеет простуюрекурсивную структуру (рис. 7.1):174ABCGDEFРис. 7.1 — Схема поиска по двоичному деревуDEPTHFIRST: procedure(TREE);declare 1 TREE,2 KEY,2 ARGUMENT, /* данные */2 RightSon, /* ноль, если нетсына*/2 LeftSon;/* ноль, если нет сына */if TREE = null then return;if текущий узел не KEY then do;call DEPTHFIRST(LtftSon);call DEPTHFIRST(RightSon);end;end DEPTHFIRST;Заметим, что если дерево упорядочено таким образом, чтоLeftSon имеет ключ, величина которого меньше, чем значение корневого узла, а величина ключа для RightSon больше,чем значение корневого узла, то такой алгоритм аналогичен алгоритму двоичного поиска.175Поиск в ширину.
Это алгоритм поиска, при котором просматривается каждый уровень в направлении сверху вниз (рис.7.2).A{A}BG{B, G}CD{C, D}EF{E, F}Рис. 7.2 — Поиск в ширинуПри таком алгоритме параллельного поиска быстро находятся кратчайшие ветви дерева. В общем виде алгоритм имеетструктуру:BREADTHFIRST: procedure(solution);declare 1 TREE,2 ARGUMENT, /* данные */2 SONS(N); /* произвольные деревья */declare (solution, NextStep) set of TREE;/* переход вниз для каждого уровня */do while (solution 0);NextStep = {TREE.SONS(I) для всех I и TREEв solution};call BREADTHFIRST(NextStep);end;end BREADTHFIRST;Поиск в ширину очень популярен при решении задачи олабиринте.Поиск с возвратом.
Для многих алгоритмов часто требуется перебор возможных вариантов решения задачи. Один изтаких способов перебора называется поиском с возвратом.176Алгоритм:Вызвать первую часть;do while (не окончится);вызвать следующую часть;do while (нет возможности продолжить);Вернуться на предыдущий уровень;Проверить возможность альтернативного решениядля этого уровня;end;end;Алгоритм поиска в глубину является примером поиска свозвратом:Начать с корневого узла;do while (существуют не просмотренные узлы);Перейти к узлу «левый сын», если возможно;Иначе перейти к узлу «правый брат»;do while (нет узлов «левый сын» и «правый брат);Перейти к узлу «отец»;Перейти к узлу «правый брат», если можно;end;end;7.4.3 Стратегия распределения памятиОдним из типов поиска являются задачи по распределению памяти (наиболее характерны они при создании ОС), однако во многих прикладных алгоритмах эти задачи возникают присоздании прикладных программ, работающих с большимобъемом данных.
Если до начала обработки полный объем данных, которые подлежат обработке, неизвестен, то используетсяобщий подход для распределения областей этой памяти согласно заданным требованиям.Дана фиксированная область памяти, задача заключаетсяв том, чтобы занимать и освобождать меньшие области памятибольшой областью, без выхода за границы памяти. При распределении памяти проверяются наибольшие свободные области.Обычно эти области малы для размещения в них всех данных,и, следовательно, память становится фрагментной.
Имеютсяследующие способы уменьшения фрагментности.177Первое возможное размещение. Последовательно просматриваются области памяти, пока не найдется первая, достаточная для размещения. Вся область организована в список иупорядочена по адресам (рис. 7.3).Список свободных областей памятиПамять…Следующий элемент в спискеАдрес текущего элементаРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
