Пошук з обмеженням глибини

Алгоритм для реалізації обмеженого пошуку вглиб (АОПГ) (англ. Depth-limited search, DLS) — алгоритм для обходу дерева.Він застосовується в таких алгоритмах, як алгоритм топологічного сортування, алгоритм пошуку сильно зв'язаних компонентів. Цей алгоритм є модифікацією алгоритму пошуку в глибину. Проблему необмежених дерев можна вирішити, передбачаючи застосування під час пошуку в глибину заздалегідь певної межі глибини L. Це означає, що вузли на глибині L розглядаються таким чином, як якщо б вони не мали наступників. Такий підхід називається пошуком з обмеженням глибини.

Опис алгоритму

Як і звичайний пошук у глибину, пошук з обмеженням глибини є алгоритмом неінформативного пошуку. Він працює так само, як пошук в глибину, але усуває недоліки повноти шляхом введення обмеження на максимальну глибину пошуку. Навіть якщо пошук все ще може відкривати дочірні вершини для вершин на максимальній глибині, він не буде робити це і, таким чином він не буде досліджувати нескінченно глибокі шляхи або застрягти в циклах. Тому пошук з обмеженням глибини знайде рішення, якщо воно знаходиться в межах заданої глибини, що гарантує повноту для будь-яких графів. Стратегія пошуку в глибину така: йти вглиб, поки це можливо (є непройдені вихідні ребра), повертатися і шукати інший шлях, коли таких ребер немає. Якщо після цього залишаються недоторкані вершини - можна вибрати одну з них і повторювати процес доти, поки залишаються невиявлені вершини. Знайшовши уперше вершину v, суміжну з u, ми відзначаємо цю подію, записуючи в поле ?[v] значення u. Утворюється дерево чи кілька дерев. Як і пошук у ширину, алгоритм пошуку в глибину використовує кольори вершин. Спочатку усі вершини - білі. При виявленні нової вершини, вона фарбується в сірий колір. Коли вершина цілком оброблена, вона фарбується в чорний колір. Крім цього пошук у глибину ставить на вершинах мітки часу. Кожна вершина має дві мітки: d[v] показує, коли вершина була виявлена, f[v] - коли оброблена. Ці мітки використовуються в багатьох алгоритмах на графах.

Вибір глибини

Іноді вибір межі глибини може бути заснований на кращому розумінні завдання. Наприклад, припустимо, що на розглянутій карті України є 20 міст. Тому відомо, що якщо рішення існує, то має бути завжди не більше 19; це означає, що одним з можливих варіантів є j = 19. Але насправді при уважному вивченні цієї карти можна виявити, що будь-яке місто може бути досягнуте з будь-якого іншого міста не більше ніж за 9 етапів. Це число, відоме як діаметр простору станів, надає нам кращу межу глибини, яка веде до більш ефективного пошуку з обмеженням глибини. Але в більшості завдань прийнята межа глибини залишається невідомою до тих пір, поки не буде вирішена сама задача.

Алгоритм (неформальний)

1. Визначити вершину, з якої слід починати пошук, і призначити максимальну глибину пошуку
2. Перевірити, чи є поточна вершина цільовим станом
   • Якщо не є цільовим станом: Нічого не робити
   • Якщо є цільовим станом: Повернути поточну вершину
3. Перевірити, чи знаходиться поточна вершина в межах максимальної глибини пошуку
   • Якщо поточна вершина знаходиться поза межею максимальної глибини пошуку: Нічого не робити
   • Якщо поточна вершина знаходиться в межах максимальної глибини пошуку:
     1. Розгорнути вершину і додати усі дочірні вершини до стеку
     2. Викликати пошук з обмеженням глибини для всіх вершин стеку і повернутися до кроку 2

Псевдокод

DLS(node, goal, depth) {
  if ( depth >= 0 ) {
    if ( node == goal )
      return node

    for each child in expand(node)
      DLS(child, goal, depth-1)
  }
}

