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

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

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

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

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

Поисковая терминология

• Проблемное пространство − Это среда, в которой происходит поиск. (Набор состояний и набор операторов для изменения этих состояний)
• Экземпляр проблемы − Это исходное состояние + Целевое состояние.
• График проблемного пространства − Представляет проблемное состояние. Состояния показаны узлами, а операторы показаны ребрами.
• Глубина проблемы − Длина кратчайшего пути или кратчайшей последовательности операторов от начального состояния до целевого состояния.
• Космическая сложность − Максимальное количество узлов, которые хранятся в памяти.
• Сложность времени − Максимальное количество создаваемых узлов.
• допустимость − Свойство алгоритма всегда находить оптимальное решение.
• Фактор ветвления − Среднее количество дочерних узлов в графе проблемного пространства.
• Глубина − Длина кратчайшего пути из начального состояния в целевое.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эвристические функции оценки

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

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

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

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

Поиск

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

f(n) = g(n) + ч(п), где

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

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

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

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

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

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

Поиск в горах

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

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

входы: проблема, проблема локальные переменные: текущий, сосед узла, узел текущий текущий если Value[neighbor] ≤ Value[current], то вернуть State[current] current 
Недостаток − Этот алгоритм не является ни полным, ни оптимальным.
Локальный поиск луча
В этом алгоритме он содержит k состояний в любой момент времени. В начале эти состояния генерируются случайным образом. Преемники этих k состояний вычисляются с помощью целевой функции. Если любой из этих преемников является максимальным значением целевой функции, то алгоритм останавливается.
В противном случае состояния (начальные k состояний и k последователей состояний = 2k) помещаются в пул. Затем пул сортируется по номерам. Высшие k состояний выбираются в качестве новых начальных состояний. Этот процесс продолжается до тех пор, пока не будет достигнуто максимальное значение.
функция BeamSearch( проблема, к.), возвращает состояние решения.
начать с k случайно сгенерированных состояний цикл сгенерировать всех преемников всех k состояний, если какое-либо из состояний = решение, затем вернуть состояние, иначе выбрать k лучших преемников end
Имитация отжига
Отжиг — это процесс нагревания и охлаждения металла с целью изменения его внутренней структуры для изменения его физических свойств. При охлаждении металла его новая структура схватывается, и металл сохраняет вновь обретенные свойства. В моделируемом процессе отжига поддерживается переменная температура.
Сначала мы устанавливаем высокую температуру, а затем позволяем ей медленно «охлаждаться» по мере выполнения алгоритма. Когда температура высока, алгоритм может принимать худшие решения с высокой частотой.
Инициализировать k = 0; L = целое число переменных;
От i → j найдите разницу в производительности Δ.
Если Δ random(0,1), то принять;
Повторите шаги 1 и 2 для L(k) шагов.
к = к + 1;
Повторяйте шаги с 1 по 4, пока критерии не будут соблюдены.
Задача коммивояжера
В этом алгоритме цель состоит в том, чтобы найти недорогой тур, который начинается в городе, посещает все города по пути ровно один раз и заканчивается в одном и том же начальном городе.
Начать Узнай все (n -1)! Возможные решения, где n — общее количество городов. Определите минимальную стоимость, узнав стоимость каждого из них (n -1)! решения. Наконец, оставьте тот, у которого минимальная стоимость. конец
   голоса
Рейтинг статьи