15 просмотров

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

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

  • Задача поиска состоит из:
    • Государственное пространство. Набор всех возможных состояний, в которых вы можете находиться.
    • Начальное состояние. Состояние, с которого начинается поиск.
    • Целевой тест. Функция, которая просматривает текущее состояние, возвращает значение независимо от того, является ли оно целевым состоянием.

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

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

    Категории алгоритмов поиска в ИИ

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

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

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

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

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

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

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

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

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

    Пример:

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

    запросы DFS

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

    Решение DFS

    Дорожка: С -> А -> В -> С -> Г

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

    Временная сложность: Эквивалентно количеству узлов, пройденных в DFS. Т (п) = 1 + п ^ 2 + п ^ 3 + . + п ^ д = О (п ^ д)
    Сложность пространства: Эквивалентно тому, насколько большой может быть бахрома. S (n) = O (n  раз d)
    Комплектность: DFS завершена, если дерево поиска конечно, то есть для заданного конечного дерева поиска DFS предложит решение, если оно существует.
    Оптимальность: DFS не является оптимальным, что означает, что количество шагов для достижения решения или стоимость, затраченная на его достижение, высоки.

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

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

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

    BFS вопросы

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

    BFS-решение

    Дорожка: С -> Д -> Г

    с = глубина самого мелкого решения.
    п^я = количество узлов на уровне я .
    Временная сложность: Эквивалентно количеству узлов, пройденных в BFS до самого поверхностного решения. Т (п) = 1 + п ^ 2 + п ^ 3 + . + п ^ с = О (п ^ с)
    Сложность пространства: Эквивалентно тому, насколько большой может быть бахрома. S (п) = О (п ^ с)
    Комплектность: BFS завершена, то есть для заданного дерева поиска BFS предложит решение, если оно существует.

    Оптимальность: BFS оптимальна, если стоимость всех ребер одинакова.

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

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

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

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

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

    проблема ПСК

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

    UCS-решение

    Дорожка: С -> А -> В -> Г
    Расходы: 5

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

    затем С / varepsilon = эффективная глубина

    Временная сложность: Т (п) = О (п ^ С ^/ ^  varepsilon) , космическая сложность: S (n) = O (n ^ C ^/ ^  varepsilon)

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

    • ПСК полна только в том случае, если состояния конечны и не должно быть петель с нулевым весом.
    • UCS оптимальна только в том случае, если нет отрицательной стоимости.

    Недостатки:

    • Исследует варианты в каждом «направлении».
    • Нет информации о местонахождении цели.

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

    Здесь алгоритмы имеют информацию о состоянии цели, что помогает в более эффективном поиске. Эта информация получена чем-то, что называется эвристика.
    В этом разделе мы обсудим следующие алгоритмы поиска.

    1. Жадный поиск
    2. A* Поиск по дереву
    3. A* Графический поиск

    Эвристика поиска: В информированном поиске эвристика – это функция который оценивает, насколько близко состояние к целевому состоянию. Например — манхэттенское расстояние, евклидово расстояние и т. д. (Меньше расстояние, ближе цель.) В разных информированных алгоритмах, обсуждаемых ниже, используются разные эвристики.

    Жадный поиск:

    В жадном поиске мы расширяем ближайший к целевому узлу узел. «Близость» оценивается эвристикой h(x).

    Эвристика: Эвристика h определяется как:
    h(x) = оценка расстояния узла x от целевого узла.
    Чем ниже значение h(x), тем ближе узел к цели.

    Стратегия: Разверните ближайший к целевому состоянию узел, то есть разверните узел с меньшим значением h.

    Пример:

    Вопрос. Найдите путь из S в G с помощью жадного поиска. Эвристические значения h каждого узла ниже имени узла.

    жадный алгоритм

    Решение. Начиная с S, мы можем перейти к A(h=9) или D(h=5). Мы выбираем D, так как он имеет меньшую эвристическую стоимость. Теперь из D мы можем перейти к B(h=4) или E(h=3). Мы выбираем E с более низкой эвристической стоимостью. Наконец, из E мы идем в G(h=0). Весь этот обход показан в дереве поиска ниже синим цветом.

    жадное решение

    Дорожка: С -> Д -> Е -> Г

    Преимущество: Хорошо работает с информированными проблемами поиска, с меньшим количеством шагов для достижения цели.
    Недостаток: В худшем случае может превратиться в неуправляемую DFS.

    A* Поиск по дереву:

    Поиск по дереву A*, или просто A* Search, сочетает в себе сильные стороны поиска с равномерной стоимостью и жадного поиска.В этом поиске эвристика представляет собой суммирование стоимости в UCS, обозначаемой g(x), и стоимости жадного поиска, обозначаемой h(x). Суммарная стоимость обозначается через f(x).

    е (х) = г (х) + ч (х)

    Эвристика: Следует отметить следующие моменты в отношении эвристики поиска A*.

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

    0 leqslant h(x) leqslant h^*(x)

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

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

    Пример:

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

    вопрос

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

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

    Дорожкач (х)г(х)е(х)
    С77
    С -> А9312
    С -> Д ✔527
    С -> Д -> Б ✔42 + 1 = 37
    С -> Д -> Э32 + 4 = 69
    С -> Д -> В -> С ✔23 + 2 = 57
    С -> Д -> В -> Е ✔33 + 1 = 47
    S -> D -> B -> C -> G5 + 4 = 99
    S -> D -> B -> E -> G ✔4 + 3 = 77

    Дорожка: S -> D -> B -> E -> G
    Расходы: 7

    A* Графический поиск:

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

    h(A) - h(B) leqslant g(A to B)

    Последовательность:

    Пример:

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

    вопрос поиска графа

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

    Дорожка: S -> D -> B -> E -> G
    Расходы: 7

    голоса
    Рейтинг статьи
    Статья в тему:  Как использовать искусственный интеллект для юридических компаний
Ссылка на основную публикацию
Статьи c упоминанием слов:

0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x