WikiSort.ru - Программирование

Поиск в ширину

Поиск в ширину (breadth-first search, BFS) — это стратегия поиска решений в пространстве состояний, в которой вначале развёртывается корневой узел, затем — все преемники корневого узла, после этого развёртываются преемники этих преемников и т.д. Прежде чем происходит развёртывание каких-либо узлов на следующем уровне, развёртываются все узлы на данной глубине в дереве поиска.

Алгоритм является полным. Если все действия имеют одинаковую стоимость, поиск в ширину является оптимальным.

Общее число выработанных узлов (временная сложность) равно O(b^d+1), где b — коэффициент ветвления, d — глубина поиска. Пространственная сложность также равна O(b^d+1)^[1].

Реализация поиска в ширину может использовать очередь FIFO. В начале очередь содержит только корневой узел. На каждой итерации основного цикла из начала очереди извлекается узел curr. Если узел curr является целевым, поиск останавливается, в противном случае узел curr развёртывается, и все его преемники добавляются в конец очереди^[4][5].

function BFS(v : Node) : Boolean;
begin
  enqueue(v);

  while queue is not empty do
  begin
    curr := dequeue();

    if is_goal(curr) then
    begin
      BFS := true;
      exit;
    end;

    mark(curr);

    for next in successors(curr) do
      if not marked(next) then
      begin
        enqueue(next);
      end;
  end;

  BFS := false;
end;

Поиск по критерию стоимости

Поиск по критерию стоимости (метод равных цен, uniform-cost search, UCS) — обобщение алгоритма поиска в ширину, учитывающее стоимости действий (рёбер графа состояний). Поиск по критерию стоимости развёртывает узлы в порядке возрастания стоимости кратчайшего пути от корневого узла. На каждом шаге алгоритма развёртывается узел с наименьшей стоимостью g(n). Узлы хранятся в очереди с приоритетом^[6].

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

Процедура поиска по критерию стоимости может войти в бесконечный цикл, если окажется, что в ней развёрнут узел, имеющий действие с нулевой стоимостью, которое снова указыает на то же состояние. Можно гарантировать полноту и оптимальность поиска при условии, что стоимости всех действий строго положительны^[1].

Поиск по критерию стоимости логически эквивалентен алгоритму Дейкстры (англ. Dijkstra's single-source shortest-path algorithm). В частности, оба алгоритма развёртывают одни и те же узлы в одном и том же порядке. Основное различие связано с наличием узлов в очереди с приоритетом: в алгоритме Дейкстры все узлы добавляются в очередь при инициализации, а в алгоритме поиска по критерию стоимости узлы добавляются «на лету» (англ. on-the-fly, lazily) во время поиска. Из этого следует, что алгоритм Дейкстры применим к явно заданным графам, в то время как алгоритм UCS может быть применён как к явным, так и к неявным графам^[7].

Поиск в глубину

Поиск в глубину (depth-first search, DFS) — стратегия поиска решений в пространстве состояний, при которой всегда развёртывается самый глубокий узел в текущей периферии дерева поиска. При поиске в глубину анализируется первый по списку преемник текущего узла, затем — его первый преемник и т. д. Развёрнутые узлы удаляются из периферии, поэтому в дальнейшем поиск «возобновляется» со следующего самого поверхностного узла, который всё ещё имеет неисследованных преемников^[1].

Стратегия поиска в глубину может быть реализована с помощью стека LIFO или с помощью рекурсивной функции^[8].

function DFS(v : Node; depth : Integer) : Boolean;
begin
  if is_goal(v) then
  begin
    DFS := true;
    exit;
  end;

  for next in successors(v) do
    if DFS(next, depth + 1) then
    begin
      DFS := true;
      exit;
    end;

  DFS := false;
end;

Поиск с ограничением глубины

Поиск с ограничением глубины (depth-limited search, DLS) — вариант поиска в глубину, в котором применяется заранее определённый предел глубины l, что позволяет решить проблему бесконечного пути.

Поиск с ограничением глубины не является полным, так как при l < d цель не будет найдена, и не является оптимальным при l > d. Его временная сложность равна O(b^l), а пространственная сложность — O(b·l)^[1][9].

Поиск с ограничением глубины применяется в алгоритме поиска с итеративным углублением.

function DLS(v : Node; depth, limit : Integer) : Boolean;
begin
  if (depth < limit) then
  begin
    if is_goal(v) then
    begin
      DLS := true;
      exit;
    end;

    for next in successors(v) do
    begin
      if DLS(next, depth + 1, limit) then
      begin
        DLS := true;
        exit;
      end;
    end;
  end;

  DLS := false;
end;

Поиск в глубину с итеративным углублением

Поиск в глубину с итеративным углублением (iterative-deepening depth-first search, IDDFS, DFID) — стратегия, которая позволяет найти наилучший предел глубины поиска DLS. Это достигается путём пошагового увеличения предела l до тех пор, пока не будет найдена цель.

В поиске с итеративным углублением сочетаются преимущества поиска в глубину (пространственная сложность O(b·l)) и поиска в ширину (полнота и оптимальность при конечном b и неотрицательных весах рёбер).

Хотя в поиске с итеративным углублением одни и те же состояния формируются несколько раз, большинство узлов находится на нижнем уровне дерева поиска, поэтому затратами времени на повторное развёртывание узлов обычно можно пренебречь. Временная сложность алгоритма имеет порядок O(b^l)^[1][9][10].

function IDDFS(v : Node) : Integer;
var
  lim: Integer;
begin
  lim := 0;
  while not DLS(v, 0, lim) do
    lim := lim + 1;
  IDDFS := lim;
end;

Двунаправленный поиск

Двунаправленный поиск (bidirectional search) в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в том, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине.

Двунаправленный поиск может быть основан на стратегии итеративного углубления. Одна итерация включает в себя поиск на глубину k в прямом направлении и два поиска на глубину k и k + 1 в обратном направлении. Так как в памяти хранятся только состояния, найденные прямым поиском на глубине k, пространственная сложность поиска определяется как O(b^d/2). Проверка принадлежности узла, найденного обратным поиском, к периферии дерева прямого поиска может быть выполнена за постоянное время, поэтому временная сложность двунаправленного поиска определяется как O(b^d/2)^[1][9][11].