Пример решения задачи поиска в пространстве состояний

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

Если представить пространство поиска в игре в восемь в виде дерева, то – это глубина от первой вершины до n -й вершины. В качестве , можно, например, выбрать число шашек, стоящих не на своих местах. Стратегия прохождения вершин – по минимуму оценочной функции.

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

 

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

При реализации решения данной задачи на CLIPS необходимо будет создать шаблон ситуации игры:

(deftemplate Field

(slot LeftTop(type NUMBER))

(slot MiddleTop(type NUMBER))

(slot RightTop(type NUMBER))

(slot LeftMiddle(type NUMBER))

(slot MiddleMiddle(type NUMBER))

(slot RightMiddle(type NUMBER))

(slot LeftBottom(type NUMBER))

(slot MiddleBottom(type NUMBER))

(slot RightBottom(type NUMBER))

(slot Level(type NUMBER))

(slot Id(type NUMBER) (default 0))

(slot State(type NUMBER) (default 0))

(slot From (type NUMBER))

(slot Exp (type NUMBER))

)

Слоты LeftTop, MiddleTop, RightTop, LeftMiddle, MiddleMiddle, RightMiddle, LeftBottom, MiddleBottom и RightBottom являются ячейками игрового поля, в которых задаются номера соответствующих фишек. Если поле пустое, то значение соответствующего ему слота будет равно 0. Level – определяет число шагов от начальной ситуации к текущей. Id – уникальный номер состояния. State – определяет принадлежность данной ситуации множеству OPEN если значение 0, CLOSED – значение 1, если ситуация является промежуточной на пути к решению, то значение данному слоту будет присваиваться 2 (определяется, когда цель будет достигнута). From – Id ситуации, из которой возможен переход в данное состояние. Exp – значение целевой функции для данной ситуации.

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

(defglobal

?*Id* = 0

)

(deffunction Get_Id()

(bind?*Id* (+?*Id* 1))

?*Id*

)

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

(deffunction W(?Level?LeftTop?MiddleTop?RightTop?RightMiddle?RightBottom?MiddleBottom?LeftBottom?LeftMiddle)

(bind?a?Level)

(if (not (=?LeftTop 1)) then

(bind?a (+ 1?a))

)

(if (not (=?MiddleTop 2)) then

(bind?a (+ 1?a))

)

(if (not (=?RightTop 3)) then

(bind?a (+ 1?a))

)

(if (not (=?RightMiddle 4)) then

(bind?a (+ 1?a))

)

(if (not (=?RightBottom 5)) then

(bind?a (+ 1?a))

)

(if (not (=?MiddleBottom 6)) then

(bind?a (+ 1?a))

)

(if (not (=?LeftBottom 7)) then

(bind?a (+ 1?a))

)

(if (not (=?LeftMiddle 8)) then

(bind?a (+ 1?a))

)

?a

)

В базу фактов помещаем начальную ситуацию и инициализируем минимум:

(deffacts start

(min (W 0 2 8 3 4 5 0 7 1))

(Field (LeftTop 2) (MiddleTop 8) (RightTop 3)

(LeftMiddle 1) (MiddleMiddle 6) (RightMiddle 4)

(LeftBottom 7) (MiddleBottom 0) (RightBottom 5)

(Level 0) (From 0) (Exp (W 0 2 8 3 4 5 0 7 1)) (Id (Get_Id))

)

)

Далее необходимо создать правила для следующих действий:

1) Если решений найдено, то выделить его.

2) Удалить ситуации, которые не являются промежуточными между начальной и конечной ситуацией.

3) Останов программы если найдено решение или решений нет.

4) Удаление повторяющихся ситуаций.

5) Поиск min – минимального значения из значений целевой функции ситуаций множества OPEN.

6) Порождение новых всевозможных ситуаций из текущего, значение целевой функции которого равна min.

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

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

