VPF::Поиск методом луча - Форум программистов

Antonik

Дата 22.3.2010, 11:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

Здравствуйте! Подскажите, в чем суть поиска методом луча (в книге Кнута он называется еще и как trie search) ? Это обычный последовательный поиск?

maxdiver

Дата 23.3.2010, 00:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Кажется, что trie и луч - совершенно разные вещи smile

Trie - это по-русски "бор", т.е. такое дерево, в котором сжато хранятся некие элементы.

Скажем, для чисел 12, 13, 2459, 301, 302, 310 trie выглядит следующим образом:
user posted image

Ну и понятно, как в таком trie искать число: спускаться по дереву (сначала найти первую цифру, потом вторую, и т.д.). Время работы - O(кол-ва цифр в числе).

Antonik

Дата 23.3.2010, 20:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

maxdiver,спасибо за понятное объяснение!А при реализации на Дельфи искомый образец должен быть строковой переменной?

maxdiver

Дата 23.3.2010, 22:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Да, удобнее всего работать с числами как со строками. Собственно, trie и строится-то по любым строкам, и не важно, числа это или нет.

Ну а само дерево хранить надо будет как-нибудь так:

Код


type PVertex = Vertex^;

type Vertex = record
   son : array ['0'..'9'] of PVertex;
end;

Код примерный, паскаль сто лет назад забыл smile

Antonik

Дата 24.3.2010, 13:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

maxdiver, спасибо! А сам поиск в массиве как делать? Проверять,есть ли следующий символ?

maxdiver

Дата 24.3.2010, 22:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Ну это не массив, а дерево. Т.е. Vertex содержит описание одной вершины дерева. Надо ввести единственную переменную, хранящую указатель на корень дерева:

Код


// объявили
var trie : PVertex;

// создали вершину-корень - пока без детей, т.е. пустой trie
New(trie);
for c:='0' to '9' do
   trie^.son[c] := nil;

Т.е. v^.son[c] для какой-то вершины v бора есть либо указатель на соответствующего сына (сына по букве c) или nil, если такого сына нет.

Скажем, чтобы добавить в trie число 12, надо сделать:

Код


var v1, v2 : PVertex;

New(v1);
New(v2);
for c:='0' to '9' do begin
   v1^.son[c] := nil;
   v2^.son[c] := nil;
end;
trie^.son['1'] := v1;
v1^.son['2'] := v2;

Поиск числа, заданного своим строковым представлением s, совсем прост:

Код


var v : PVertex;
   s : string;

v := trie;
for i:=1 to length(s) do
   if v <> nil then
      v := v^.son[s[i]];
if v = nil then
   writeln ('такого числа нет');
else
   writeln ('число найдено в trie');

Antonik

Дата 25.3.2010, 19:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

Спасибо!!!

Antonik

Дата 26.3.2010, 16:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

maxdiver!, а как забить весь массив в дерево? и вывести номер элемента?

Код


procedure TForm1.Button1Click(Sender: TObject);
 type PVertex=^Vertex;
      Vertex=record
      son:array['0'..'9'] of PVertex;
 end;
 const n=10;
 var a:array[1..n] of integer;
     i,j,buf,min:integer;
     s:string;
     trie,v:PVertex;
     c:Char;
 begin
//простая сортировка->>
 for i:=1 to n do
   begin
     StringGrid1.Cells[i-1,0]:=IntToStr(random(10));
     a[i]:=StrToInt(StringGrid1.Cells[i-1,0]);
     randomize;
   end;
 for i:=1 to n-1 do
  begin
   min:=i;
   for j:=i+1 to n do
    if (a[j]<a[min]) then
     min:=j;
     buf:=a[i];
     a[i]:=a[min];
     a[min]:=buf;
  end;
 for i:=1 to n do
 begin
  StringGrid2.Cells[i-1,0]:=IntToStr(a[i]);
 end;
//ввод искомого элемента->
s:=Edit1.Text;
New(trie);
for c:='0' to '9' do
  begin
    trie^.son[c]:=nil;
  end;
 v:=trie;
 for i:=1 to length(s) do
   if v<>nil then v:=v^.son[s[i]];
   if v=nil then Label1.Caption:='no '
   else Label1.Caption:='yes';
 end;
end.

maxdiver

Дата 28.3.2010, 00:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

Как добавлять - я написал выше, на примере числа 12. Вы уж сами постарайтесь сделать.

Antonik

Дата 28.3.2010, 21:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

maxdiver, просто у меня компилятор выдает, что массив с-(char) несовместим с типом PVertex

Добавлено позже
maxdiver, просто у меня компилятор выдает, что массив с-(char) несовместим с типом PVertex

maxdiver

Дата 29.3.2010, 23:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

И на какой строчке он это выдаёт?

Antonik

Дата 30.3.2010, 20:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2010

Репутация: нет
Всего: нет

Код


type PVertex = ^Vertex;
        Vertex = record
        son : array ['0'..'9'] of PVertex;
var trie ,v,v1,v2,v3: PVertex;
      c:array['0'..'9'] of Char;
      s:string;
begin
 s:=Edit1.Text;
 New(trie);
for c:='0' to '9' do //тут выдает E2010 Incompatible types: 'Char' and 'Array'
   trie^.son[c] := nil;
New(v1);
for c:='0' to '9' do 
 begin
   v1^.son[c] := nil;
   v2^.son[c] := nil;
 end;
for i:=1 to n do
begin
 trie^.son[c] :=b[i];//правильно ли добавляются элементы в дерево?
end;
v := trie;
for i:=1 to length(s) do
   if v <> nil then v := v^.son[s[i]];
   if v = nil then Label9.Caption:= 'такого числа нет'
                else Label9.Caption:= 'число найдено в trie';
 end;

maxdiver

Дата 3.4.2010, 09:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

c : char

И добавляются элементы тоже неправильно. Ещё раз посмотрите на внешний вид бора, на примеры добавляемых элементов. При добавлении нового числа в бор надо создавать промежуточные вершины.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »