Неинформированный метод поиска — Википедия
Неинформи́рованный по́иск (также слепой поиск, метод грубой силы, англ. 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 2 3 4 5 6 7 Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд. — М.: Вильямс, 2006. — 1408 с. — ISBN 5-8459-0887-6. Архивировано 28 февраля 2011 года.
- ↑ Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
- ↑ Brute-force search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
- ↑ Breadth-First Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
- ↑ Поиск в ширину в графе и его приложения . MAXimal :: algo. Дата обращения: 30 июля 2013. Архивировано 16 сентября 2013 года.
- ↑ Uniform-Cost Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
- ↑ Ariel Felner. Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm. — 2011.
- ↑ Depth-First Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
- ↑ 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.
- ↑ Depth-First Iterative Deepening (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
- ↑ Bidirectional Search (англ.). Articles on artificial intelligence. Дата обращения: 30 июля 2013. Архивировано 29 августа 2013 года.
Литература
[править | править код]- Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд. — М.: Вильямс, 2006. — 1408 с. — ISBN 5-8459-0887-6.
- Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
- Richard E. Korf. Artificial Intelligence Search Algorithms. — 1998.