Программирование на языке Prolog

Для простоты изложения рассмотрим решение задачи для n=3. Количество необходимых действий в этом случае равно 7. Необходимо предпринять следующие действия:

1. переместить 2 диска с А на Б. Поскольку по условию задачи нельзя перемещать за одно действие более одного диска, то первое действие сводиться к рекурсивному вызову решения задачи для n=2, при этом Б уже выступает как целевой стержень, а В - промежуточный:
1. перемещаем верхний диск с А на В;
2. перемещаем средний диск с А на Б;
3. перемещаем верхний диск с В на Б;
2. перемещаем нижний диск с А на В;
3. переместить 2 диска с Б на В. Аналогично действию № 1 данное действие своидиться к рекурсивоному решению задачи для n=2, при этом B – целевой стержень, а А – промежуточный:
1. перемещаем верхний диск с Б на А;
2. перемещаем средний диск с Б на В;
3. перемещаем верхний диск с А на В.

 

В консоли решение данной задачи может быть реализовано следующим  образом:

 

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):-write("\nДиск перемещается с стержня ", Loc1, " на стержень ", Loc2).

GOAL

  hanoi(5).

 

В Visual Prolog 5.2 cоздан проект Tower.pro.

Основной листинг проекта  Tower приведен ниже:

 

domains

  loc =right;middle;left

facts - coor

xy(loc,integer)%промежуточная БД свободного места по вертикали на стержнях

facts - d

n(loc,integer)%промежуточная БД со знанием номера самого верхнего диска на каждом стержне

facts - posx

ps(loc,integer)% координаты x

facts - coorxy

pol(integer,integer,integer)% координаты; 1-номер диска, 2-х,3-у

facts - locat

k(integer,integer,integer)% координаты; 1-номер диска, 2-х,3-у

 

predicates

 

  dlg_tower_eh : EHANDLER

  dlg_tower_handle_answer(INTEGER EndButton,DIALOG_VAL_LIST)

  dlg_tower_update(DIALOG_VAL_LIST)

 

nondeterm  move(integer,loc,loc,loc) % предикат для нахождения самого решения

nondeterm pick(WINDOW)% предикат для рисования

nondeterm coordin(loc,loc)% предикат для занесения в базы данных различных координат

nondeterm zapol(integer,integer,integer)% предикат для первоначального заполенения БД coor,coorxy,d

nondeterm proverka(string)% предикат на коректность ввода

 

clauses

ps(left,60).

ps(middle,260).

ps(right,460).

 

%BEGIN Tower, idc_push_button _CtlInfo

  dlg_tower_eh(_Win,e_Control(idc_push_button,_CtrlType,_CtrlWin,_CtlInfo),0):-!,

retractall(xy(_,_),coor),retractall(n(_,_),d),retractall(pol(_,_,_),coorxy),

retractall(k(_,_,_),locat),P=win_GetCtlHandle(_WIN,idc_d),  win_SetText(P,""),not(pick(_Win)),

WIN1=win_GetCtlHandle(_WIN,idc_ok),

win_SetState(WIN1,[wsf_Enabled]), !.

%END Tower, idc_push_button _CtlInfo

 

%BEGIN Tower, idc_ok _CtlInfo

  dlg_tower_eh(_Win,e_Control(idc_ok,_CtrlType,_CtrlWin,_CtlInfo),0):-!,

WIN1=win_GetCtlHandle(_WIN,idc_ok),win_SetState(WIN1,[wsf_Disabled]),% делаем данную кнопку выключенной

assertz(xy(left,240),coor),assertz(xy(middle,240),coor),assertz(xy(right,240),coor),

D=win_GetCtlHandle(_WIN,idc_d),  P=win_GetText(D), proverka(P),

 not(pick(_Win)),!.

%END Tower, idc_ok _CtlInfo

 

%BEGIN Tower, e_MouseDown

  dlg_tower_eh(_Win,e_MouseDown(_PNT,_ShiftCtlAlt,_Button),0):-!,

  k(C,B,D),retract(k(C,B,D),locat),

  pol(D,X,Y),retract(pol(D,X,Y),coorxy),assertz(pol(D,C,B),coorxy),

  not(pick(_Win)),!.

 dlg_tower_eh(_Win,e_Update(_UpdateRct),0):-!,  not(pick(_Win)), !.

 

