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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Поиск с ограничением глубины»)
Перейти к: навигация, поиск

Неинформи́рованный по́иск (также слепой поиск, метод грубой силы, англ. 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.
  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. Архивировано 29 августа 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. pp. 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 года.

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

Ссылки[править | править код]