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

 

 

 

Пример  выполнения:

 

Задание: Телефонная сеть между 5 городами задана БД (X,Y,стоимость 1 минуты). Определить может ли пользователь позвонить из одного заданного пункта в другой и в случае положительного ответа посчитать какое время пользователь может проговорить по телефону при условии наличия у него n у.е., а стоимости складываются при сложении путей.

 

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

 

В среде Visual Prolog 5.2 создан соответствующий проект .

 

Логика программы: решая задачи с графами в Prolog обычно придерживаются следующей рекурсивной идеи: для нахождения пути из A в Z если A и Z – смежные вершины, то путь найден, иначе нужно найти смежную с Z вершину Y и найти путь из A в Y (рисунок 13). Эту же идею можно использовать «с другой стороны»: для нахождения пути из A в Z если A и Z – смежные вершины, то путь найден, иначе нужно найти смежную с A вершину X и найти путь из X в Z.

Рисунок 13- Идея нахождения пути в Prolog

 

Для решения нашей задачи основной код может выглядеть  следующим образом (в предикате move первый аргумент – это точка отправления, второй – точка назначения, третий – список пройденного пути, четвертый – количество имеющихся денег, пятый – сумма стоимостей минут разговора; предикат is проверяет было ли уже вхождение данного пункта в искомый путь):

 

move(X,Y,T,K,L):-way(X,Y,F),L1=L+F,M=K/L1,

 term_str(real, M,M1), dlg_Note(" Доступные минуты  ", M1),!.

move(X,X,T,K,L):-M=K/L,term_str(real, M,M1),

dlg_Note("Доступные минуты  ",M1),!.

move(X,Y,T,K,L):-way(X,Z,F),not(is(Z,T)),L1=L+F,move(Z,Y,[Z|T],K,L1).

 

Имеющиеся данные о телефонной сети и стоимости переговоров  между пунктами описываются фактами way, в которых первые два аргумента отвечают за наименование пунктов, а третий за стоимость телефонных переговоров между ними (данные о телефонной сети необязательно хранить в коде самой программы, для удобства редактирования фактов имеет смысл использованить внешние базы данных). Пусть наша телефонная сеть описывается следующими фактами (рисунок 14):

 

way(a,b,5). way(b,d,7). way(a,c,6). way(b,c,4). way(c,d,9). way(d,e,10).

Рисунок 14-  Граф телефонной сети

 

Основной листинг программы  приведен ниже. Пример экранных форм программы  приведен на рисунок 15.

 

domains

CITY=a;b;c;d;e

R=CITY*

 

predicates

 

 dlg_mydialog_eh : EHANDLER

 dlg_mydialog_handle_answer(INTEGER EndButton,DIALOG_VAL_LIST)

 dlg_mydialog_update(DIALOG_VAL_LIST)

nondeterm way (CITY,CITY,integer)

nondeterm move(CITY,CITY,R, real,integer)

nondeterm is(CITY,R)

 

clauses

 

way(a,b,5).

way(b,d,7).

way(a,c,6).

way(b,c,4).

way(c,d,9).

way(d,e,10).

 

%BEGIN mydialog, idc_ok _CtlInfo

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

  X=win_GetCtlHandle(_Win,idc_begin),X1=win_GetText(X),term_str(CITY,X2,X1),

  Y=win_GetCtlHandle(_Win,idc_end),Y1=win_GetText(Y),term_str(CITY,Y2,Y1),

  Z=win_GetCtlHandle(_Win,idc_mon),Z1=win_GetText(Z),str_real(Z1,Z2),

  move(X2,Y2,[],Z2,0),!. 

move(X,Y,_,K,L):-way(X,Y,F),L1=L+F,M=K/L1,

 term_str(real, M,M1),dlg_Note(" Доступные минуты  ", M1),!.

move(X,X,_,K,L):-M=K/L,term_str(real, M,M1),dlg_Note(" Доступные минуты  ",M1),!.

move(X,Y,T,K,L):-way(X,Z,F),not(is(Z,T)),L1=L+F,move(Z,Y,[Z|T],K,L1).

 

is(X,[X|_]).

is(X,[A|Y]):-is(X,Y).

 

 

 

Рисунок 15- Экранные формы Prolog-программы

 

Вывод:

 

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

 

 

 

3.5 Построение экспертной системы

 

Цель:  Отработка практических навыков по построению экспертных систем в среде Visual Prolog 5.2

Задание: Создать приложение экспертной системы, предназначенное для поддержки принятия решения задачи выбранной предметной области.

 

Пример  выполнения:

 

