Основные стратегии решения задач. Поиск решения в пространстве состояний

Понятие пространства состояния

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

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

К таким задачам относятся следующие задачи:

· задача о восьми ферзях;

· переупорядочение кубиков, поставленных друг на друга в виде столбиков;

· головоломка «игра в восемь»;

· головоломка о «ханойской башне»;

· задача о перевозке через реку волка, козы и капусты;

· задача о двух кувшинах;

· задача о коммивояжере;

· другие оптимизационные задачи.

Со всеми задачами такого рода связано два типа понятий:

· проблемные ситуации;

· разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

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

Пространство состояний некоторой задачи определяет «правила игры»: вершины пространства состояний соответствуют ситуациям, а дуги – разрешенным ходам или действиям, или шагам решения задачи. Конкретная задача определяется:

· пространством состояний;

· стартовой вершиной;

· целевым условием или целевой вершиной.

Каждому разрешенному ходу или действию можно приписать его стоимость. Например, в задаче о коммивояжере ходы соответствуют переездам из города в город, ясно, что стоимость хода в данном случае – это расстояние между соответствующими городами.

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

В представленной в примере 57 программе о N ферзях проблемная ситуация (вершина в пространстве состояний) описывается в виде списка из N X-координат ферзей, а переход из одной вершины в другую генерирует предикат queens, причем начальная ситуация генерируется предикатом range, а целевая ситуация определяется при помощи предиката attack.

Основные стратегии поиска решений

Поиск в глубину

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

 

 

 

Порядок обхода вершин указан пунктирными стрелками, a – начальная вершина, j и f – целевые вершины.

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что обрабатывая цели, Пролог сам просматривает альтернативы именно в глубину.

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

Другой проблемой при описании пространства состояний является способ представления самих вершин, то есть самих состояний.

В качестве первого примера решения таких задач рассмотрим задачу о ханойских башнях. Есть три стержня и набор дисков разного диаметра. В начале игры все диски надеты на левый стержень. Цель игры заключается в переносе всех дисков на правый стержень по одному стержню за раз, при этом нельзя ставить диск большего диаметра на диск меньшего диаметра. Для этой игры есть простая стратегия:

1. Один диск перемещается непосредственно;

2. N дисков переносятся в 3 этапа:

· Перенести N-1 диск на средний стержень;

· Перенести последний диск на правый стержень;

· Перенести N-1 диск со среднего на правый стержень.

В программе на языке Пролог есть 3 предиката:

· hanoi – запускающий предикат, указывает сколько дисков надо переместить;

· move – описывает правила перемещения дисков с одного стержня на другой;

· inform – указывает на действие с конкретным диском.

Пример 58: решение задачи о ханойских башнях.

domains

loc=right;middle;left

% описывает состояние стержней

predicates

hanoi(integer)

% определяет размерность задачи

move(integer,loc,loc,loc)

% определяет переход из одной вершины пространства состояния в другую, то есть описывает правила перекладывания дисков

inform(loc,loc)

% распечатывает действия с дисками

clauses

hanoi(N):-move(N,left,middle,right).

move(1,A,_,C):-inform(A,C),!.

move(N,A,B,C):-N1=N-1, move(N1,A,C,B),

inform(A,C), move(N1,B,A,C).

inform(Loc1,Loc2):-nl, write(“Move a disk from “,Loc1,” to “, Loc2).

goal

hanoi(3).

Поиск в ширину

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

 

 

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

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

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

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

Одним из эвристических алгоритмов решения задач является алгоритм А*, который является усовершенствованным алгоритмом поиска в ширину. Это, так называемый, алгоритм поиска по заданному критерию. Для каждого возможного перехода за один шаг определяется эвристическая оценка и для продолжения поиска решающего пути выбирается наилучшая в соответствии с данной оценкой вершина.

Предполагается, что для всех дуг в пространстве состояний определена функция стоимости перемещения от вершины к вершинам-преемникам. Допустим, для эвристической оценки применяется функция f(n) такая, что для каждой вершины n она служит для оценки «сложности достижения n». Соответственно наиболее перспективной является та вершина, для которой значение функции f(n) является минимальным. Рассмотрим алгоритм А* на примере решения задачи «игра в восемь».

На следующем рисунке представлена задача «игра в восемь» в виде задачи поиска пути в пространстве состояний. В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующих матрицу 3х3. Одна из ячеек всегда пуста, любая смежная с ней фишка может быть передвинута в эту ячейку. Конечная ситуация – это некоторая заранее заданная конфигурация фишек.

 

 

 

При этом можно выделить четыре основных оператора:

1. Перемещение пустой фишки вниз;

2. Перемещение пустой фишки вверх;

3. Перемещение пустой фишки влево;

4. Перемещение пустой фишки вправо.

Оценочная функция f(n) формируется как стоимость оптимального пути к цели из начального состояния через n вершин дерева поиска. Значение оценочной функции для вершины n равно: f(n)=g(n)+h(n), где g(n) – стоимость оптимального пути от начальной вершины до n-ой, а h(n) – стоимость оптимального пути от n-ой вершины до целевой. Понятно, что h(n) это эвристическая гипотеза, основанная на имеющейся информации о данной конкретной задаче.

При этом g(n) принимается равной глубине пройденного пути на дереве поиска от начальной вершины до n-ой, а h(n) – расстояние Хемминга от n-ой вершины до целевой (в данном случае оно равно числу фишек, стоящих не на своих местах). Существует модификация алгоритма А*, в которой h(n) представляет сумму манхэттеновских расстояний (считается как сумма расстояний в горизонтальном и вертикальном направлениях) от каждой фишки до ёё «целевой клетки» плюс утроенное значение «оценки упорядоченности». Оценка упорядоченности определяет степень упорядоченности фишек текущей позиции по отношению к целевой позиции и высчитывается по следующим правилам:

· Фишка в центре имеет оценку 1;

· Фишка в другой позиции имеет оценку 0, если за ней в направлении по часовой стрелке следует соответствующий ей преемник;

· Фишка в другой позиции имеет оценку 2, если за ней в направлении по часовой стрелке не следует соответствующий ей преемник.

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

Формулировка алгоритма:

1. Рассматриваем все варианты перемещения пустой фишки за один шаг и выбираем вариант с минимальной оценкой h(n).

2. Переходим в новое состояние.

3. Создаём вершины следующего уровня иерархии.

4. Выбираем состояние с минимальной оценкой h(n).

5. Повторяем до тех пор, пока не достигнем цели.

Цель не будет достигнута до тех пор, пока число перемещений меньше числа фишек, находящихся не на своих местах.

Для исходного алгоритма оценочные стоимости вершин на первом шаге равны f(1)=n+h(1)=1+1=2 и f(2)=1+3=4, а на втором соответственно: f(3)=2+2=4 и f(4)=2+0=2. Последняя вершина является целевой.

В соответствии с модифицированным алгоритмом, от начальной вершины возможен переход в два состояния с оценочной стоимостью f(1)=n+h(1)=1+1+3*(1+2)=11 и f(2)=1+3+3*(1+2+2)=19. Выбираем минимальную стоимость и переходим в состояние 1. Далее генерируем вершины 3 и 4 с оценочными стоимостями соответственно f(3)=2+2+3*(1+2+2)=19 и f(4)=2+0=2. Последняя вершина является целевой.