AI — популярные алгоритмы поиска

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

Проблемы с поиском одиночного агента

Игры типа 8X3 с восьмью ячейками, 4X4 с пятнадцатью ячейками и 5X5 с двадцатью четырьмя мозаичными головоломками — это задачи поиска одного агента. Они состоят из матрицы плиток с пустой плиткой. Игрок должен расположить плитки, сдвинув плитку вертикально или горизонтально в пустое пространство с целью достижения некоторой цели.

Другими примерами задач поиска пути одного агента являются задача коммивояжера, кубик Рубика и доказательство теорем.

Терминология поиска

• Проблемное пространство — это среда, в которой происходит поиск. (Набор состояний и набор операторов для изменения этих состояний)

• Экземпляр проблемы — это исходное состояние + состояние цели.

• Диаграмма пространства проблем — представляет состояние проблемы. Состояния показаны узлами, а операторы показаны ребрами.

• Глубина проблемы — длина кратчайшего пути или кратчайшей последовательности операторов от начального состояния до состояния цели.

• Сложность пространства — максимальное количество узлов, которые хранятся в памяти.

• Сложность времени — максимальное количество создаваемых узлов.

• Допустимость — свойство алгоритма всегда находить оптимальное решение.

• Коэффициент ветвления — среднее число дочерних узлов в графе проблемного пространства.

• Глубина — длина кратчайшего пути от исходного состояния до состояния цели.

Проблемное пространство — это среда, в которой происходит поиск. (Набор состояний и набор операторов для изменения этих состояний)

Экземпляр проблемы — это исходное состояние + состояние цели.

Диаграмма пространства проблем — представляет состояние проблемы. Состояния показаны узлами, а операторы показаны ребрами.

Глубина проблемы — длина кратчайшего пути или кратчайшей последовательности операторов от начального состояния до состояния цели.

Сложность пространства — максимальное количество узлов, которые хранятся в памяти.

Сложность времени — максимальное количество создаваемых узлов.

Допустимость — свойство алгоритма всегда находить оптимальное решение.

Коэффициент ветвления — среднее число дочерних узлов в графе проблемного пространства.

Глубина — длина кратчайшего пути от исходного состояния до состояния цели.

Стратегии поиска грубой силы

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

Требования —

• Описание состояния
• Набор действительных операторов
• Начальное состояние
• Описание состояния цели

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

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

Если коэффициент ветвления (среднее количество дочерних узлов для данного узла) = b и глубина = d, то количество узлов на уровне d = b ^d .

Общее количество созданных узлов в худшем случае равно b + b ² + b ³ +… + b ^d .

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

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

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

Он реализован в рекурсии со структурой данных стека LIFO. Он создает тот же набор узлов, что и метод Breadth-First, только в другом порядке.

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

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

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

Двунаправленный поиск

Он ищет вперед от исходного состояния и назад от целевого состояния, пока оба не встретятся, чтобы идентифицировать общее состояние.

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

Поиск единой стоимости

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

Он исследует пути в порядке возрастания стоимости.

Недостаток — может быть несколько длинных путей со стоимостью ≤ C *. Поиск равномерной стоимости должен изучить их все.

Итеративное углубление поиска в глубину

Выполняется поиск в глубину до уровня 1, начинается заново, выполняется полный поиск в глубину до уровня 2 и продолжается таким образом, пока не будет найдено решение.

Он никогда не создает узел, пока не будут созданы все нижние узлы. Это только сохраняет стек узлов. Алгоритм заканчивается, когда он находит решение на глубине d . Число созданных узлов на глубине d равно b ^d, а на глубине d-1 равно b ^d-1.

Сравнение сложности различных алгоритмов

Давайте посмотрим на производительность алгоритмов на основе различных критериев —

Информированные (эвристические) стратегии поиска

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

Функции эвристической оценки

Они рассчитывают стоимость оптимального пути между двумя государствами. Эвристическая функция для игр со скользящими плитками вычисляется путем подсчета количества ходов, которые каждая плитка делает из своего целевого состояния, и суммирования количества ходов для всех плиток.

Чистый эвристический поиск

Расширяет узлы в порядке их эвристических значений. Он создает два списка: закрытый список для уже развернутых узлов и открытый список для созданных, но нерасширенных узлов.

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

Поиск

Это самая известная форма поиска Best First. Он избегает расширения дорог, которые уже дороги, но в первую очередь расширяет наиболее перспективные.

f (n) = g (n) + h (n), где

• g (n) стоимость (пока) для достижения узла
• h (n) оценочная стоимость, чтобы добраться от узла до цели
• f (n) предполагаемая общая стоимость пути от n до цели. Это реализовано с использованием очереди приоритетов путем увеличения f (n).

Жадный Лучший Первый Поиск

Это расширяет узел, который оценивается как ближайший к цели. Он расширяет узлы на основе f (n) = h (n). Это реализовано с использованием очереди приоритетов.

Недостаток — он может застрять в петлях. Это не оптимально.

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

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

Поиск альпинизма

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

функция Hill-Climbing (задача), возвращает состояние, которое является локальным максимумом.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Недостаток — этот алгоритм не является ни полным, ни оптимальным.

Локальный Поиск Луча

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

В противном случае (начальные k состояний и k преемников состояний = 2k) состояний помещаются в пул. Затем пул отсортирован по номерам. Наивысшие k состояний выбираются в качестве новых начальных состояний. Этот процесс продолжается, пока не будет достигнуто максимальное значение.

функция BeamSearch ( problem, k ), возвращает состояние решения.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Имитация отжига

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

Сначала мы устанавливаем высокую температуру, а затем позволяем ей медленно «остывать» в процессе работы алгоритма. Когда температура высокая, алгоритм может принимать худшие решения с высокой частотой.

Начните

• Инициализировать k = 0; L = целое число переменных;
• Из i → j найдите разницу в производительности Δ.
• Если Δ <= 0, тогда примите другое, если exp (-Δ / T (k))> random (0,1), тогда примите;
• Повторите шаги 1 и 2 для шагов L (k).
• k = k + 1;

Повторите шаги с 1 по 4, пока критерии не будут выполнены.

Конец

Задача коммивояжера

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