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

Применение алгоритмов поиска ИИ для решения реальных проблем

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

Прежде чем углубляться в алгоритмы, во-первых, мы должны понять природу проблемы и некоторую связанную с ней терминологию. Как правило, проблема состоит из 04 основных компонентов, таких как состояния, действия/операции, цели, путь. Проще говоря, решение проблем можно определить как процесс, включающий преобразование набора состояний посредством действий или операций в цель по пути/путям.

Государственное пространство

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

Примечание: У проблемы может быть несколько целей, а также путей.

Проблема 01:

Для ясного понимания пространства состояний рассмотрим следующую задачу [рис. 2].

Представьте, что в комнате «А» (исходное состояние) есть робот, и ему нужно пройти в комнату «Z» (целевое состояние). Мы можем изобразить пространство состояний в виде дерева, если рассмотрим все возможные движения робота в каждой комнате (узле). Например, когда робот находится в начальном состоянии A, он может перейти либо в B, либо в D. Когда робот перешел в следующее состояние B, он может перейти в C, E или обратно в A [рис. 3].

Основываясь на всех возможных движениях робота в каждом состоянии, мы можем нарисовать пространство состояний для приведенного выше сценария следующим образом:

Мы можем определить множество путей помимо прямого пути A, B, C, Z.

Пример: А Б С Я 
А Б А Б С Я 
А Г Д Е Б В Я 
А Г Д Е Б А Б С Я 
. 

Можно заметить, что некоторые пути короче, а другие длиннее. Настоящая проблема возникает здесь. Мы можем определить лучший/кратчайший путь в случаях, подобных приведенному выше примеру, когда пространство состояний невелико. Но представьте себе пространство состояний с сотнями тысяч узлов. Как мы можем исследовать такое пространство состояний?

Решение — не что иное, как поисковые алгоритмы.В следующей главе мы обсудим 8 основных алгоритмов поиска в искусственном интеллекте.

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

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

Алгоритмы поиска бывают двух типов: алгоритмы неинформированного и информированного поиска [Рисунок 5]. Алгоритмы информированного поиска обеспечивают только систематический способ исследования пространства состояний, и никакой дополнительной информации для поддержки процесса поиска не предоставляется. Поиск в ширину, равномерный поиск, поиск в глубину, поиск с ограничением глубины, итеративный поиск с углублением и поиск в двух направлениях — это 06 основных алгоритмов неинформированного поиска.

С другой стороны, алгоритмы информационного поиска, такие как жадный поиск и алгоритмы поиска A*, основаны на дополнительной информации, которая делает процедуру поиска систематической и эффективной.

Примечание: Есть некоторые алгоритмы поиска ИИ, которые не подпадают ни под одну из вышеперечисленных основных категорий. Потому что есть проблемы, для решения которых не нужен конкретный путь, а важно, может ли процесс поиска прийти к целевому состоянию. Применяя поиск для таких задач, мы просто находим лучший доступный узел в окрестности (локальный поиск), либо ищем в конкурентной среде (состязательный поиск).

Пример: — Некоторые игры, такие как шахматы, восхождение на холмы, определенные проблемы с дизайном и планированием.

Алгоритм поиска, оценивающий критерии:

Существует 04 критерия, которые мы используем для оценки производительности каждого из упомянутых выше поисковых алгоритмов. Они есть:

1. Комплектность: Способность находить решение, когда оно есть (алгоритм не должен пропускать ни одного узла до достижения любого целевого узла/конца пространства состояний).
2. Оптимальность: Возможность найти решение самого высокого качества (алгоритм должен сначала найти целевые узлы на более мелком уровне).
3. Временная сложность: Сколько времени требуется алгоритму для обработки узлов. (Время выполнения алгоритма/процессорное время)
4. Сложность пространства: Сколько памяти используется алгоритмом для хранения узлов.

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

Проблема 02:

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

