Алгоритмы и структуры данных

Идею метода альфа-бета отсечения реализует следующий алгоритм:

function AB(p: position; alpha, beta:  integer):  integer; {оценивает и возвращает выигрыш F''(p)  для позиции p} label done; var

m,i,t,d:  integer; begin

Определить позиции p₁,...,p_d, подчиненные p; if d = 0 then AB := f(p)  else begin m := alpha;

for i:= 1 to d do begin

t := -AB(p_±,  -beta,  -m);

if t > m then m := t;

if m >= beta then goto done; end;

done: AB := m; end; end;

Выгода от альфа-бета отсечения заключается в более раннем выходе из цикла. Эти отсечения полностью безопасны (корректны), потому что они гарантируют, что отсекаемая часть дерева хуже, чем основной вариант.

При оптимальных обстоятельствах перебор с альфа-бета отсечением должен просмотреть W^L+1)/2 + W^L/2-1 позицию, где W - среднее количество ходов в позиции, а L - количество уровней дерева. Это намного меньше, чем перебор с возвратом. Данное отсечение позволяет достигать примерно вдвое большей глубины за то же самое время.

2.2.6. Локальные и глобальные оптимальные решения

Описанная ниже стратегия нередко приводит к оптимальному решению задачи:

1) находится произвольное решение;

2. для улучшения текущего решения применяется к нему какое-либо преобразование из некоторой заданной совокупности преобразований. Это улучшенное решение становится новым «текущим» решением;
3. указанная процедура повторяется до тех пор, пока ни одно из преобразований в заданной их совокупности не позволит улучшить текущее решение.

Результирующее решение может, хотя и необязательно, оказаться оптимальным. В принципе, если «заданная совокупность преобразований» включает все преобразования, которые берут в качестве исходного одно решение и заменяют его каким-либо другим, процесс «улучшений» не закончится до тех пор, пока не получим оптимальное решение. Но в таком случае время выполнения пункта 2 окажется таким же, как и время, требующееся для анализа всех решений, поэтому описываемый подход в целом окажется достаточно бессмысленным.

Этот метод имеет смысл лишь в том случае, когда можно ограничить совокупность преобразований небольшим ее подмножеством, что дает возможность выполнить все преобразования за относительно короткое время: если «размер» задачи равняется n, то можно допустить O(n²) или O(n³) преобразований. Если совокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое за один шаг, как «близкие». Такие преобразования называются «локальными», а соответствующий метод называется локальным поиском.

 

Одной из задач, которую можно решить именно методом локального поиска, является задача нахождения минимального остовного дерева (см. 2.6.4). Локальными преобразованиями являются такие преобразования, в ходе которых берется то или иное ребро, не относящееся к текущему остовному дереву, оно добавляется в это дерево (в результате должен получиться цикл), а затем убирается из этого цикла в точности одно ребро (предположительно, ребро с наивысшей стоимостью), чтобы образовалось новое дерево.

Время, которое занимает выполнение этого алгоритма на графе из n узлов и e ребер, зависит от количества требующихся улучшений решения. Одна лишь проверка того факта, что преобразования уже неприменимы, может занять 0(n-e) времени, поскольку для этого необходимо перебрать e ребер, а каждое из них может образовать цикл длиной примерно n. Таким образом, этот алгоритм несколько хуже, чем алгоритмы Прима и Крускала (см. 2.6.4.1 и 2.6.4.2), однако он может служить примером получения оптимального решения на основе локального поиска.

Алгоритмы локального поиска проявляют себя с наилучшей стороны как эвристические алгоритмы для решения задач, точные решения которых требуют экспоненциальных затрат времени (относятся к классу EXPTIME). Общепринятый метод поиска состоит в следующем. Начать следует с ряда произвольных решений, применяя к каждому из них локальные преобразования до тех пор, пока не будет получено локально-оптимальное решение, т. е. такое, которое не сможет улучшить ни одно преобразование. Как показывает рис. 25, на основе большинства (или даже всех) произвольных начальных решений нередко будут получаться разные локально-оптимальные решения. Если повезет, одно из них окажется глобально-оптимальным, т. е. лучше любого другого решения.

На практике можно и не найти глобально-оптимального решения, поскольку количество локально-оптимальных решений может оказаться колоссальным. Однако можно, по крайней мере, выбрать локально-оптимальное решение, имеющее минимальную стоимость среди всех найденных решений.

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

