Полная версия: метод равномерного и дихотомического поиска
Нигде не могу в сети найти алгоритмы этих методов, если у кого то есть алгоритмы киньте сюда пожалуйста или дайте ссылку! :flowers: :flowers:
Цитата
2.3. Дихотомический (бинарный) поиск
Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.
Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.
На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.
Запишем все сказанное в виде программы:
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 <элемент найден> else <элемент не найден>;
Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).
Особого внимания здесь заслуживают операции добавления и удаления. Они должны сохранять массив отсортированным (лучше написать операции так, чтобы они не нарушали отсортированности массива, чем каждый раз сортировать его). Рассмотрим сначала добавление.
Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива:
i := n;
while (i>=1)and(A[i]>Key) do
begin
A[i+1] := A[i]; {сдвигаем}
Dec(i);
end;
A[i+1] := Key;
Inc(n);
Такая операция добавления имеет сложность T(n).
Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.
Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.
Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.
На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.
Запишем все сказанное в виде программы:
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 <элемент найден> else <элемент не найден>;
Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).
Особого внимания здесь заслуживают операции добавления и удаления. Они должны сохранять массив отсортированным (лучше написать операции так, чтобы они не нарушали отсортированности массива, чем каждый раз сортировать его). Рассмотрим сначала добавление.
Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива:
i := n;
while (i>=1)and(A[i]>Key) do
begin
A[i+1] := A[i]; {сдвигаем}
Dec(i);
end;
A[i+1] := Key;
Inc(n);
Такая операция добавления имеет сложность T(n).
Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.
Такое впечатление что просто хотят запудрить народу мозг 
Метод дихотомического поиска - он же метод бинарного поиска, ну а метод равномерного поиска - это судя по всему :
вполне равномерно ... :D
Метод дихотомического поиска - он же метод бинарного поиска, ну а метод равномерного поиска - это судя по всему :
i:=1;
while( i<=n and x[i] <> key ) do
inc(i);
if i>n then
writeln('Not found')
else writeln('pos=',i);
вполне равномерно ... :D
я имела ввиду методы оптимизации:
нам задано функцию например y=sin(x) и нужно найти минимум этой функции на заданом интервале напримео от 0 до 8 при таком то шаге и с такой то точностью!!
нам задано функцию например y=sin(x) и нужно найти минимум этой функции на заданом интервале напримео от 0 до 8 при таком то шаге и с такой то точностью!!
конкретно то что ты написала можно сделать так :
если использовать методы поиска, то надо просто забить значения ф-и в массив, в такомже цикле, ну а затем просто воспользоваться методом поиска.
uses crt;
var
left, right : single;
step, t, min : single;
function f( x : single) : single;
begin
f := sin(x);
end;
Begin
clrscr;
write('Left='); readln(left);
write('Right='); readln(right);
write('Step='); readln(step);
min := left;
t := min;
while (t<=right) do begin
writeln('t = ',t:2:2,' f( ',t:2:2,' )= ', f(t)2);
if f(t) < f(min) then
min := t;
t := t + step;
end;
writeln;
writeln('MIN : ');
writeln('t = ', min:2:2, ' f(' ,min:2:2,' ) = ', f(min)
readln;
end.
если использовать методы поиска, то надо просто забить значения ф-и в массив, в такомже цикле, ну а затем просто воспользоваться методом поиска.
Это прямой перебор, а мне надо равномерный поиск! И дихотомичкский метод должен осуществляться с заданой функцией без масива и без сортировки!!
дихотомия ::
оба метода выдают точные результаты при наличии строго одного минимума. При наличии двух и более на некоторых тестах неверные результаты.
Код
const _eps = 1E-7;
...................
v := up - down; {8 - 0}
x1 := v / 2;
step := v / 4;
whili (step >= _eps) and (abs(f(x1 - step) - f(x1 + step)) >= _eps) do
begin
if f(x1 - step) < f(x1 + step) then
x1 := x1 - step else x1 := x1 + step;
step := step / 2;
end;
...................
v := up - down; {8 - 0}
x1 := v / 2;
step := v / 4;
whili (step >= _eps) and (abs(f(x1 - step) - f(x1 + step)) >= _eps) do
begin
if f(x1 - step) < f(x1 + step) then
x1 := x1 - step else x1 := x1 + step;
step := step / 2;
end;
оба метода выдают точные результаты при наличии строго одного минимума. При наличии двух и более на некоторых тестах неверные результаты.
Catty, это все конечно хорошо, но функция Sin(x) - периодическая, а следовательно - может иметь на заданном интервале не один min/max, какой из них будем искать?
P.S.
Virt, опередил :D
P.S.
Virt, опередил :D
если я правильно догадываюсь то дихотомия это частный случай равномерного поиска.
ЗЫ
volvo
стараемся.
ЗЫ
volvo
стараемся.
Volvo
нужно искать глобальный минимум, тоесть самый минимумистый минимум! :D
нужно искать глобальный минимум, тоесть самый минимумистый минимум! :D
по идее оба метода должны находить самый минимальный минимум!
и это можно пару слов к прогам а то что-то я не совсем понимаю почему именно так ...
и это можно пару слов к прогам а то что-то я не совсем понимаю почему именно так ...
Ну, а как быть, если (опять же берем для примера y = Sin(x)) у функции несколько одинаковых минимумов? У синуса минимальное значение = -1, и именно оно будет встречаться на заданном интервале неоднократно (хотя если X измеряется в радианах - то минимум будет всего один <_< )
Volvo забуть про sin(x) это я взяла для примера! но если даже минимумов несколько и они все равны -1, то программа должна выдать -1, тоесть это самый минимальный минимум, а сколько их это уже не важно!
1) берется середина отрезка в котором ищется минимум ,смотрится справа или слева от него меньшее значение ,где меньше там следующая середина. Смотрится справа или слева от середины опять ,... До тех пор пока не будет нужная точность (1E-7 до 7го знака после запятой)
спасибо рыбки! я уже во всем разобралась!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.