Создаем искусственный интеллект. Урок 3. Поиск решений задач в пространстве состояний.

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

В рассматриваемых ниже алгоритмах поиска используются два списка: список открытых вершин и список закрытых вершин. В списке открытых вершин (OPEN) находятся идентификаторы (имена) вершин, подлежащих раскрытию; в списке закрытых вершин (CLOSED) находятся имена вершин, раскрытых к данному моменту, и имя вершины, раскрываемой на текущем шаге работы алгоритма.

1. Методы «слепого» поиска.

Методы "слепого" поиска можно разделить на три группы:

• Случайный поиск;

• Поиск «в глубину и ширину»;

• Алгоритм равных цен.

Рассмотрим каждый метод в отдельности с примерами программ на псевдоязыке.

1). Случайный поиск.

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

Пример программы на псевдоязыке:

Procedure Random_Search;

Begin

       n := ’начальная вершина’;

       While n <> целевая вершина’ Do Begin

             Выбрать случайно оператор, применимый к ’n’;

             Применить данный оператор к ’n’ и получить новую вершину ’n_New’;

             n := n_New;

       End;

End.

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

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

2). Поиск «в глубину и ширину».

Данные методы исключают бесполезный повторный выбор одних и тех же вершин. Для этого с помощью списков CLOSED и OPEN ведется соответственно учет уже раскрытых вершин и вершин, подлежащих раскрытию. Кроме этого, задается определенный порядок (систематичность) обследования графа состояния, что позволяет последовательно пройти все маршруты по одному разу, без пропусков и повторений. Рассмотрим процедуру поиска в глубину:

Procedure Depth_First;

Begin

       Поместить начальную вершину в список OPEN;

       CLOSED := ’пустой список’;

       While OPEN <> ’пустой список’ Do Begin

             n := first(OPEN)

             If n = ’целевая вершина’ Then Выход(УСПЕХ);

             Переместить n из списка OPEN в CLOSED;

             Раскрыть вершину n и поместить все ее дочерние вершины, отсутствующие в списках OPEN и CLOSED, в начало списка OPEN, связав с каждой дочерней вершиной указатель на n;

       End;

       Выход(НЕУДАЧА);

End.

В начале поиска список CLOSED пустой, а OPEN содержит только начальную вершину. Каждый раз из списка OPEN выбирается для раскрытия первая вершина (вызов функции first(OPEN)). Раскрытая вершина перемещается в список CLOSED, а ее дочерние вершины помещаются в начало списка OPEN. Таким образом, на следующем шаге будут раскрываться дочерние вершины текущей вершины n. Принцип формирования списка OPEN в этом случае соответствует стеку, т.е. вершина, добавленная в список последней, обрабатывается первой (LIFO – Last In First Out). Если проследить направление поиска по дереву состояний, то фронт поиска растет в глубину. Для построения обратного пути (из целевой вершины в начальную вершину) все дочерние вершины снабжаются указателями на соответствующие родительские вершины.

Процедура поиска в ширину отличается от рассмотренной процедуры поиска в глубину тем, что дочерние вершины, получаемые при раскрытии вершины n, помещаются в конец списка OPEN. Следовательно, при поиске в ширину принцип формирования списка OPEN соответствует очереди, т.е. вершина, внесенная в список первой, обрабатывается первой (FIFO – First In First Out). Благодаря этому фронт поиска растет в ширину, что гарантирует нахождение пути с минимальным количеством дуг (ребер) между исходной и целевой вершинами (своего рода оптимальность).

3). Алгоритм равных цен.

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

где  – стоимость пути из начальной вершины в вершину .

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

Ниже представлена процедура поиска оптимального пути (минимальной стоимости), записанная на псевдоязыке:

Procedure Optimal_Search;

Begin

       Поместить начальную вершину в список OPEN;

       CLOSED := ’пустой список’;

       While OPEN <> ’пустой список’ Do Begin

            n := first(OPEN);

            If n = ’целевая вершина’ Then Выход(УСПЕХ);

Переместить n из списка OPEN в CLOSED;

Раскрыть вершину n, для каждой дочерней вершины / вычислить стоимость ;

Поместить дочерние вершины, которых нет в списке OPEN и CLOSED, в список OPEN,

связав с каждой вершиной указатель на вершину n и положить ;

Для каждой из дочерних вершин, которые уже содержаться в списке OPEN,

сравнить текущую стоимость  с ранее вычисленным значением стоимости ,

хранящемся в списке OPEN, если , то установить .

Снабдить указанные дочерние вершины указателями на вершину n;

Упорядочить список OPEN по возрастанию стоимости;           

End;

Выход(НЕУДАЧА);

End.

В тот момент, когда раскрывается некоторая вершина n, оптимальный путь к этой вершине уже найден, т.е. . Иными словами, если вершина уже находится в начале списка OPEN, то для нее невозможно найти более дешевого пути. Следовательно, перевод вершины в список CLOSED является окончательным.

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