proverka(A):-str_int(A,B),B>=1,B<=10,!,zapol(1,B,240), move(B,left,middle,right), !.

proverka(_):-dlg_MessageBox("Ошибка","Введите целое число от 1 до 10",2,0,0,0).

 

zapol(A,B,C):-A<=B,A1=A+1,asserta(n(left,A),d),assertz(pol(A,60,C),coorxy),

retract(xy(left,_),coor),C1=C-10,assertz(xy(left,C1),coor),zapol(A1,B,C1).

zapol(_,_,_):-!.

 

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

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

 

coordin(A,B):-xy(A,N),  N1=N+10,retract(xy(A,N),coor),assertz(xy(A,N1),coor),

xy(B,M),M1=M-10,retract(xy(B,M),coor),assertz(xy(B,M1),coor),

    n(A,F),retract(n(A,F),d),asserta(n(B,F),d),

    ps(B,H),assertz(k(H,M,F),locat).

pick(Win):-

   Pic=pict_getfromres(idb_yellow),

   pict_Draw(Win,Pic,pnt(0,80),rop_MergeCopy),

   Picture=pict_getfromres(idb_step),

   pict_Destroy (Pic),  % удаляем картинку из памяти

D1=win_GetCtlHandle(WIN,idc_d),  P=win_GetText(D1), str_int(P,P2),P2>=1,P2<=10,

pict_Draw(Win,Picture,pnt(60,100),rop_MergeCopy),

   pict_Draw(Win,Picture,pnt(260,100),rop_MergeCopy),

   pict_Draw(Win,Picture,pnt(460,100),rop_MergeCopy),

   pict_Destroy (Picture),

   P2>=1,pol(1,A1,B1),   

   Picture1=pict_getfromres(idb_disk1),

pict_Draw(Win,Picture1,pnt(A1,B1),rop_MergeCopy),

pict_Destroy (Picture1),

P2>=2,pol(2,A2,B2), 

   Picture2=pict_getfromres(idb_disk2),

   pict_Draw(Win,Picture2,pnt(A2,B2),rop_MergeCopy),

   pict_Destroy (Picture2),

   P2>=3,pol(3,A3,B3),

   Picture3=pict_getfromres(idb_disk3),

   pict_Draw(Win,Picture3,pnt(A3,B3),rop_MergeCopy),

   pict_Destroy (Picture3),

   P2>=4,pol(4,A4,B4),   

   Picture4=pict_getfromres(idb_disk4),

   pict_Draw(Win,Picture4,pnt(A4,B4),rop_MergeCopy),

   pict_Destroy (Picture4),

   P2>=5,pol(5,A5,B5),

   Picture5=pict_getfromres(idb_disk5),

   pict_Draw(Win,Picture5,pnt(A5,B5),rop_MergeCopy),

   pict_Destroy (Picture5),

   P2>=6,pol(6,A6,B6),

   Picture6=pict_getfromres(idb_disk6),

   pict_Draw(Win,Picture6,pnt(A6,B6),rop_MergeCopy),

   pict_Destroy (Picture6),

   P2>=7,pol(7,A7,B7),

   Picture7=pict_getfromres(idb_disk7),

   pict_Draw(Win,Picture7,pnt(A7,B7),rop_MergeCopy),

   pict_Destroy (Picture7),

   P2>=8,pol(8,A8,B8),

   Picture8=pict_getfromres(idb_disk8),

   pict_Draw(Win,Picture8,pnt(A8,B8),rop_MergeCopy),

   pict_Destroy (Picture8),

   P2>=9,pol(9,A9,B9),

   Picture9=pict_getfromres(idb_disk9),

   pict_Draw(Win,Picture9,pnt(A9,B9),rop_MergeCopy),

   pict_Destroy (Picture9),

   P2>=10,pol(10,A10,B10),

   Picture10=pict_getfromres(idb_disk10),

   pict_Draw(Win,Picture10,pnt(A10,B10),rop_MergeCopy),

   pict_Destroy (Picture10),

   P2>10.

 

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