(defrule start_select_answer

(declare (salience 500))

?f<-(Field (LeftTop 1) (MiddleTop 2) (RightTop 3)

(LeftMiddle 8) (MiddleMiddle 0) (RightMiddle 4)

(LeftBottom 7) (MiddleBottom 6) (RightBottom 5) (State ~2) (From?Id))

=>

(modify?f(State 2))

)

 

(defrule select_answer

(declare (salience 500))

(Field (State 2) (From?Id))

?f<-(Field (Id?Id) (State ~2))

=>

(modify?f(State 2))

)

В первом правиле помечается ситуация, соответствующая конечной, а во втором с помощью значения в слоте From помеченной ситуации ищется непомеченная ситуация.

Если предыдущие правила не выполнимы и решение найдено, то необходимо удалить лишнее:

(defrule delete_not_answer

(declare (salience 400))

(Field (State 2))

?f<-(Field (State ~2))

=>

(retract?f)

)

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

Возможность останова программы реализуем в следующих правилах:

(defrule Stop_1

(declare (salience 200))

(not (Field(State 0|2)))

=>

(halt)

(printout t "no solutions" crlf)

)

 

(defrule Stop_2

(declare (salience 200))

(Field(State 2))

=>

(halt)

(printout t "fined solution" crlf)

)

Действия первого правила выполняются, если решение не найдено: в базе фактов нет ситуаций помеченных 0 или 2. Второе правило выполняется, если решение найдено.

Для удаления повторяющихся ситуаций создадим правило:

(defrule move_circle

(declare (salience 1000))

(Field (Exp?X))

?Field2<-(Field (Exp?Y&~?X))

(test (<?X?Y))

=>

(retract?Field2)

)

Обратите внимание на предпосылку (test (<?X?Y)), которая позволяет выбрать для удаления факт, целевая функция которого больше.

Для поиска минимального значения создадим правило, которое будет выполняться, когда будет существовать ситуация из множества OPEN у которой значение целевой функции меньше заданной в min:

(defrule find_min

(declare (salience 150))

?fmin<-(min?min)

(Field (Exp?E&:(<?E?min)) (State 0))

=>

(retract?fmin)

(assert (min?E))

)

Для порождения новых ситуаций создадим 9 правил, каждое из которых будет соответствовать местонахождению пустого поля. Так как принцип их реализации идентичный, рассмотрим одно из них (остальные правила см. в листинге 3):

(defrule make_new_path_RightBottom

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom 0) (Exp?E&:(=?E?min)))

=>

(modify?f(State 1))

(bind?a (W (+?L 1)?LT?MT?RT 0?RM?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle 0)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RM)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom 0) (RightBottom?MB)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RM?MB 0?LB?LM)) (Id (Get_Id))

)

)

)

В каждом правиле выполняются следующие действия:

· помечается выбранная ситуация как принадлежащая множеству CLOSED.

· создаются новые всевозможные ситуации.

· запоминается значение целевой функции одной из новых ситуаций (инициализация поиска min).

Полный текст программы приведен в листинге 4.

Листинг 4. Программа поиска решения для игры в «восемь»

;;задается шаблон в соответствии с квадратом 3x3

(deftemplate Field

(slot LeftTop(type NUMBER))

(slot MiddleTop(type NUMBER))

(slot RightTop(type NUMBER))

(slot LeftMiddle(type NUMBER))

(slot MiddleMiddle(type NUMBER))

(slot RightMiddle(type NUMBER))

(slot LeftBottom(type NUMBER))

(slot MiddleBottom(type NUMBER))

(slot RightBottom(type NUMBER))

(slot Level(type NUMBER));;задает уровень в дереве

(slot Id(type NUMBER) (default 0))

(slot State(type NUMBER) (default 0));;0 - не рассматривалось, 1 - рассмотрено 2 - соответствует решению

(slot From (type NUMBER))

(slot Exp (type NUMBER));;значение целевой функции

)

 

;глобальная переменная

(defglobal

?*Id* = 0

)

 

;целевая функция