Рекурсивна реалізація -- Псевдокод

Пошук з обмеженням глибини може бути реалізований як проста модифікація загального алгоритму пошуку в дереві або рекурсивного алгоритму пошуку в глибину . Псевдокод реалізації рекурсивного алгоритму пошуку в глибину приведений нижче! Зверніть увагу на те, що пошук з обмеженням глибини може призвести до невдачного завершення двох типів : стандартне значення failure вказує на відсутність рішення, а значення cutoff вказує на те, що на заданій межі глибини рішення немає!

   function Deptch-Limited-Search(problem , limit) returns рішення result 
                  або індикатор невдачі failure/cutoff
    return Recursive-DLS(Make-Node(Initial-State[problem]), problem,limit)
     
    function Recursive-DLS(Make-Node(node, problem, limit) 
          returns рішення  result   або індикатор невдачі failure/cutoff
      cutoff_occurred  <- false
     if Goal-Test[problem] (State[node]) then return Solution (node)
     else ifDeptch[node] = limit then return індикатор невдачі cutoff
     else foreachприйомник successorinExpand(node, problem) do 
      result <- Recursive-DLS(successor, problem, limit)
      if result = cutoff then cutoff_occurred? <- true
      else if result != failure then return  рішення result
      if cutoff_occurred?
       then return індикатор невдачі cutoff
         else return індикатор невдачі failure
            

Не рекурсивна реалізація Pascal

uses crt;
var graph:array[1..100,1..100] of integer; 
    n:integer; 
    fin:text; 
    fout:text;
    nnew:array[1..100] of boolean; 
    st:array[1..100] of integer;
    fres:text; 
 
procedure CheckGraph; 
var i,j:integer;
begin
        for i:=1 to n do
        for j:=1 to n do
        begin
                if graph[i,j]>1 then 
                 graph[i,j]:=1; 
                if graph[i,j]<0 then 
                 graph[i,j]:=0; 
                if ((i=j) and (graph[i,j]<>0)) then 
                 graph[i,j]:=0; 
        end;
end;
 
procedure ShowGraph; 
var i,j:integer;
begin
        Clrscr;
        Writeln('The graph you inputed is:');
        for i:=1 to n do
        begin
                Writeln;
                Write(i,' | ');
                for j:=1 to n do
                Write (graph[i,j]:2,' '); 
        end;
        ReadKey;
end;
 
procedure Input;
var ch:char; 
    cod:byte; 
    fname:string; 
    i,j:integer;
begin
        repeat
        Clrscr;
        Writeln('Choose the source');
        Writeln('1. Keyboard');
        Writeln('2. File');
        Readln(ch);
        if ch='1' then 
        begin
                Writeln('How many edges are in the graph?');
                Readln(n);
                while ((n<0) or (n>100)) do 
                begin
                        if n<0 then 
                         Writeln('The number of edges must be positive. Try again');
                        if n>100 then 
                         Writeln('Top much edges! Try again');
                        Readln(n);
                end;
                for i:=1 to n do
                for j:=1 to n do
                begin
                        Writeln(i,'-',j,': '); 
                        Readln(graph[i,j]); 
                end;
                CheckGraph; 
                ShowGraph;      
           end;
 
        if ch='2' then 
        begin
                Writeln('The name of file is:'); 
                Readln(fname);
                Assign(fin, fname);
                {$I-}
                Reset(fin);
                {$I+}
                cod:=IOResult;
                while cod<>0 do
                begin
                        Writeln('I cannot find a file ',fname,'    Choose another file');
                        Readln(fname);
                        Assign(fin, fname);
                        {$I-}
                        Reset(fin);
                        {$I+}
                        cod:=IOResult;
                end;
                Readln(fin, n);
                for i:=1 to n do
                        for j:=1 to n do
                        Read(fin,graph[i,j]);
                CheckGraph;
                ShowGraph;
                close(fin);
        end;
        until ((ch='1') or (ch='2'));
end;
 
procedure ShowRes; 
var i:integer;
begin
        Assign(fres, 'results.txt');
        Rewrite(fres);
        for i:=1 to n do
        begin
        Writeln(fres,st[i]);
        Writeln(st[i]);
        end;
        close(fres);
end;
 
procedure WriteToLog(a:integer); 
var i:integer;
begin
Writeln(fout, 'Current edge: ',a);
for i:=1 to n do
        Write(fout, nnew[i]:5,' ');
Writeln(fout);
end;
 
procedure Pgn(v:integer); 
var yk,t,j,k:integer;
    stt:array [1..100] of integer;
    pp:boolean; 
begin
        Assign(fout, 'log.txt');
        Rewrite(fout);
        yk:=1; 
        k:=1; 
        st[yk]:=v;
        stt[yk]:=v;
        nnew[v]:=false;
        while (yk<>0) do 
        begin
                t:=stt[yk]; 
                j:=1;
                pp:=false;
                WriteToLog(t);
        repeat
        if ((graph[t,j]=1) and (nnew[j]=false)) then
                pp:=true
        else
                j:=j+1;
        until ((pp=true) or (j>n)); 
        if (pp=true) then
        begin
                yk:=yk+1;
                nnew[t]:=true; 
                k:=k+1;
                st[k]:=j;
                stt[yk]:=j;
        end
        else 
        begin
                nnew[t]:=true;
                yk:=yk-1; 
        end;
        end;
        close(fout);
end;
 
procedure DFS; 
var v:integer;
begin
        Writeln;
        Writeln('Enter the number of edge, wherefrom to start depth search');
        Readln(v);
        while((v<0) or (v>n)) do 
        begin
                Writeln('There is no such edge in the graph. Try again');
                Readln(v);
        end;
        Pgn(v);
end;
 
begin 
Input;
DFS;
ShowRes;
Readln;
end.

Властивості

Просторова складність

Оскільки пошук з обмеженням глибини використовує пошук в глибину, то просторова [[Обчислювальна складність|складність] еквівалентна складності звичайного пошуку в глибину і вона складає $O(|V|)$. Ємкісна складність - O (b * L) .

Часова складність

Оскільки пошук з обмеженням глибини використовує пошук в глибину, то часова складність еквівалентна складності звичайного пошуку в глибину і вона складає O($\vert V \vert + \vert E \vert$), де $\vert V \vert$ — кількість вершин, $\vert E \vert$ — кількість ребер в досліджуваному графі. Зверніть увагу, що пошук з обмеженням глибини досліджує не весь граф, а тільки ту частину, яка розташована в межах вказаної глибини.

Повнота

Незважаючи на те, що алгоритм пошуку з обмеженнями глибини не може створювати нескінченно довгі шляхи і не може застрявати в циклах, в цілому алгоритм не є повним, оскільки він не знаходить рішення, яке лежить за межами даної глибини пошуку. Але якщо максимальна глибина пошуку обрана більше глибини рішення, алгоритм стає повним.

Оптимальність

Пошук з обмеженням глибини не є оптимальним. Ця модифікація зберігає проблему пошуку в глибину: алгоритм спочатку досліджує один шлях до кінця, що може привести до знаходження рішення, що коштує дорожче, ніж деякі рішення в інших шляхах.

Недоліки алгоритму

Недоліки методу - необхідність знати оцінку складності задачі. Якщо встановлена межа глибини буде занадто великою, це призведе до зайвих затрат ресурсів на пошук, якщо занадто малою - ціль не буде досягнута!

Література

• Стюарт Рассел, Питер Норвиг Искусственный интеллект: современный подход. — М.: Вильямс, 2007. С. 1424. ISBN 0-13-790395-2
• И.А. Бессмертный ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
• Н.В. Лукьянова, Д.Ю. Куприянов, Н.А. Роганова ОСНОВЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Див. також

• Список алгоритмів
• Пошук у глибину
• Обхід дерева