|
Неинформированный метод поискаНеинформи́рованный по́иск (также слепой поиск, метод грубой силы, англ. 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]. См. такжеПримечания
Литература
Ссылки |
Portal di Ensiklopedia Dunia