(deffunction W(?Level?LeftTop?MiddleTop?RightTop?RightMiddle?RightBottom?MiddleBottom?LeftBottom?LeftMiddle)

(bind?a?Level)

(if (not (=?LeftTop 1)) then

(bind?a (+ 1?a))

)

(if (not (=?MiddleTop 2)) then

(bind?a (+ 1?a))

)

(if (not (=?RightTop 3)) then

(bind?a (+ 1?a))

)

(if (not (=?RightMiddle 4)) then

(bind?a (+ 1?a))

)

(if (not (=?RightBottom 5)) then

(bind?a (+ 1?a))

)

(if (not (=?MiddleBottom 6)) then

(bind?a (+ 1?a))

)

(if (not (=?LeftBottom 7)) then

(bind?a (+ 1?a))

)

(if (not (=?LeftMiddle 8)) then

(bind?a (+ 1?a))

)

?a

)

 

;;определяет идентификатор (чтобы можно найти элементы в последовательности)

(deffunction Get_Id()

(bind?*Id* (+?*Id* 1))

?*Id*

)

 

;;задаем начальное положение

(deffacts start

(min (W 0 2 8 3 4 5 0 7 1))

(Field (LeftTop 2) (MiddleTop 8) (RightTop 3)

(LeftMiddle 1) (MiddleMiddle 6) (RightMiddle 4)

(LeftBottom 7) (MiddleBottom 0) (RightBottom 5)

(Level 0);;это корень дерева

(From 0) (Exp (W 0 2 8 3 4 5 0 7 1)) (Id (Get_Id))

)

)

 

;;удаляем правила, которые встретились повторно

(defrule move_circle

(declare (salience 1000))

(Field (Exp?X));;первый факт

?Field2<-(Field (Exp?Y&~?X) (State 0));;второй факт

(test (<?X?Y));;удаляется ситуация, у которой целевая функция больше

=>

(retract?Field2)

(printout t "delete rule" crlf)

)

 

;;выбираем узлы из множества Open, и создаем соответствующие пути из него

;;для этого создается 9 правил с одинаковым приоритетом, что дает случайность

(defrule make_new_path_LeftTop

(declare (salience 100))

?fmin <- (min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop 0) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+ 1?L)?MT 0?RT?RM?RB?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?MT) (MiddleTop 0) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LM) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle 0) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LM?MT?RT?RM?RB?MB?LB 0)) (Id (Get_Id))

)

)

(printout t "LeftTop" crlf)

)

 

(defrule make_new_path_MiddleTop

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop 0) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+ 1?L) 0?LT?RT?RM?RB?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop 0) (MiddleTop?LT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MM) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle 0) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MM?RT?RM?RB?MB?LB?LM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?RT) (RightTop 0)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?RT 0?RM?RB?MB?LB?LM)) (Id (Get_Id))

)

)

(printout t "MiddleTop" crlf)

)

 

(defrule make_new_path_RightTop

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop 0)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+ 1?L)?LT 0?MT?RM?RB?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop 0) (RightTop?MT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RM)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle 0)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RM 0?RB?MB?LB?LM)) (Id (Get_Id))

)

)

(printout t "RightTop" crlf)

)

 

(defrule make_new_path_LeftMiddle

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle 0) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+ 1?L) 0?MT?RT?RM?RB?MB?LB?LT))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop 0) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LT) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?MM) (MiddleMiddle 0) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RT?RM?RB?MB?LB?MM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LB) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom 0) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RT?RM?RB?MB 0?LB)) (Id (Get_Id))

)

)

(printout t "LeftMiddle" crlf)

)

 

(defrule make_new_path_MiddleMiddle

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle 0) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+ 1?L)?LT 0?RT?RM?RB?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop 0) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MT) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?RM) (RightMiddle 0)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RT 0?RB?MB?LB?LM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MB) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom 0) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RT?RM?RB 0?LB?LM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle 0) (MiddleMiddle?LM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+ 1?L)?LT?MT?RT?RM?RB?MB?LB 0)) (Id (Get_Id))

)

)

