Интеллектуальные информационные системы

Содержание

 

 
1 Задание 3

2 Ход выполнения работы  4

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

 

 

Задание

 

Реализовать головоломку  о Ханойской башне: Имеется три  стержня. На левом стержне насажены несколько дисков разных диаметров. Диск с самым большим диаметром  находится в самом низу, а диск с самым маленьким диаметром на самом верху. Требуется переложить все диски в той же последовательности с левого стержня на правый, при этом за один ход можно со стрежня на стержень перетащить только один диск и диск большего диаметра нельзя класть на диск меньшего диаметра (рис. 1).

 

Рис. 1 - головоломка «Ханойская башня»

 

 

 

Ход выполнения

 

1. Условно обозначим стержень № 1 буквой  А, стержень № 2 – Б, стержень № 3 – В. Логика решения данной головомки: для перемещения n дисков с А на В используя промежуточный стержень Б нужно:
2. переместить n-1 дисков с А на Б;
3. переместить нижний диск с номером n c A на В;
4. переместить n-1 диск с Б на В.

Как видно из логики здесь возникает рекурсия. Решение задачи требует  действий, где n – количество дисков. Если предположить, что за 1 секунду будет произведено 100 действий, то, например, для решения задачи при n=50 понадобиться более 350 000 лет!

Для простоты изложения  рассмотрим решение задачи для 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. Этапы создания и редактирования проекта Visual Prolog описаны в разделах.

Основной листинг  проекта 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.

Созданная программа  представлена на рис. 2 - 4.

 

Рис. 2. - Начало решения задачи

 

Рис. 3. - Четвертый шаг решения

 

Рис. 4. - Окончание решения

 

 

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

 

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с.