Дихотомический поиск

Cтраница 2

К основным методам поиска формуляров в списках относятся: перебор, вычисление адресов, дихотомический поиск. [16]

Последовательность поиска [ IMAGE ] Последовательность поиска оптимального значения параметра ди - оптимального значения параметра ме-хотомическим методом тодом Фибоначчи. [17]

Длина полученного интервала 1N ( интервал неопределенности) оценивает точность определения экстремума Ф, Рассмотрим в качестве методов сокращения интервала неопределенности метод последовательного дихотомического поиска ( половинного деления), метод Фибоначчи и метод золотого сечения. [18]

Поиск в описываемом случае распадается на два этапа. На первом из них используется обычный алгоритм дихотомического поиска, основанный на делении массива пополам и используемый для поиска в упорядоченных массивах. [19]

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

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

Количество узловых точек, которые необходимо хранить в ЗУ, можно было бы уменьшить в еще большей степени, если бы для описания функции можно было использовать произвольную совокупность из тр возможных наборов двух аргументов, распределяя их с большей плотностью на участках быстрого изменения функции и с меньшей плотностью на участках их медленного изменения. Однако при таком способе описания функций процедура поиска сильно усложняется, так как в общем случае дихотомический поиск оказывается неприменимым. [22]

Множество объектов, организованное в памяти в виде цепочки, не приспособлено для дихотомического поиска. Структура же двоичного дерева с двумя адресами связи, исходящими от каждого объекта, весьма удобна для организации дихотомического поиска. Через один из этих адресов связи каждый объект связывается с группой объектов, признак которых больше ( или по крайней мере не меньше), чем у этого объекта, а через другой адрес связи - с группой объектов, у которых признак меньше ( или по крайней мере не больше), чем у исходного объекта. В результате проверки знака отклонения от условия поиска одна из групп исключается из подмножества неопределенности и, следовательно, из дальнейшего поиска. [23]

Количество элементов списка, необходимых для изображения функции с заданной точностью, можно уменьшить в случае записи отдельных точек через неравноотстоящие интервалы, но обязательно в порядке монотонного изменения аргумента. В этом случае информация, хранящаяся в ЗУ, должна в явном виде содержать узловые значения аргумента. Отыскание требуемого элемента списка может быть осуществлено по заданному значению аргумента методом дихотомического поиска по близости. Вычисление функции выполняется так же, как и для случая записи через равноотстоящие значения аргумента. [24]

Пример двоичного дерева. [25]

Дихотомический поиск особенно удобен в том случае, если таблица сначала составляется, а затем многократно используется. Если же приходится часто производить не только поиск, но и занесение новых записей, то эффективность работы снижается, так как для занесения новой ключевой записи в монотонно возрастающую по ключам последовательность в массиве S потребуется произвести раздвижку этой последовательности. При такой раздвижке потребуется - Л / операций перемещения помимо тех - logs N операций, которые будут затрачены на дихотомический поиск места в массиве S, куда нужно вставить новую ключевую запись. Преимущество раздельного хранения информации в массивах S к Т состоит в том, что при разд-движке ключевых записей в массиве S нет надобности перемещать тексты записей в массиве Т, поскольку порядок следования этих текстов записей не имеет значения. [26]

Однако при достаточно большом количестве несущественных сочетаний подобное построение таблицы может привести к неэкономному использованию памяти. Может оказаться целесообразным записывать в таблицу только существенные сочетания в порядке монотонного изменения кода, составленного из HOi, Fa состояния и совместимого с ним номера входного сигнала. Информация, относящаяся к каждой точке, естественно, должна в явном виде содержать старое состояние и входной сигнал. Однако если для таблицы функции от двух числовых аргументов, в которой для описания функции используется произвольная совокупность наборов из двух фиксированных аргументов, процедуру дихотомического поиска по близости в общем виде не удается использовать, то в таблице конечного автомата дихотомический поиск ( по совладению) может быть применен. Поиск производится по коду, составленному из номера старого состояния я номера входного сигнала. Признаком несущественности заданного сочетания может служить отсутствие в таблице требуемого кода. [27]

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

Страницы: 1 2