Задание: Написать элементарную кулинарную экспертную систему.

 

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

 

В среде Visual Prolog 5.2 создан соответствующий проект. Экпертная система будет работать в двух режимах: режим экперта, в котором можно будет редактировать базу знаний и режим пользователя, в котором пользователь на основе имеющихся ингридиентов сможет определить какое блюдо ему лучше приготовить. Программе предусмотрена как работа со списками (раздел 9.3), так и работа с базами данных.

Основной листинг программы  приведен ниже. Пример экранных форм программы  приведен на рисунок 16-17.

 

database - expertdb

blyuda(string,ilist)

numProducts(integer)

products(integer,string)

temp1(string)

temp2(string)

 

predicates

 

products2idents(slist,ilist)

idents2products(ilist,slist)

sfirst(slist,string)

ifirst(ilist,integer)

isInclude(slist,string)

ask(slist)

logic(slist,iilist)

check(slist)

my_concat(slist,string)

 

clauses

 

products2idents([],[]):-!.

products2idents([Product|SList],[Ident|IList]):-retract(products(Ident,Product),expertdb),

assert(products(Ident,Product),expertdb),

products2idents(SList,IList),!.

idents2products([],[]):-!.

idents2products([Ident|IList],[Product|SList]):-retract(products(Ident,Product),expertdb),

assert(products(Ident,Product),expertdb),

idents2products(IList,SList),!.

sfirst([X|_],X):-!.

ifirst([X|_],X):-!.

isInclude([Elem|_],Elem):-!.

isInclude([_|List],Elem):-isInclude(List,Elem),!.

ask([]):-!.

ask([Product|List]):-concat("is there that product: \n      ",Product,Text),

Result=dlg_Ask(Text,["Yes","No"]),Result=resp_default,

assert(temp1(Product),expertdb),ask(List),!.

ask([_|List]):-ask(List),!.

logic([],_):-!.

logic([Blyudo|BList],[ProductsIdent|SList]):-idents2products(ProductsIdent,Products),

check(Products),assert(temp2(Blyudo),expertdb),

logic(BList,SList),!.

logic([_|List],[_|SList]):-logic(List,SList),!.

check([]):-!.

check([Product|List]):-temp1(Product),check(List),!.

my_concat([],""):-!.

my_concat([X|List],Result):-my_concat(List,Text1),

concat(X, "\n", Text2),

concat(Text2,Text1,Result),!.

 

 

dlg_window_add_blyudo_eh(_Win,e_Control(idc_close,_CtrlType,_CtrlWin,_CtlInfo),0):-

win_Destroy(_Win),!.

dlg_window_add_blyudo_eh(_Win,e_Create(_CreationData),0):-

findall(X,products(_,X),ProductList),

ListHandle=win_GetCtlHandle(_Win,idc_products),

lbox_Add(ListHandle,0,ProductList),!.

 

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_choosen_products,_CtrlType,_CtrlWin,selchanged),0):-lbox_GetSel(_CtrlWin,_,IList),

  ifirst(IList,Index),

   lbox_Delete(_CtrlWin,Index),!.

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_products,_CtrlType,_CtrlWin,selchanged),0):-

   lbox_GetSel(_CtrlWin,SList,_),

   sfirst(SList,Product),

   ProductsHandle=win_GetCtlHandle(_Win,idc_choosen_products),

   Products=lbox_GetAll(ProductsHandle),

   not(isInclude(Products,Product)),

   lbox_Add(ProductsHandle,0,Product),!.

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_products,_CtrlType,_CtrlWin,selchanged),0):-

   dlg_error("Уже выбран"),!.

 

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_add_blyudo,_CtrlType,_CtrlWin,_CtlInfo),0):-

HandleBlyudo=win_GetCtlHandle(_Win,idc_new_blyudo),

Blyudo=win_GetText(HandleBlyudo),

not(Blyudo=""),

not(blyuda(Blyudo,_)),

ListHandle=win_GetCtlHandle(_Win,idc_choosen_products),

ProductsList=lbox_GetAll(ListHandle),

products2idents(ProductsList,IdentList),

assert(blyuda(Blyudo,IdentList)),!.

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_add_blyudo,_CtrlType,_CtrlWin,_CtlInfo),0):- 

dlg_error("пустое значение"),!.

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_add_product,_CtrlType,_CtrlWin,_CtlInfo),0):-

HandleProduct=win_GetCtlHandle(_Win,idc_new_product),

Product=win_GetText(HandleProduct),

not(Product=""),

not(products(_,Product)),

