unit AIObj
Создаем искусственный интеллект. Урок 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
является окончательным.
Рассмотренная процедура поиска гарантирует нахождение пути минимальной
стоимости, если граф окончен и существует путь из начальной вершины в целевую
вершину. Однако сам процесс поиска не является оптимальным, так как поиск
выполняется без учета положения целевых вершин.
|