«Гимназии полны различных тренажеров с разной скоростью сжигания калорий. При выполнении упражнений важно покрывать все тело, а не часть тела. Выбор методов упражнений с наименьшим временем восстановления может сократить общее время, затрачиваемое на выполнение упражнения, а также любые повреждения тела. Поэтому важно выбрать правильный тренажер для сжигания целевых калорий, а также вовлечь все тело в процесс упражнений и с наименьшей склонностью к травмам. Сценарий основан на информации, приведенной в таблице 1, и пространстве состояний [рис. 6]».

Стоимость пути: Время, необходимое для сжигания 300 кал (минут)
Эвристическая ценность: Время восстановления, необходимое после сжигания 300 кал (минут)

Примечание: единицы стоимости пути и эвристических значений одинаковы.

На основе приведенной выше информации строится следующая диаграмма в пространстве состояний [Рисунок 6]. Это проблема с несколькими путями, но с одним целевым узлом. На следующей диаграмме также показаны стоимость пути и эвристические значения. Но обратите внимание, что дополнительная информация требуется только для определенных алгоритмов.На каждом пути покрыты участки всего тела (верхняя часть тела, средняя часть тела и нижняя часть тела).

Теперь мы обсудим особенности алгоритмов неинформированного и информированного поиска при их применении к указанному выше пространству состояний.

Примечание: Для реализации поиска обычно мы используем два списка для хранения узлов: ОТКРЫТЫЕ (узлы, которые нужно посетить/крайние) и ЗАКРЫТЫЕ (уже посещенные узлы).

Для демонстрации каждого алгоритма я использовал инструмент онлайн-моделирования: AI Search (ali-elganzory.github.io).

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

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

1.1 Поиск в ширину (BFS)

Как следует из названия, алгоритм BFS исследует пространство состояний слой за слоем (рис. 7). Когда мы исследуем узел, дочерние элементы всегда добавляются в конец списка OPEN. При удалении узлов из OPEN для добавления в CLOSED проверяем, является ли он целевым узлом, если да, то останавливается.

Дорожка: 0, 1, 5, 10, 13

Обход находится в списке ЗАКРЫТ. Но ОТКРЫТЫЙ список и ЗАКРЫТЫЙ список в целом вносят свой вклад в сложность пространства, поскольку общее количество узлов, хранящихся в памяти, является суммой ОТКРЫТЫХ и ЗАКРЫТЫХ списков.

Поскольку узлы за целевым узлом в списке OPEN не обрабатываются, временная сложность BFS связана только с количеством узлов в списке CLOSE. Поскольку пространство состояний исследуется слой за слоем, если есть решение, оно определенно найденный. Следовательно, BFS завершена. BFS оптимален, потому что целевые узлы на более мелком уровне находятся первыми.

В BFS сложность пространства для пространства состояний с коэффициентом ветвления «b» и уровнем, на котором найден целевой узел «d», равна О(бᵈ⁺¹). Временная сложность О(бᵈ) потому что, хотя память содержит узлы из «d+1», узлы после «d» не обрабатываются в BFS.

1.2 Поиск в глубину (DFS)

В DFS пространство состояний исследуется по ветвям в глубину. Он проверяет целевой узел вдоль каждой ветви.

Дорожка: 0, 4, 9, 12, 13

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

Удивительно, но DFS использует очень мало памяти. Он хранит узлы только вдоль ветви, поэтому на каждом уровне хранится минимальное количество узлов, в отличие от BFS, где все узлы хранятся на каждом уровне. В наихудшем сценарии, если максимальная глубина дерева поиска с коэффициентом ветвления «b» равна «m», тогда пространственная и временная сложности DFS равны О(бм) а также О(бᵐ) соответственно.

1.3 Поиск с ограничением глубины (DLS)

В DFS вы заметили, что это не оптимально, т. Е. Если цель присутствует на более мелком уровне, она не будет найдена первой. Что, если мы установим ограничение на глубину поиска? Это DFS, где мы можем установить предел глубины, чтобы поиск за пределами этого дерева не производился. Итак, если цель находится на более мелком уровне, то она быстро находится. Но что, если цель выходит за пределы установленного нами уровня? То же самое произошло и в нашем примерном сценарии [рис. 9]. Здесь глубина установлена ​​на уровне 3, но целевой узел находится на уровне 4, поэтому поиск никогда не сможет найти целевой узел.

