Последовательный, индексно-последовательный, бинарный поиск

Поиск данных

Поиск циклов на ориентированном графе

Многие практические задачи сводятся к поиску циклов, то есть путей, начинающихся и заканчивающихся в одной и той же вершине. Отметим два момента. Во-первых, очевидно есть смысл искать элементарные циклы, то есть пути, не содержащие циклов внутри себя. Во-вторых, каждый цикл из K вершин порождает еще K-1 цикл путем выбора другой начальной вершины. Например, если путь из вершин a – b - c образует цикл, то циклами будут и пути b – c - a, c – a – b. Простейший способ избежать такого повторения – нумеровать вершины графа и считать, что цикл начинает вершина с минимальным номером.

Циклы можно находить различными способами. Выберем, например, начальную вершину S и методом поиска в глубину будем искать пути S–T–R-…-S с дополнительными условиями, чтобы номера вершин T, R, … были большими, чем номер вершины S, а отличные от S вершины в пути не повторялись. Если из некоторой промежуточной вершины B не находится путь в вершину S, имеет смысл временно запретить эту вершину, чтобы не повторять бесполезных попыток. Перебирая начальные вершины, можно найти все циклы.

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

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

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

Чаще всего встречаются следующие задачи поиска:

· найти любую запись с заданным значением ключа;

· найти первую запись с заданным значением ключа;

· найти все записи с заданным значением ключа;

· найти любую запись с заданным значением ключа;

· если поиск неудачен, вставить новую запись с заданным значением ключа;

· найти и удалить запись с заданным значением ключа.

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

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

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

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

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

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

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

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

Бинарный поиск основан на идее известного численного метода половинного деления или дихотомии. Записи в таблице располагаются по возрастанию (убыванию) значений ключа поиска. Первоначально нижняя граница поиска соответствует первой, а верхняя - последней записи таблицы. Анализируется средняя запись таблицы. В зависимости от величины ключа можно сделать вывод о том, в какой половине таблицы нужно продолжать поиск. Тем самым пространство поиска сокращается вдвое, и процесс продолжается. Легко видеть, что максимальная трудоемкость поиска пропорциональна величине log₂N, где N - размер таблицы.

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

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

Program Index;

{ Создание индекса для отсортированного файла и поиск }

Uses Crt;

Type

zap=record

Name: string

{ далее могут быть другие поля }

end;

ind=record

Name: string;

Nom: integer

end;

Var

I, M, N, Low, High, Mid: integer;

Key, Namer: string;

B: boolean;

Zapr: zap;

Indr: ind;

Fzap: file of zap;

Find: file of ind;

Ish: text;

Procedure Vvod;

Begin

Reset(Ish);

Rewrite(Fzap);

While not Eof(Ish) do

begin

ReadLn(Ish,Namer);

Zapr.Name:=Namer;

Write(Fzap,Zapr)

end;

Close(Ish);

Close(Fzap);

End;

Procedure SozdInd(var N: integer);

Begin

I:=5; M:=0; { номер записи в Fzap }

N:=0; { номер записи в Find}

Rewrite(Find);

Reset(Fzap);

While not Eof(Fzap) do

begin

I:=I-1;

Read(Fzap,Zapr);

if I=0 then

begin

Indr.Name:=Zapr.Name;

Indr.Nom:=M;

N:=N+1;

{ счетчик числа записей в индексном файле }

Write(Find, Indr);

I:=5

end;

M:=M+1

end;

Close(Find);

Close(Fzap)

End;

Procedure Poisk(Key: string; var M: integer);

{ Key-ключевое имя для поиска, N-число записей в индексном файле }

{ M-номер найденной записи в исходном файле, M = -1 – запись не найдена }

Begin

Reset(Fzap);

Reset(Find);

Low:=0;

High:=N-1;

While Low<=High do { бинарный поиск индекса }

begin

Mid:=(Low+High) div 2;

Seek(Find, Mid);

Read(Find, Indr);

if Key=Indr.Name then

begin

Low:=Mid+1;

High:=Mid

end

else if Key<Indr.Name then High:=Mid-1

else Low:=Mid+1

end;

M:=High;

{ здесь Low>High}

{ M - максимальный номер записи в индексе, для которой Name<=Key }

{ если такой записи нет, то M = -1 }

if M >= 0 then

begin

Seek(Find, M);

Read(Find, Indr);

M:=Indr.Nom;

end

else M:=0;

Seek(Fzap, M);

Read(Fzap, Zapr);

While not Eof(Fzap) and (Zapr.Name<Key) do

begin

Read(Fzap, Zapr);

M:=M+1

end;

if Zapr.Name<>Key then M:=-1; { имя не найдено }

Close(Fzap);

Close(Find)

End;

Begin { начало основной программы }

ClrScr;

WriteLn;

Write('Введите имя исходного файла ');

Readln(Namer);

Assign(Ish,Namer);

Assign(Fzap,'a');

Assign(Find,'b');

Vvod;

SozdInd(N);

B:=True;

While B do

begin

Write('Введите фамилию (признак конца - к) ');

ReadLn(Namer);

if Namer<>'к' then

begin

Poisk(Namer, M);

Writeln('M=', M)

end

else B:=False

end;

Erase(Find);

Erase(Fzap)

End.

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

Дата добавления: 2014-01-11