(printout t "MiddleMiddle" crlf)

)

 

(defrule make_new_path_RightMiddle

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle 0)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+?L 1)?LT?MT 0?RT?RB?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop 0)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RT)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle 0) (RightMiddle?MM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?MM?RB?MB?LB?LM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RB)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom 0)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RB 0?MB?LB?LM)) (Id (Get_Id))

)

)

(printout t "RightMiddle" crlf)

)

 

(defrule make_new_path_LeftBottom

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom 0) (MiddleBottom?MB) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+?L 1)?LT?MT?RT?RM?RB?MB?LM 0))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle 0) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LM) (MiddleBottom?MB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?MB) (MiddleBottom 0) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RM?RB 0?MB?LM)) (Id (Get_Id))

)

)

(printout t "LeftBottom" crlf)

)

 

(defrule make_new_path_MiddleBottom

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom 0) (RightBottom?RB) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+?L 1)?LT?MT?RT?RM?RB?LB 0?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom 0) (MiddleBottom?LB) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle 0) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MM) (RightBottom?RB)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RM?RB?MM?LB?LM)) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?RB) (RightBottom 0)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RM 0?RB?LB?LM)) (Id (Get_Id))

)

)

(printout t "MiddleBottom" crlf)

)

 

(defrule make_new_path_RightBottom

(declare (salience 100))

?fmin<-(min?min)

?f<-(Field (State 0) (Level?L) (Id?Id)

(LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom 0) (Exp?E&:(=?E?min)))

=>

(printout t?min " " (fact-slot-value?f Exp) crlf)

(modify?f(State 1))

(bind?a (W (+?L 1)?LT?MT?RT 0?RM?MB?LB?LM))

(retract?fmin)

(assert (min?a))

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle 0)

(LeftBottom?LB) (MiddleBottom?MB) (RightBottom?RM)

(Level (+?L 1)) (From?Id) (Exp?a) (Id (Get_Id))

)

)

(assert (Field (LeftTop?LT) (MiddleTop?MT) (RightTop?RT)

(LeftMiddle?LM) (MiddleMiddle?MM) (RightMiddle?RM)

(LeftBottom?LB) (MiddleBottom 0) (RightBottom?MB)

(Level (+?L 1)) (From?Id) (Exp (W (+?L 1)?LT?MT?RT?RM?MB 0?LB?LM)) (Id (Get_Id))

)

)

(printout t "RightBottom" crlf)

)

 

(defrule find_min

(declare (salience 150))

;;приоритет ниже чем у правила исключающего циклы и выше чем у правил порождения новых ходов

?fmin<-(min?min)

(Field (Exp?E&:(<?E?min)) (State 0))

=>

(retract?fmin)

(assert (min?E))

)

 

;;если нашли решение, то выделяем его

(defrule start_select_answer

(declare (salience 500))

?f<-(Field (LeftTop 1) (MiddleTop 2) (RightTop 3)

(LeftMiddle 8) (MiddleMiddle 0) (RightMiddle 4)

(LeftBottom 7) (MiddleBottom 6) (RightBottom 5) (State ~2) (From?Id))

=>

(printout t "start select answer Id=" (fact-slot-value?f Id) crlf)

(modify?f(State 2))

)

 

(defrule select_answer

(declare (salience 500))

(Field (State 2) (From?Id))

?f<-(Field (Id?Id) (State ~2))

=>

(modify?f(State 2))

(printout t "select answer Id="?Id crlf)

)

 

;;удаляем остальные

(defrule delete_not_answer

(declare (salience 400))

(Field (State 2))

?f<-(Field (State ~2))

=>

(retract?f)

(printout t "delete not answer" crlf)

)

 

;;делаем останов если решений нет

(defrule Stop_1

(declare (salience 200))

(Field(State?x))

(not (Field(State 0|2)))

=>

(halt)

(printout t "no solutions" crlf)

)

 