Дорожка: Не найден

В DLS он не является ни полным, ни оптимальным, поскольку не все узлы в графе проверяются, и целевые узлы не могут быть эффективно найдены. Если мы установим предел глубины «l» для пространства состояний с коэффициентом ветвления «b», то пространственная и временная сложности DLS будут О(бл) а также О(бˡ), соответственно.

1.4 Итеративный поиск с углублением (IDS)

В IDS мы итеративно увеличиваем предел глубины и выполняем DFS до тех пор, пока не будет найден целевой узел. Использование DFS помогает сократить использование памяти для хранения узлов.И поскольку пространство состояний исследуется итеративно (послойно), если целевой узел находится на более мелком уровне (оптимальном), он сначала находится перед тем, как углубиться, и все узлы в слое проверяются полностью (полнота). .

Таким образом, IDS обладает преимуществом как DFS (за счет меньшего объема памяти), так и BFS (полноты и оптимальности), и устраняет проблемы, с которыми сталкивается DLS. Анимация ниже показывает обход пространства состояний в IDS [рис. 10].

Дорожка: 0, 4, 9, 12, 13

1.5 Двунаправленный поиск (BDS)

BDS применяется, если мы запускаем два одновременных алгоритма поиска BFS: один от «начального узла» к «целевому узлу» вперед, а другой — от «цели» к «началу» в обратном направлении, ожидая, пока два поиска встретятся друг с другом в середине. . из-за этого и временная, и пространственная сложности становятся в два раза больше половины этой BFS (что чрезвычайно меньше, чем O(бᵈ) БФС). Для графа с коэффициентом ветвления «b» и глубиной «d» пространственная и временная сложности BDS обозначаются как О(бᵈ/²).

Но BDS неприменим для ситуаций, подобных нашему примеру, когда некоторые дочерние узлы имеют несколько родителей (пример: узел-9 имеет узел-3 и узел-4 в качестве родительских узлов). Потому что алгоритм обратного поиска не может определить, за каким узлом следует следовать из нескольких родительских узлов.

1.6 Единый поиск стоимости (UCS)

В UCS каждому действию (ребру) от одного узла к другому присваивается значение. И каждый узел связан с общая стоимость пути который рассчитывается от «начального узла» до конкретного узла. В UCS вместо глубины учитывается общая стоимость пути.

Подобно BFS, мы расширяем узел с наименьшей стоимостью, а не самый мелкий узел в списке OPEN. Хотя в BFS перекрестными соединениями в графе пренебрегают, здесь они учитываются, поскольку каждому пути соответствует значение.

е (п) = г (п) 
 = Сумма (общая стоимость пути к каждому узлу от начального узла) 
= (Узел0-Узел1)+(Узел1-Узел6)+(Узел6-Узел10)+(Узел10-Узел13) 
= 10 + 15 + 10 + 11 
= 46 (стоимость пути)
Дорожка: 0, 1, 6, 10, 13 (Путь с наименьшей стоимостью пути)

Согласно нашему сценарию выше рассчитывается только путь с наименьшими затратами. На анимации [рис. 11] вы можете наблюдать, что обход очень похож на BFS, но с учетом стоимости. Таким образом, UCS является полным и оптимальным, а временные и пространственные сложности аналогичны BFS, которые О(бᵈ), а также О(бᵈ⁺¹), соответственно.

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

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

Бывший: Если вы путешествуете между двумя городами на машине, эвристикой будет уровень трафика. (Непосредственно стоимость пути будет расстоянием между двумя городами. Дополнительная информация, такая как перемещение и трафик между городами, рассматривается как эвристика)

В алгоритмах информированного поиска, чтобы найти лучший узел для следующего посещения, мы используем функция оценки ф (п) который помогает дочернему узлу решить, какой узел следует посетить следующим. Затем мы переходим к следующему узлу с наименьшее f(n) ценность. В зависимости от f(n) у нас есть два алгоритма информированного поиска: жадный поиск и алгоритмы поиска A*.