Поиск - процесс отыскания информации во множестве данных (обычно представляющих собой записи) путем просмотра специального поля в каждой записи, называемого ключом. Целью поиска является отыскание записи (если она есть) с данным значением ключа.

Поиск - одно из наиболее часто встречающихся в программировании действий. Существует множество различных алгоритмов этого действия, принципиально зависящих от способа организации данных. Далее рассмотрены алгоритмы поиска в различных структурах данных.

2.3.1. Поиск в линейных структурах

При дальнейшем рассмотрении поиска в линейных структурах определим, что множество данных, в котором производится поиск, описывается как массив фиксированной длины:

A: array[1..n]  of ItemType;

Обычно тип ItemType описывает запись с некоторым полем, играющим роль ключа, а сам массив представляет собой таблицу. Так как здесь рассматривается, прежде всего, сам процесс поиска, то будем считать, что тип ItemType включает только ключ.

2.3.1.1. Последовательный (линейный) поиск

Последовательный поиск - самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Именно так поступает человек, когда ищет что-то в неупорядоченном множестве. Таким образом, данный алгоритм можно применять тогда, когда нет никакой дополнительной информации о расположении данных в рассматриваемой последовательности.

Оформим описанный алгоритм в виде функции на Паскале.

function LineSearch(Key: ItemType, n: integer;

var A: array[1..n] of ItemType): boolean; {Функция линейного поиска,}

{если элемент найден, то возвращает значение true, иначе - false} var

i: integer; begin

i := 1;

while (i <=n ) and (A[i]<>Key) do i := i + 1; if A[i]=Key then LineSearch := true

else LineSearch := false;

end;

В среднем этот алгоритм требует n/2 итераций цикла. Это означает временную сложность алгоритма поиска, пропорциональную O(n). Никаких ограничений на порядок элементов в массиве данный алгоритм не накладывает. При наличии в массиве нескольких элементов со значением Key алгоритм находит только первый из них (с наименьшим индексом).

Здесь можно хранить множество как в массиве (как показано выше), так и в обычном однонаправленном списке.

Существует модификация алгоритма последовательного поиска, которая ускоряет поиск.

Эта модификация поиска является небольшим усовершенствованием предыдущего. В любой программе, имеющей циклы, наибольший интерес представляет оптимизация именно циклов, т. е. сокращение числа действий в них. Посмотрим на алгоритм последовательного поиска. В цикле while производятся два сравнения: (i<=n) и (A[i]<>Key). Избавимся от одного из них (от первого), введя в массив так называемый «барьер», положив A[n+1] := Key. В этом случае в цикле обязательно будет найден элемент со значением Key. После завершения цикла требуется дополнительная проверка того, был ли найден искомый элемент, или «барьер».

Тогда функция поиска будет выглядеть так:

function LineSearchWithBarrier(Key:  ItemType, n:  integer;

var A: array[1..n+1] of ItemType): boolean;

{Функция линейного поиска с барьером,}

{если элемент найден, то возвращает значение true, иначе - false} var

i: integer; begin

I := 1;

A[n+1]  := Key;

while A[i]<>Key do I := I + 1; if I <= n then LineSearchWithBarrier := true else LineSearchWithBarrier := false;

end;

Надо сказать, что хотя такая функция будет работать быстрее, но временная сложность алгоритма остается такой же - O(n). Гораздо больший интерес представляют методы, не только работающие быстро, но и реализующие алгоритмы с меньшей сложностью. Один из таких методов - бинарный поиск.

2.3.1.2. Бинарный поиск

Этот алгоритм поиска предполагает, что множество хранится, как некоторая упорядоченная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.

Суть метода заключается в следующем. Областью поиска (L, R) назовем часть массива с индексами от L до R, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (L, R), где L = 1, а R = n, т. е. вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m := (L+R) div 2. Если Key > A_m, то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от L + m до R, следовательно, можно присвоить L := m + 1, сократив область поиска. В противном случае можно положить R := m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны (рис. 26).

На каждом шаге метода область поиска будет сокращаться вдвое. Как только L станет равно R, т. е. область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

 

Оформим описанный алгоритм в виде функции на Паскале.

