Алгоритмы поиска в AI

Искусственный интеллект - это исследование агентов, которые действуют рационально. В большинстве случаев эти агенты выполняют какой-то поисковый алгоритм в фоновом режиме для выполнения своих задач.

• Задача поиска состоит из:
  • Государственное пространство. Множество всех возможных состояний, в которых вы можете быть.
  • Состояние запуска. Состояние, с которого начинается поиск.
  • Тест цели. Функция, которая смотрит на текущее состояние, возвращает, является ли это целевым состоянием.
• Решение проблемы поиска - это последовательность действий, называемая планом, которая преобразует начальное состояние в целевое состояние.
• Этот план достигается за счет алгоритмов поиска.

Типы поисковых алгоритмов

Существует слишком много мощных поисковых алгоритмов, чтобы поместиться в одной статье. Вместо этого в этой статье будут обсуждаться шесть основных алгоритмов поиска, разделенных на две категории, как показано ниже.

Обратите внимание, что есть гораздо больше алгоритмов поиска, чем в приведенной выше диаграмме. Тем не менее, эта статья в основном будет придерживаться приведенной выше диаграммы, исследуя приведенные там алгоритмы.

Алгоритмы неинформированного поиска

Алгоритмы поиска в этом разделе не содержат дополнительной информации о целевом узле, кроме той, которая указана в определении проблемы. Планы достижения целевого состояния из начального состояния различаются только порядком и / или продолжительностью действий. Неинформированный поиск также называется слепым поиском .

В этом разделе обсуждаются следующие алгоритмы неинформированного поиска.

1. Поиск в глубину
2. Дыхание первым поиск
3. Единый поиск по стоимости

Каждый из этих алгоритмов будет иметь:

• Граф проблем, содержащий начальный узел S и целевой узел G
• Стратегия, описывающая способ обхода графа, чтобы добраться до G
• Бахрома, которая представляет собой структуру данных, используемую для хранения всех возможных состояний (узлов), к которым вы можете перейти из текущих состояний.
• Дерево, которое получается при переходе к целевому узлу.
• План решения , в котором последовательность узлов от S до G

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