2.1 Алгоритмы жадного поиска

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

е (п) = ч (п) 
= Суммирование (эвристические значения узлов) 
= Узел0 + Узел2 + Узел7 + Узел11 + Узел13 
= 5 + 10 + 8 + 5 + 0 
= 28
Дорожка: 0, 2, 7, 11, 13

В жадном поиске вы можете видеть, что мы не посещаем все дочерние узлы определенного узла.Мы находим эвристику каждого дочернего узла, только тот с наименьшим значением вставляется в список OPEN для обработки. Поэтому жадный поиск не завершен. А также это не лучший путь (не самый короткий путь — мы нашли этот путь в поиске по единой стоимости). Поэтому жадный поиск также не является оптимальным. В качестве решения мы должны рассматривать не только эвристическое значение, но и стоимость пути. А вот и алгоритм A*.

2.2 Алгоритмы поиска A*

В алгоритме A* мы учитываем как стоимость пути, так и эвристику. В A* функция f(n) состоит из двух компонентов: стоимости пути [g(n)] и эвристического значения ([h(n)]. Значение f(n) для узла «a» можно рассчитать следующим образом:

f (n) ₐ = г (n) ₐ + h (n) ₐf (n) ₐ = значение оценки в конкретном узле (узел «a»)
g(n)ₐ = Общая стоимость пути от начального узла до определенного узла (узел 'a')
h(n)ₐ = эвристическое значение конкретного узла (узел 'a')

Теперь мы найдем лучший путь в соответствии с алгоритмом поиска A* для нашей предыдущей задачи. Мы должны найти значение f(n) для каждого узла и выбрать дочерний узел с наименьшим значением f(n) и пройти до достижения целевого узла. В примере упоминаются только значения f(n) целей на пути.

В узле-0: 
f(n)₀ = 0 + 5 = 5
В узле-3: 
f(n)₃ = 10 + 12 = 22
В узле-8: 
f(n)₈ = 30 + 10 = 40
В узле-11: 
f(n)₁₁ = 36 + 5 = 41
В узле-13: 
f(n)₁₃ = 46 + 0 = 46

f(n)ₜₒₜₐₗ = f(n)₀ + f(n)₃ + f(n)₈ + f(n)₁₁ + f(n)₁₃ = 154Дорожка: 0, 3, 8, 11, 13

Алгоритм A* завершен, так как он проверяет все узлы перед достижением целевого узла/конца пространства состояний. Это также оптимально, потому что, учитывая как стоимость пути, так и эвристические значения, поэтому самый низкий путь с самой низкой эвристикой может быть найден с помощью A *. Одним из недостатков A* является то, что он хранит все узлы, которые обрабатывает, в памяти. Следовательно, для пространства состояний с коэффициентом ветвления «b» и глубиной «d» пространственная и временная сложности A* обозначаются как О(бᵈ). Временная сложность A* зависит от эвристических значений.

Резюме сравнения алгоритмов поиска

Резюме каждого алгоритма информированного поиска можно резюмировать следующим образом.

Примечание: Все BFS, IDS, BDS (если алгоритм может применяться в обоих направлениях) и UCS являются полными, если коэффициент ветвления графа пространства состояний конечен. Если алгоритм можно применять в обоих направлениях, а стоимость шагов одинакова, то BDS завершена.

Вывод

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

При рассмотрении алгоритмов неинформированного поиска лучшим алгоритмом поиска с точки зрения полноты, оптимальности, временной и пространственной сложности является алгоритм двунаправленного поиска, если каждый дочерний узел в пространстве состояний имеет только один родительский узел. Но если дочерние узлы имеют больше, чем родительские узлы в пространстве состояний, двунаправленный поиск неприменим, и это алгоритм IDS, потому что он оптимален, полон, пространственная сложность находится в порядке (bm), а временная сложность — это алгоритм. порядок (bᵈ), который подобен другим.

Лучшим алгоритмом поиска является A*, потому что он оптимален, полон и использует дополнительную информацию (эвристику), поэтому решение лучше, чем у других алгоритмов.