Методы поиска в одном пространстве

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

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

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

Игру в шахматы можно теоретически представить тройкой (S₀, F, S_T), где S ₀ – начальное состояние (расположение шахматных фигур на доске); S_T – множество заключительных состояний (расположений фигур, означающих мат или ничью); F – множество допустимых по шахматным правилам ходов, реализация каждого из которых преобразует текущее состояние (расположение фигур) в новое. Заключительные состояния множества S_T в шахматах явно перечислить невозможно, поэтому множество S_T можно лишь описать через свойства заключительных состояний (расположений фигур, означающих мат или ничью). Задача состоит в том, чтобы найти последовательность ходов (операторов), преобразующих S ₀ в одно из состояний (каждый из игроков желает свое) множества S_T. Описать процесс поиска можно с помощью графа, вершины которого соответствуют состояниям (шахматным позициям), а дуги – переходам из состояния в состояние под действием операторов (выполняемых ходов).

Аналогичным образом может быть описана игра в крестики-нолики. В этой игре позиция задается матрицей 3×3. Исходной позицией является пустая матрица. Два игрока (один из которых играет фишками Х, а другой 0) поочередно помещают свои фишки в свободные клетки матрицы. Цель игрока – установить в линию 3 своих фишки. Побеждает тот, кто это сделает первым. В этой игре, в отличие от шахмат, есть лишь один тип оператора – помещение фишки в клетку матрицы.

Методы поиска без информации дают решение задачи, но в процессе поиска создается слишком много вариантов. Поскольку на практике всегда существуют ограничения на время и память для реализации процесса поиска, такие методы оказываются весьма неэффективными. Поэтому не только в шахматах, но и в такой простой игре, как крестики-нолики, возникает вопрос о выборе наилучшего в данной позиции хода. Действительно, простейшая стратегия – перебрать все варианты продолжения игры и выбрать ход, соответствующий выигрышному варианту. Однако подсчитано, что в шахматах просмотр позиции лишь на 5 ходов вперед уже дает 10¹⁵ вариантов, а в такой простой игре, как крестики-нолики существует 362880 (9!) позиций, число которых за счет учета симметрии можно сократить до 60000, но это тоже немало. Поэтому вместо полного перебора вариантов используют стратегии с применением «эвристических правил», позволяющих существенно сократить объем перебора за счет снижения гарантии успешности поиска.

Информацию о задаче, которая позволяет сократить поиск решения, называют эвристической, а процедуры поиска, использующие ее, – методами эвристического поиска. Эвристическая информация используется таким образом, чтобы процесс поиска распространялся только по наиболее перспективным направлениям. Для применения эвристического поиска нужна оценка эффективности вариантов, которую обычно получают с помощью некоторой оценочной функции. Например, в игре крестики-нолики можно использовать достаточно простую оценочную функцию. Значение оценки доступных игроку ходов можно получить, подсчитывая число открытых игроку линий и вычитая число таких линий у противника при выборе того или иного хода. На рис. 4.3 приведен пример текущей позиции и варианты ходов игрока Х с их оценками. Наилучшим считается ход, дающий наиболшее значение разности числа открытых линий (в данном примере это вариант 3).

Ход 1: 4 - 4 = 0 Ход 2: 4 - 4 = 0 Ход 3: 4 - 3 = +1 Ход 4: 4 - 5 = -1

Рис. 4.3. Пример вычисления оценок ходов игрока Х
в игре крестики-нолики

Во второй главе было также рассмотрено применение концепции поиска в пространстве состояний на примере игры в 8, тоже ориентированное на использование эвристической оценочной функции эффективности ходов. Для вычисления «перспективности» вершин можно применить, например, следующую оценочную функцию. Обозначим эту функцию символом f. Тогда f (n) будет давать ее значение в вершине n дерева поиска. Будем считать, что вершина дерева с меньшей оценкой имеет большую вероятность оказаться на оптимальном пути. Тогда в качестве оценочной функции можно взять выражение f (n) = d (n) + W (n), где d (n) – глубина вершины n на дереве поиска и W (n) – число не находящихся на нужном месте клеток в базе данных, связанной с вершиной n. Таким образом, в процессе поиска варианты его продолжения следует рассматривать в порядке возрастания значения функции f (n). Использование этого правила будет способствовать сокращению среднего числа ходов, затрачиваемых на решение задачи.

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

Наиболее предпочтительным является случай, когда удается представить процесс решения сложной задачи в виде уже рассматривавшегося нами в разделе 4.2 дизъюнктивно-конъюнктивного дерева
(ДК-дерева), которое обычно изображается в форме графа с вершинами двух типов: & и . Конъюнктивная вершина (&) требует решения всех своих дочерних подзадач, дизъюнктивная же вершина () удовлетворяется решением хотя бы одной из дочерних подзадач. Цель поиска в этом случае состоит в нахождении при заданных условиях задачи «решающего подграфа» (части ДК-дерева, удовлетворяющей все его вершины типов & и ). На рис. 4.4 приведен абстрактный пример ДК-дерева, на котором жирными линиями выделен решающий подграф, представляющий собой тоже ДК-дерево.

Рис. 4.4. Пример ДК-дерева. Затененными вершинами и жирными ребрами выделен один из вариантов решающего подграфа

Смешивание дизъюнктивных и конъюнктивных вершин на одном уровне создает неудобства в организации поиска решения, поэтому часто в таких случаях в ДК-дерево вводят фиктивные ребра и вершины. Фиктивность таких вершин состоит в том, что для их выполнения не требуется решения каких-либо задач. По сути, они являют собой лишь логические операторы (например, в ДК-дерево на рис. 4.4 целесообразно ввести между вершиной S ₀ и вершинами S ₁ и S ₂ фиктивную вершину S ₁₀, роль которой сводится к констатации факта решения задач S ₁ и S ₂ и передаче сообщения об этом вершине S ₀). Обобщением этого подхода являются различные методы структурирования процессов решения задач, широко применяемые в программировании, но они не годятся для поиска в больших пространствах.

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

В идеальном случае генератор должен быть полным (т. е. порождать все варианты структур, могущие быть решением) и неизбыточным (т. е. не должен порождать вариантов структур, не могущих быть решением).

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

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

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