Неинформи́рованный по́иск (также слепой поиск , метод грубой силы , англ. uninformed search, blind search, brute-force search ) — стратегия поиска решений в пространстве состояний , в которой не используется дополнительная информация о состояниях, кроме той, которая представлена в определении задачи. Всё, на что способен метод неинформированного поиска, — вырабатывать преемников и отличать целевое состояние от нецелевого .

Алгоритмы

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

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

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

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

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

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 ). Узлы хранятся в очереди с приоритетом .

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

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

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

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

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

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

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 ) .

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

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 ) .

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} ) .

См. также

• Информированный метод поиска
• Поиск в пространстве состояний

Примечания

Литература

• Стюарт Рассел, Питер Норвиг. = Artificial Intelligence: A Modern Approach. — 2-е изд. — М. : Вильямс, 2006. — 1408 с. — ISBN 5-8459-0887-6 .
• Stefan Edelkamp, Stefan Schrödl. . — Morgan Kaufmann Publishers , 2012. — 712 с. — ISBN 978-0-12-372512-7 .
• Richard E. Korf. Artificial Intelligence Search Algorithms. — 1998.

Ссылки