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

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

Поиску в пространстве состояний - это математическая формулировка. Поиск пространства состояний очень общее. Любую задачу поиска можно свести к ней. Что это значит? Если принять во внимание системный подход, то вот есть некоторая система. Описывающая задачу этой системы - есть состояние. Система может переходить из состояния в состояние. Есть два выделенных состояния: начальное и целевое. В начальном состоянии, система находится в текущее время, в целевое она должна попасть. Задача поиска, как раз является обнаружение последовательности переходов изначального состояния в целевое. Давайте рассмотрим пару примеров. Первый - простой и даже банальный. Автономный автомобиль находится в такой-то точке на карте. В него садиться пассажир и дает задачу перевести его в новую точку. Начальным состоянием является то место, где автономный автомобиль стоит прямо сейчас. Соответственно, целевым состоянием, является точка назначения. Задачей поиска будет прокладка маршрута из начальной точки в целевую. Вот здесь возникает новый аспект. Вполне может существовать большое, или даже огромное количество, разных путей, изначально в стане целевой. И тут необходимо провести минимакс на оптимизацию. В условиях ограничений минимизации затрат получить максимальную выгоду. Другими словами, при решении задачи поиска, необходимо максимизировать выгоду и минимизировать затраченные ресурсы. При этом термины ресурсы и выгода понимаются в зависимости от конкретно решаемой задачи. В случае автономного автомобиля ресурсами будет время, затраченное на поездку, а выгодой безопасный проезд до назначенного места.

Второй пример: есть система для игры в крестики-нолики. В принципе, подойдет любая детерминированная игра с двумя игроками и полной информацией. То есть, шашки, шахматы, го и так далее. Рассмотрим крестики-нолики, потому что это простая игра и все знают, что это такое. В этом случае состоянием является вид поля для игры. Начальная стадия - все 9 сегментов пустые. Целевое состояние - 3 сегмента по вертикали, горизонтали или диагонали, заполнены фишками за которые играет ИИ-система. Также, конечными состояниями являются такие, в которых 3 сегмента в ряд заполнены чужими фишками - это называется проигрышем. А также такие, в которых все 9 сегментов заполнены, но 3 в ряд нет. И это называется ничьей. ИИ-система должна на каждом шаге своей игры, перестраивать свою стратегию так, чтобы выиграть или свести партию хотя-бы к ничьей. Проигрывать она не хочет. Это желание вполне можно формализовать в задачи поиска. И только она будет динамической, так как в процессе присутствует другой игрок. Но полное дерево ходов построить можно и по нему можно выстраивать стратегию игры. Так вот, при игре в крестики-нолики, если ИИ-система ходит первой, то она или выигрывает, или будет ничья. Если она ходит второй, то она не проигрывает. Другими словами крестики-нолики не интересная игра ИИ-система никогда не проиграет. Такими же играми являются все детерминированные игры с полной информацией.

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

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