метод равномерного и дихотомического поиска Опции

[Catty]

Нигде не могу в сети найти алгоритмы этих методов, если у кого то есть алгоритмы киньте сюда пожалуйста или дайте ссылку! :flowers: :flowers:

[klem4]

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. сохраняет массив отсортированным.

[klem4]

Такое впечатление что просто хотят запудрить народу мозг Метод дихотомического поиска - он же метод бинарного поиска, ну а метод равномерного поиска - это судя по всему :

i:=1;
while( i<=n and x[i] <> key ) do
 inc(i);
if i>n then
 writeln('Not found')
else writeln('pos=',i);

вполне равномерно ... :D

Сообщение отредактировано: klem4 - 14.09.2005 22:36

[Catty]

я имела ввиду методы оптимизации:
нам задано функцию например y=sin(x) и нужно найти минимум этой функции на заданом интервале напримео от 0 до 8 при таком то шаге и с такой то точностью!!

[klem4]

конкретно то что ты написала можно сделать так :

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)2);

   readln;

end.

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

[Catty]

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

[virt]

дихотомия ::

Код

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;

оба метода выдают точные результаты при наличии строго одного минимума. При наличии двух и более на некоторых тестах неверные результаты.

Сообщение отредактировано: virt - 15.09.2005 11:28

[volvo]

Catty, это все конечно хорошо, но функция Sin(x) - периодическая, а следовательно - может иметь на заданном интервале не один min/max, какой из них будем искать?

P.S.
Virt, опередил :D

Сообщение отредактировано: volvo - 15.09.2005 0:43

[virt]

если я правильно догадываюсь то дихотомия это частный случай равномерного поиска.

ЗЫ
volvo
стараемся.

Сообщение отредактировано: virt - 15.09.2005 0:55

[Catty]

Volvo
нужно искать глобальный минимум, тоесть самый минимумистый минимум! :D

[Catty]

по идее оба метода должны находить самый минимальный минимум!
и это можно пару слов к прогам а то что-то я не совсем понимаю почему именно так ...

[volvo]

Ну, а как быть, если (опять же берем для примера y = Sin(x)) у функции несколько одинаковых минимумов? У синуса минимальное значение = -1, и именно оно будет встречаться на заданном интервале неоднократно (хотя если X измеряется в радианах - то минимум будет всего один <_< )

[Catty]

Volvo забуть про sin(x) это я взяла для примера! но если даже минимумов несколько и они все равны -1, то программа должна выдать -1, тоесть это самый минимальный минимум, а сколько их это уже не важно!

[virt]

1) берется середина отрезка в котором ищется минимум ,смотрится справа или слева от него меньшее значение ,где меньше там следующая середина. Смотрится справа или слева от середины опять ,... До тех пор пока не будет нужная точность (1E-7 до 7го знака после запятой)

[Catty]

спасибо рыбки! я уже во всем разобралась!

Сообщение отредактировано: Catty - 15.09.2005 23:32