В разделе используется алгоритм случайного поиска, аналогичный рассмотренному в предыдущем разделе. С помощью датчика случайных чисел, имеющих равномерное распределение на (ОД), формируем начальное множество возможных решений (в этом методе часто называемом начальной популяцией особей). Каждое решение представим в виде бинарной матрицы, состоящей из нулей и единиц [c.509]
Основным принципом проектирования процедура поиска технических решений определена как установление бинарных отношений между множествами признаков и технических решений, причем возможные варианты составляют подмножество [c.125]
Ступенчатый поиск имеет важный частный вариант -бинарный поиск, когда 8=2. [c.149]
Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(A+B)/2 с округлением в меньшую сторону. Ключ i-й записи p(i) сравнивается с искомым значением q. Если p(i) =q, то поиск заканчивается. В случае p(i)>q записи с номерами i+1, i+2,..., М заведомо не содержат ключа q, и надо сократить интервал поиска, приняв B=i. Аналогично при p(i)
[c.149]
Алгоритм бинарного поиска может быть представлен следующей программой на языке Паскаль [c.149]
Достаточно легко оценить максимальное число сравнений m при поиске данных бинарным методом. Сокращение интервала поиска на каждом шаге в худшем случае приведет к интервалу нулевой длины, что соответствует отсутствию в массиве искомого значения ключевого атрибута. После первого сравнения интервал поиска составит М/2 записей, после второго - М/4 и т. д. Когда интервал поиска впервые станет меньше 1, применяемая схема округления результата деления даст нулевой интервал и поиск закончится. Это соответствует неравенству [c.150]
Среднее число сравнений при бинарном поиске составляет =log(M) -1. Для обоснования представим все возможные разветвления алгоритма бинарного поиска в виде дерева. Число уровней дерева соответствует m. Половина возможных сравнений расположена на последнем уровне и половина - на первых (log(M)-l) уровнях. [c.150]
Определение лучшего метода поиска (из рассмотренных выше последовательного, двухступенчатого и бинарного) опирается на следующие рассуждения. Во всех трех случаях время поиска является функцией от числа записей М. Конкретные выражения составляют [c.150]
Поэтому можно утверждать даже при неизвестных коэффициентах kl, k2, k3, что при достаточно большом числе записей М бинарный метод поиска выполняется, безусловно, быстрее двух остальных. Значения kl, k2, k3 влияют на граничную величину М, выше которой преимущество бинарного поиска безусловно. [c.151]
Неэффективность бинарного поиска для списковой организации данных объясняется тем обстоятельством, что для достижения середины интервала требуется последовательное движение в соответствии с адресами связи и суммарное количество переходов от записи к записи достаточно велико. Число переходов от записи к записи при доступе к серединам интервалов представляется величиной М/2+М/4+М/8+..., что практически составляет М. [c.156]
В процессе поиска данных по совпадению в упорядоченном бинарном дереве просматривается некоторый путь по дереву, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р(1). Если p(l)>q, просмотр дерева продолжается по левой ветви корня, если p(l)<=q - по правой. Для произвольной записи дерева с ключом p(i) результаты сравнения означают [c.163]
Для определения среднего числа сравнений при поиске записи в упорядоченном бинарном дереве рассмотрим ситуацию, когда требуемая запись не найдена, что равноценно вставке записи с искомым значением в дерево. Ненайденный ключ может с одинаковой вероятностью попасть в один из М+1 интервалов, образованных ключами, находящимися в дереве. Неудачный поиск закончится всегда на нулевом адресе связи. [c.163]
Если обозначить через Е(М) сумму длин всех ветвей дерева с учетом выхода на нулевые адреса связи, то среднее число сравнений при поиске в упорядоченном бинарном дереве С(М) составит [c.164]
При замене натурального логарифма на двоичный (1п2 = 0,7) получаем оценку числа сравнений при поиске в упорядоченном бинарном дереве [c.164]
По времени поиска последовательный массив и бинарное дерево предпочтительнее цепного каталога. Минимальное время корректировки характерно для бинарного дерева, а минимальный объем дополнительной памяти - для последовательного массива. [c.168]
Для последовательного массива и упорядоченного бинарного дерева известен алгоритм поиска по совпадению. Как использовать этот алгоритм для поиска по условию p(i)>q [c.186]
Вычисление медианы Кемени является задачей целочисленного программирования. Для ее нахождения используют различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ. Применяют также алгоритмы, основанные на идее случайного поиска, поскольку для каждого бинарного отношения нетрудно найти множество его соседей. [c.335]
Допустим, вы хотите найти данные об абоненте с номером 357-14-18 в таблице из 526 строк. Система знает (1) значения ключа (т. е. номера) — уникальны (2) всего в справочнике 526 записей. Прежде всего система заглядывает в середину таблицы и читает 263-ю запись. Возможны три случая (1) номер телефона этой записи равен искомому — запись найдена сразу (2) номер меньше искомого (например, 213-14-52, — значит, искомый телефон находится в верхней половине таблицы) (3) номер больше искомого (например, 425-17-25, значит, искомый номер находится в нижней половине таблицы). Таким образом, с первого захода система исключает из области поиска сразу половину таблицы. Следующая запись берется из середины нижней или верхней половины (например, 131-я запись). В зависимости от результата сравнения, исключается половина новой группы записей и т. д. Выполнив всего несколько шагов (в нашем случае прочитав максимум 9-10 записей вместо 526), система либо найдет искомый номер, либо удостоверится, что его в таблице нет. Это самый простой метод поиска, и называется он двоичным (или бинарным, от слова binary — двоичный). [c.246]