retract(numProducts(Ident),expertdb),

Ident2=Ident+1,

assert(numProducts(Ident2),expertdb),

assert(products(Ident,Product)),

HandleProductList1=win_GetCtlHandle(_Win,idc_products),

HandleProductList2=win_GetCtlHandle(_Win,idc_choosen_products),

lbox_Add(HandleProductList1,Product),

lbox_Add(HandleProductList2,Product), !.

  dlg_window_add_blyudo_eh(_Win,e_Control(idc_add_product,_CtrlType,_CtrlWin,_CtlInfo),0):-

dlg_error("пустое значение "),!. 

 

 dlg_window_view_blyuda_eh(_Win,e_Create(_CreationData),0):-

findall(X,blyuda(X,_),BlyudaList),

ListHandle=win_GetCtlHandle(_Win,idc_blyuda),

lbox_Add(ListHandle,0,BlyudaList), !.

dlg_window_view_blyuda_eh(_Win,e_Control(idc_delete_blyudo,_CtrlType,_CtrlWin,_CtlInfo),0):-

ListHandle=win_GetCtlHandle(_Win,idc_blyuda),

   lbox_GetSel(ListHandle,SList,IList),

   not(Slist=[]),

   sfirst(SList,Blyudo),

   ifirst(IList,Index),

   retract(blyuda(Blyudo,_),expertdb),

   lbox_Delete(ListHandle,Index),!.

  dlg_window_view_blyuda_eh(_Win,e_Control(idc_delete_blyudo,_CtrlType,_CtrlWin,_CtlInfo),0):-

   dlg_error("Выберите блюдо"),!.

  dlg_window_view_blyuda_eh(_Win,e_Control(idc_view_products,_CtrlType,_CtrlWin,_CtlInfo),0):-

   ListHandle=win_GetCtlHandle(_Win,idc_blyuda),

   lbox_GetSel(ListHandle,SList,_),

   not(Slist=[]),

   dlg_window_view_products_Create(_Win), !.

 

dlg_window_view_products_eh(_Win,e_Create(_CreationData),0):-

_Parent=win_GetParent(_Win),

ListHandle=win_GetCtlHandle(_Parent,idc_blyuda),

   lbox_GetSel(ListHandle,SList,_),

   sfirst(SList,Blyudo),

   retract(blyuda(Blyudo,Idents),expertdb),

assert(blyuda(Blyudo,Idents),expertdb),

idents2products(Idents,Products),

ListHandle2=win_GetCtlHandle(_Win,idc_products),

lbox_Add(ListHandle2,0,Products), !.

dlg_window_user_eh(_Win,e_Destroy,0):-

save("expert.db",expertdb),!.

 

dlg_window_user_eh(_Win,e_Control(idc_blyuda,_CtrlType,_CtrlWin,selchanged),0):-

ListHandle=win_GetCtlHandle(_Win,idc_blyuda),

lbox_GetSel(ListHandle,SList,_),

sfirst(SList,Blyudo),

retract(blyuda(Blyudo,IdentProducts),expertdb),

assert(blyuda(Blyudo,IdentProducts),expertdb),

idents2products(IdentProducts,Products),

my_concat(Products,Text),

LabelHandle=win_GetCtlHandle(_Win,idct_explain),

concat("you can cook because of: \n",Text,ResultText),

win_SetText(LabelHandle,ResultText),!.

dlg_window_user_eh(_Win,e_Control(idc_ask,_CtrlType,_CtrlWin,_CtlInfo),0):-

retractall(temp1(_),expertdb),

retractall(temp2(_),expertdb),

findall(X,products(_,X),Products),

ask(Products),

findall(Y,blyuda(Y,_),Blyuda),

findall(Z,blyuda(_,Z),ListProducts),

logic(Blyuda,ListProducts),

findall(Y,temp2(Y),FoundBlyuda),

ListHandle=win_GetCtlHandle(_Win,idc_blyuda),

lbox_Clear(ListHandle),

lbox_Add(ListHandle,0,FoundBlyuda),!,

FoundBlyuda=[],

LabelHandle=win_GetCtlHandle(_Win,idct_explain),

win_SetText(LabelHandle, "no blyudo"),!.

 

Рисунок 16- Экранные формы созданной ЭС

 

 

Рисунок 17-Экранные формы созданной ЭС

 

 

 

3.6 Реализация  головоломки о Ханоской башне

 

Задание

 

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

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

 

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

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

1. переместить n-1 дисков с А на Б;
2. переместить нижний диск с номером n c A на В;
3. переместить n-1 диск с Б на В.

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