• loc =right;middle;left  - описывает положение диска на одном из трех стержней (слева, посередине или справа).

В программе определены следующие  предикаты:

• move(integer,loc,loc,loc)  - предикат для нахождения самого решения. Первый аргумент – номер диска, остальные три аргумента – это три стержня
• pick(WINDOW) – предикат для отображения картинок. Аргумент - окно на которое производится отображение
• coordin(loc,loc) – предикат для обновление БД coor, d, locat. Первый аргумент – стержень, с которого взяли диск, второй аргумент – стержень, на который этот диск надели
• zapol(integer,integer,integer) – предикат для заполнения БД d, coorxy, coor первоначальными данными. Первый аргумент – номер диска, второй аргумент – общее количество дисков, третий – координаты расположения диска по оси OY
• proverka(string) – предикат для проверки на корректность значения, введенного пользователем. Аргумент – данные, введенные пользователем

В программе определены следующие  БД:

 

facts – coor

xy(loc,integer)

 

БД со знаниями о координатах  по оси OY свободного места на каждом стержне. Первый аргумент – название стержня, второй – координата

 

facts - d

n(loc,integer)

 

БД со знанием номера диска, который лежит на самом верху  каждого из стержней. Первый аргумент – название стержня, второй – номер  диска:

 

facts - posx

ps(loc,integer)

 

БД со знанием координат  по оси OX каждого из стержней. В процессе работы программы эта БД никак не обновляется. Первый аргумент – название стержня, второй – координата.

 

facts - coorxy

pol(integer,integer,integer)

 

БД со знанием координат  каждого диска. Первый аргумент –  номер диска, второй – координата по оси OX, третий – координата по оси OY

 

facts - locat

k(integer,integer,integer)

 

БД, в которой хранится информация о последовательности перемещения  дисков. Первый аргумент – номер  диска, второй – координата по оси  OX, третий – координата по оси OY

С помощью предиката proverka проверяется правильность введенного пользователем значения. В случае успеха с помощью предиката zapol заполняются базы данных первоначальными значениями (в БД d сохраняются данные о том, что все диски находятся на левом стержне, в БД coorxy сохраняются данные координат каждого диска, а в БД coor сохраняются ординаты свободного места для каждого из стержней). Далее управление передается предикату move, который собственно находит решение задачи и все необходимые данные сохраняет в промежуточной БД locat (с помощью предиката coordin). После всего этого вызывается предикат pick, который отвечает за отображение всех необходимых картинок на форме. При каждом нажатии на кнопку мыши обновляется БД coorxy с помощью БД locat и происходит вызов предиката pick. При нажатии на кнопку «Обновить» удаляются все данные из БД d, coor, coorxy, locat.

Созданная программа представлена на рисунок 19-21.

 

Рисунок 19 - Начало решения задачи

 

Рисунок 20 - Четвертый шаг решения

 

Рисунок 21 - Окончание решения

 

Список использованных источников

 

1. Лорьер Ж, Системы искусственного интеллекта/ Ж.Л. Лорьер.-М: Мир, 1990. – 345с.

2. Братко И. С, Программирование на языке Пролог для искусственного интеллекта/ И.С. Братко. - М: Мир,1990. – 456с.

3. Попов Э. В, Экспертные системы/ Э.В. Попов. - М: Наука, 1987. – 789с.

4. Марселлус Д, Программирование экспертных систем на Турбо Прологе/ Д. В. Марселлус. - М: Финансы и статистика, 1994.  – 434с.

5. Соломон Я, Программирование на Турбо Прологе/ Я. Соломон - М: Наука, 1994. - 234с.

6. Уотермен У, Руководство по экспертным системам / У. Уотермен -М: Мир, 1986. – 354с.

7. Гриб Д. Логический подход к искусственному интеллекту / Д. Гриб - М: Мир, 1985. – 345с.

8. Шапиро В.С. Искусство программирования на языке Пролог / В.С. Шапиро - М: Наука, 1985. – 451с.

9. Нейлор М. Как построить свою экспертную систему / М. Нейлор - М: Мир, 1992. – 287с.