Неинформированный метод поиска

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

Общее число выработанных узлов (временная сложность) равно O(bd+1), где b — коэффициент ветвления, d — глубина поиска. Пространственная сложность также равна O(bd+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(bl), а пространственная сложность — 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(bl)[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(bd/2). Проверка принадлежности узла, найденного обратным поиском, к периферии дерева прямого поиска может быть выполнена за постоянное время, поэтому временная сложность двунаправленного поиска определяется как O(bd/2)[1][9][11].

Примечания

[править | править код]
  1. 1 2 3 4 5 6 7 Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд. — М.: Вильямс, 2006. — 1408 с. — ISBN 5-8459-0887-6. Архивировано 28 февраля 2011 года.
  2. Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
  3. Brute-force search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
  4. Breadth-First Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
  5. Поиск в ширину в графе и его приложения. MAXimal :: algo. Дата обращения: 30 июля 2013. Архивировано 16 сентября 2013 года.
  6. Uniform-Cost Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
  7. Ariel Felner. Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm. — 2011.
  8. Depth-First Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
  9. 1 2 3 Korf, R.E. Depth-first iterative-deepening: An optimal admissible tree search (англ.) // Artificial Intelligence. — 1985. — Vol. Vol.27, no. 1. — P. 97—109. — doi:10.1016/0004-3702(85)90084-0.
  10. Depth-First Iterative Deepening (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
  11. Bidirectional Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.

Литература

[править | править код]