Поиск в глубину (DFS) - это алгоритм обхода или поиска структур данных в виде дерева или графа. Алгоритм начинается с корневого узла (выбирая какой-либо произвольный узел в качестве корневого узла в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед отслеживанием с возвратом.

Пример:

Вопрос. Какое решение найдет DFS для перехода от узла S к узлу G если запустить его на графике ниже?

Решение. Эквивалентное дерево поиска для приведенного выше графа выглядит следующим образом. По мере того, как DFS проходит дерево «сначала самый глубокий узел», он всегда выбирает более глубокую ветвь, пока не достигнет решения (или у него не закончатся узлы, и он не перейдет к следующей ветви). Ход показан синими стрелками.

Путь: S -> A -> B -> C -> G

Позволять = глубина дерева поиска = количество уровней дерева поиска.
= количество узлов на уровне .

Сложность по времени: эквивалентна количеству узлов, пройденных в DFS.
Сложность пространства: эквивалентна тому, насколько большой может быть бахрома.
Полнота: DFS является завершенной, если дерево поиска конечно, то есть для данного конечного дерева поиска DFS предложит решение, если оно существует.
Оптимальность: DFS не является оптимальным, то есть количество шагов для достижения решения или затраты, затрачиваемые на его достижение, высоки.

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

Поиск в ширину (BFS) - это алгоритм для обхода или поиска структур данных в виде дерева или графа. Он начинается с корня дерева (или некоторого произвольного узла графа, иногда называемого «ключом поиска») и исследует все соседние узлы на текущей глубине, прежде чем перейти к узлам на следующем уровне глубины.

Пример:

Вопрос. Какое решение найдет BFS для перехода от узла S к узлу G если запустить его на графике ниже?

Решение. Эквивалентное дерево поиска для приведенного выше графа выглядит следующим образом. Поскольку BFS проходит дерево «сначала самый мелкий узел», он всегда будет выбирать более мелкую ветвь, пока не достигнет решения (или оно исчерпает все узлы и перейдет к следующей ветке). Ход показан синими стрелками.

Путь: S -> D -> G

Позволять = глубина самого мелкого решения.
= количество узлов на уровне .

Сложность по времени: эквивалентна количеству узлов, пройденных в BFS, до самого мелкого решения.
Сложность пространства: эквивалентна тому, насколько большой может быть бахрома.
Полнота: BFS завершена, что означает, что для данного дерева поиска BFS предложит решение, если оно существует.
Оптимальность: BFS оптимален, если стоимость всех ребер одинакова.

Единый поиск по стоимости

UCS отличается от BFS и DFS, потому что здесь в игру вступают затраты. Другими словами, обход по разным ребрам может иметь разную стоимость. Цель состоит в том, чтобы найти путь, по которому совокупная сумма затрат будет наименьшей.

Стоимость узла определяется как:

  стоимость (узел) = совокупная стоимость всех узлов от корня
  стоимость (корень) = 0

Пример:

Вопрос. Какое решение найдет UCS для перехода от узла S к узлу G если его запустить на графике ниже?

Решение. Эквивалентное дерево поиска для приведенного выше графа выглядит следующим образом. Стоимость каждого узла - это совокупная стоимость достижения этого узла из корня. На основе стратегии UCS выбирается путь с наименьшей совокупной стоимостью. Обратите внимание, что из-за множества опций в грани, алгоритм исследует большинство из них, пока их стоимость невысока, и отбрасывает их, когда найден путь с более низкой стоимостью; эти отброшенные обходы не показаны ниже. Фактический обход показан синим цветом.

Путь: S -> A -> B -> G
Стоимость: 5

Позволять = стоимость решения.
= стоимость дуг.

потом эффективная глубина

Временная сложность:
Космическая сложность:

Преимущества:

Поиск A * оптимален только тогда, когда для всех узлов прямая стоимость узла h(x) занижает фактическую стоимость h*(x) для достижения цели. Это свойство эвристики A * называется допустимостью .

Допустимость:

Стратегия: выберите узел с наименьшим значением f(x) .

Пример:

Вопрос. Найдите путь от S до G используя поиск A *.

Решение. Начиная с S , алгоритм вычисляет g(x) + h(x) для всех узлов в полосе на каждом шаге, выбирая узел с наименьшей суммой. Вся работа представлена в таблице ниже.

Обратите внимание, что в четвертом наборе итераций мы получаем два пути с равной суммированной стоимостью f(x) , поэтому мы расширяем их оба в следующем наборе. Путь с меньшими затратами на дальнейшее расширение - это выбранный путь.

Дорожка	h(x)	g(x)	f(x)
S	7	0	7
S -> A	9	3	12
S -> D ✔	5	2	7
S -> D -> B ✔	4	2 + 1 = 3	7
S -> D -> E	3	2 + 4 = 6	9
S -> D -> B -> C ✔	2	3 + 2 = 5	7
S -> D -> B -> E ✔	3	3 + 1 = 4	7
S -> D -> B -> C -> G	0	5 + 4 = 9	9
S -> D -> B -> E -> G ✔	0	4 + 3 = 7	7

Путь: S -> D -> B -> E -> G
Стоимость: 7

A * Поиск по графику

• Поиск * по дереву работает хорошо, за исключением того, что требуется время, чтобы повторно исследовать ветви, которые он уже исследовал. Другими словами, если один и тот же узел дважды расширялся в разных ветвях дерева поиска, поиск A * может исследовать обе эти ветви, таким образом теряя время.
• A * Graph Search, или просто Graph Search, снимает это ограничение, добавляя следующее правило: не расширять один и тот же узел более одного раза.
• Эвристический. Поиск по графу оптимален только тогда, когда прямые затраты между двумя последовательными узлами A и B , заданные как h(A) - h (B) , меньше или равны обратным затратам между этими двумя узлами g(A -> B). Это свойство эвристики поиска по графу называется согласованностью .
  Последовательность:

Пример

Вопрос. Используйте поиск по графу, чтобы найти путь от S до G на следующем графике.

Решение. Мы решаем этот вопрос почти так же, как и последний вопрос, но в этом случае мы отслеживаем исследованные узлы, чтобы не исследовать их повторно.

Путь: S -> D -> B -> C -> E -> G
Стоимость: 7

Рекомендации

• Слайды лекций CS 188
• AI: современный подход, 3e