Давайте продолжим исследовать методы и технологии Искусственного Интеллекта. И если на прошлых занятиях мы изучили обработку естественного языка и методы представления и обработки знаний, то сегодня у нас поиск и методы поиска. Это очень важно, так что давайте-ка посмотрим.
Фактически, поиск в довольно широком смысле — это нахождение траектории в некотором пространстве от текущего состояния к целевому. Это очень общее определение, так как и пространство поиска, и целевая функция могут быть произвольными. Для Искусственного Интеллекта очень важно уметь осуществлять поиск, поскольку поиск — это один из методов познания реальности, получения новых знаний.
Выделяются следующие типы поиска, которые имеют непосредственное отношение к методам Искусственного Интеллекта. Это — поиск в пространстве состояний, поиск пути, эвристический поиск и информационный поиск.
Эти типы поиска не являются взаимоисключающими. Это, скорее, именно типы поисковых алгоритмов, и некоторые из таких алгоритмов, к примеру, могут осуществлять информационный поиск при помощи эвристик случайного блуждания в пространстве состояний. Так что имеет смысл рассмотреть каждый тип, но принимая во внимание то, что некоторые алгоритмы могут обладать свойствами нескольких типов.
Сейчас я не буду давать вам детали по поисковым алгоритмам, поскольку одно только их перечисление заняло бы целый лонгрид, а по всем методам и алгоритмам поиска можно было бы создать отдельный курс. Но я кратко пробегусь по всем минимально необходимым понятиям, которые вам потребуются для работы и которые вы потом сможете самостоятельно изучить.
Поиск в пространстве состояний осуществляется для нахождения траектории системы в фазовом пространстве её состояний из некоторого начального состояния до целевого. Целевое состояние определяется при помощи предиката, реализующего алгоритм проверки, является ли заданное состояние целевым или нет (очевидно, что целевых состояний может быть несколько, и предикат описывает ту желательную конфигурацию системы, в которую она должна попасть в результате поиска). Поиск осуществляется при помощи использования двух функций — определения следующих возможных состояний для заданного и определения стоимости пути из одного состояния в другое.
Фактически, такая постановка задачи позволяет описать задачу поиска при помощи теории графов, когда состояниям системы соответствуют вершины графа, направленные рёбра графа — это возможность перехода из одного состояния в другое, а функция стоимости пути определяет веса на рёбрах. В таком представлении предикат целевых состояний определяет те вершины графа, в которые необходимо перейти из текущей. А функция стоимости пути, соответственно, позволяет минимизировать (если это возможно) сумму всех весов на обходимых рёбрах.
Из такой постановки задачи поиска в пространстве состояний понятно, что это задача оптимизации. Из этого с очевидностью следует, что решать её можно различными методами, имеющимися в арсенале теории оптимизации для решения задач на графах.
Для решения этой задачи разработано достаточное количество методов и алгоритмов, которые разделяются на информированные и неинформированные. Информированные методы поиска пользуются различными эвристиками, которые определяют дополнительную информацию о той задаче, которая решается. Это часто позволяет сократить перебор состояний системы и оптимизировать поиск. Но многие информированные методы зачастую применимы только для конкретных задач. В отличие от них неинформированные методы поиска, также называемые методами грубой силы, пользуются только информацией о том, как отличить целевое состояние от нецелевых. Фактически, различие в методах этой группы сводится к порядку перебора состояний в процессе поиска.
Неинформированные методы поиска подразделяются на следующие варианты: поиск с возвратом, поиск в ширину, поиск по критерию стоимости, поиск в глубину, поиск с ограничением глубины, поиск в глубину с итеративным углублением, двунаправленный поиск.
В свою очередь информированный поиск может вестись при помощи следующих алгоритмов: метод ветвей и границ, альфа-бета отсечение, поиск по первому наилучшему совпадению, алгоритм А*, алгоритм IDA*, алгоритм SMA*.
Конечно, я перечислил не все методы и алгоритмы поиска, разработанные к настоящему времени, но основные классы таких методов. В специализированных источниках можно найти описания более специализированных методов поиска обоих классов.
Перейдём к следующему типу поиска — поиску пути. Этот тип поиска крайне востребован в таких областях, как игровой Искусственный Интеллект и навигация, причём вторую область можно разделить на навигацию для человека (то есть построение оптимального маршрута от начальной точки до конечной с учётом возможных промежуточных) и для автономного интеллектуального агента, типа автономного автомобиля (фактически, то же самое, но с учётом дополнительных ограничений и нюансов функционирования такого агента). По своей сути алгоритмы поиска пути являются теми же самыми алгоритмами поиска на графах, только теперь граф представляет не отображение перехода между состояниями системы, а более конкретизированную вещь — отображение локаций и путей между ними в физической или виртуальной реальности.
Если граф пространства, в котором ищется путь, не слишком сложный, то можно воспользоваться алгоритмами поиска в пространстве состояний. Обычно для этих целей используется алгоритм A* с различными эвристиками, подбираемыми под конкретную задачу. Если пространство (географическая местность или виртуальное пространство) более сложные, то резонно воспользоваться специализированными алгоритмами.
В качестве интересных примеров таких алгоритмов можно отметить следующие: алгоритм Дейкстры и его расширения, волновой алгоритм, муравьиный алгоритм, методы динамического программирования.
Третий тип поиска — эвристический. Вообще, эвристика — это некоторый не совсем точный и практический алгоритм решения некоторой задачи, который не гарантирует точность или оптимальность решения, но вполне достаточный для достижения практического результата. Эвристики ускоряют решение задач там и тогда, когда точное аналитическое решение не может быть найдено или с практической точки зрения, или из-за фундаментальных ограничений. Другими словами, эвристический алгоритм является не полностью обоснованным математически, а иногда и вовсе некорректным, но при этом вполне полезным алгоритмом.
Эвристики обычно применяются там, где используются задачи высокой вычислительной сложности, при этом оценка стоимости применения точных алгоритмов (которых может и не существовать в принципе) существенно выше, чем стоимость применения эвристического алгоритма. Само собой разумеется, что эвристика и возможность её применения подбирается для каждой конкретной задачи. Но при этом эвристические алгоритмы вполне применимы и в других областях.
На этом спешу закончить. Сегодня мы здорово позанимались и узнали про виды поиска. И теперь мы готовы перейти к методам машинного обучения.