function BinarySearch(Key: ItemType, n: integer;

var A: array[1..n] of ItemType): boolean; {Функция двоичного поиска,}

{если элемент найден, то возвращает значение true, иначе - false} var

L, m, R: integer; begin

L := 1; R := n;

while (L <> R) do begin m := (L+R) div 2; if Key > A[m] then L := m+1 else R := m;

end;

if A[L]= Key then BinarySearch := true else BinarySearch := false;

end;

Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность алгоритма пропорциональную O(log n).

2.3.2. Хеширование данных

 

2.3.2.1. Функция хеширования

В рассмотренных выше методах поиска число итераций в лучшем случае было пропорционально O(log n). Естественно, возникает желание найти такой метод поиска, при котором число итераций не зависело бы от размера таблицы, а в идеальном случае поиск сводился бы к одному шагу.

Простейшей организацией таблицы, обеспечивающей идеально быстрый поиск, является таблица прямого доступа. В такой таблице ключ

92 является адресом записи в таблице или может быть преобразован в адрес, причем таким образом, что никакие два разных ключа не преобразуются в один и тот же адрес. При создании таблицы выделяется память для хранения всей таблицы и заполняется пустыми записями. Затем записи вносятся в таблицу - каждая на свое место, определяемое ее ключом. При поиске ключ используется как адрес и по этому адресу выбирается запись, если выбранная запись пустая, то записи с таким ключом вообще нет в таблице. Таблицы прямого доступа очень эффективны в использовании, но, к сожалению, область их применения весьма ограничена.

Назовем пространством ключей множество всех теоретически возможных значений ключей записи. Назовем пространством записей множество тех ячеек памяти, которые выделяются для хранения таблицы.

Таблицы прямого доступа применимы только для таких задач, в которых размер пространства записей может быть равен размеру пространства ключей. В большинстве реальных задач, однако, размер пространства записей много меньше, чем пространства ключей. Так, если в качестве ключа используется фамилия, то, даже ограничив длину ключа 10 символами кириллицы, получаем 33¹⁰ возможных значений ключей. Даже если ресурсы вычислительной системы и позволят выделить пространство записей такого размера, то значительная часть этого пространства будет заполнена пустыми записями, так как в каждом конкретном заполнении таблицы фактическое множество ключей не будет полностью покрывать пространство ключей.

Из соображений экономии памяти целесообразно назначать размер пространства записей равным размеру фактического множества записей или превосходящим его незначительно. В этом случае необходимо иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, т. е., преобразование ключа в адрес записи: a := h(k), где a - адрес, k - ключ. Такая функция называется функцией хеширования (другие ее названия - функция перемешивания, функция рандомизации).

Идеальной хеш-функцией является такая функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса: k1 Ф k2 == h(k1) Ф h(k2).

При попытке отображения точек из некоторого широкого пространства в узкое неизбежны ситуации, когда разные точки в исходном пространстве отобразятся в одну и ту же точку в целевом пространстве.

Ситуация, при которой разные ключи отображаются в один и тот же адрес записи, называется к о ллизией, или перепо лнением , а такие ключи называются синонимами. Коллизии составляют основную проблему для хеш-таблиц и решение ее будет рассмотрено особо.

Если хеш-функция, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k := h'(a), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.

К хеш-функции в общем случае предъявляются следующие требования:

• она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей (рис. 27);
• она должна порождать как можно меньше коллизий для данного фактического множества записей;
• она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;

- она должна быть простой и быстрой для вычисления.

 

Рис. 27. Распределение коллизий в адресном пространстве таблицы

Приведем обзор и анализ некоторых наиболее простых из применяемых на практике хеш-функций.

Простейшей хеш-функцией является деление по модулю числового значения ключа на размер пространства записи. Результат интерпретируется как адрес записи. Следует иметь в виду, что такая функция плохо соответствует первым трем требованиям к хеш-функции и сама по себе может быть применена лишь в очень ограниченном диапазоне реальных задач. Однако операция деления по модулю обычно применяется как последний шаг в более сложных функциях хеширования, обеспечивая приведение результата к размеру пространства записей.

Следующей хеш-функцией является функция середины квадрата. Значение ключа преобразуется в число, это число затем возводится в квадрат, из него выбираются несколько средних цифр и интерпретируются как адрес записи.