;;делаем останов если решение есть

(defrule Stop_2

(declare (salience 200))

(Field(State 2))

=>

(halt)

(printout t "fined solution" crlf)

)

 

Варианты заданий

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

1. Трем миссионерам и трем каннибалам необходимо переправиться на другой берег реки. На берегу реки находится лодка (без гребца), которая может вместить не более 2-х человек. Необходимо организовать переправу так, чтобы ни на одном берегу количество каннибалов не превышало количество миссионеров.

2. Три рыцаря, каждый в сопровождении оруженосца, съехались на берегу реки, намереваясь переправиться на другую сторону. Им удалось найти двухместную лодку и переправа произошла бы легко, если бы не одно затруднение: все оруженосцы, словно сговорившись, наотрез отказались оставаться в обществе незнакомых рыцарей без своих хозяев. Необходимо организовать переправу, соблюдая условия оруженосцев.

3. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трех точек: или точку с координатами (x +3, y), или в точку с координатами (x, y +3), или в точку с координатами (x, y +4). Выигрывает игрок, после хода которого расстояния от фишки до точки с координатами (0, 0) не меньше 13 единиц. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

4. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (3, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трех точек: или в точку с координатами (x +3, y), или в точку с координатами (x, y +2), или в точку с координатами (x, y +4). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0, 0) больше 12 единиц. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

5. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (0, -5). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трех точек: или в точку с координатами (x +4, y), или в точку с координатами (x, y +4), или в точку с координатами (x +4, y +4). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0, 0) не меньше 13 единиц. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

6. Перед игроками лежат две кучи камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней становится не менее 17 камней. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

7. Перед игроками лежат две кучи камней, в первой из которых 6, а во второй – 5 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает или в 2 раза или в 3 раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится менее 48 камней. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

8. Перед двумя игроками лежат две кучи камней, в первой из которых 3, а во второй – 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого число камней в двух кучах становится не менее 24 камней. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

9. Даны три кучи камней, содержащих соответственно 2, 3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче (если их две – то в каждой из них), или добавить по 1 камню в каждую из всех трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

10. Перед игроками лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число камней в 2 раза, или добавляет в какую-то кучку 3 камня. Выигрывает тот игрок, после хода которого общее число камней в двух кучках становится не менее 23. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

11. Перед игроками лежат две кучки камней, в первой из которых 2, во второй – 3 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает число камней в какой-то куче в 3 раза, или добавляет 3 камня в любую из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 33. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

12. Даны две горки фишек, содержащих соответственно 2 и 4 фишки. За один ход разрешается или удвоить количество фишек в какой-нибудь горке, или добавить по две фишки в каждую из двух горок. Выигрывает тот игрок, после чьего хода в двух горках суммарно становится не менее 24 фишек. Игроки ходят но очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

13. Два игрока играют в следующую игру. Перед ними лежат две кучки фишек, в первой из которых 3, а во второй – 5 фишек. У каждого игрока неограниченно много фишек. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число фишек в 2 раза, или добавляет в какую-то кучку 2 фишки. Выигрывает тот игрок, после хода которого общее число фишек в двух кучках становится не менее 23. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

14. Даны три кучи камней, содержащих соответственно 3, 4, и 5 камней. За один ход разрешается или удвоить количество камней в меньшей куче (если таких две – то лишь в одной из них), или добавить 2 камня в большую из куч (если таких две – то лишь в одну из них). Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.

15. Имеются три колышка A, B, C, и n дисков разного размера, перенумерованных от 1 до n в порядке возрастания их размеров. Сначала все диски надеты на колышек A так, что диски меньшего размера находятся на дисках большего размера. Требуется перенести все диски с колышка A на колышек C соблюдая следующие условия: диски можно переносить только по одному, больший диск можно ставить на меньший.

16. Имеется n населенных пунктов, перенумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Определить, кратчайший путь из пункта x в пункт y (, ).