Поиск решения на графах пространства состояний

Автор: Пользователь скрыл имя, 21 Февраля 2012 в 17:17, курсовая работа

Описание работы

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

Скачать полностью (78.55 Кб) Сколько стоит заказать работу?
Работа содержит 1 файл

РЛП_РГЗ.doc

— 183.50 Кб (Скачать)

move(state([R1,R2,R3,b,R5],[O1,O2,O3,O4,O5],_),state([R1,R2,R3,r,R5],[O1,O2,O3,O4,O5],r)).

move(state([R1,R2,R3,R4,b],[O1,O2,O3,O4,O5],_),state([R1,R2,R3,R4,r],[O1,O2,O3,O4,O5],r)).

 

%Рыцарь высаживается из лодки на левый берег

move(state([b,R2,R3,R4,R5],[O1,O2,O3,O4,O5],_),state([l,R2,R3,R4,R5],[O1,O2,O3,O4,O5],l)).

move(state([R1,b,R3,R4,R5],[O1,O2,O3,O4,O5],_),state([R1,l,R3,R4,R5],[O1,O2,O3,O4,O5],l)).

move(state([R1,R2,b,R4,R5],[O1,O2,O3,O4,O5],_),state([R1,R2,l,R4,R5],[O1,O2,O3,O4,O5],l)).

move(state([R1,R2,R3,b,R5],[O1,O2,O3,O4,O5],_),state([R1,R2,R3,l,R5],[O1,O2,O3,O4,O5],l)).

move(state([R1,R2,R3,R4,b],[O1,O2,O3,O4,O5],_),state([R1,R2,R3,R4,l],[O1,O2,O3,O4,O5],l)).

 

%Оруженосец высаживается из лодки на правый берег

move(state([R1,R2,R3,R4,R5],[b,O2,O3,O4,O5],_),state([R1,R2,R3,R4,R5],[r,O2,O3,O4,O5],r)).

move(state([R1,R2,R3,R4,R5],[O1,b,O3,O4,O5],_),state([R1,R2,R3,R4,R5],[O1,r,O3,O4,O5],r)).

move(state([R1,R2,R3,R4,R5],[O1,O2,b,O4,O5],_),state([R1,R2,R3,R4,R5],[O1,O2,r,O4,O5],r)).

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,b,O5],_),state([R1,R2,R3,R4,R5],[O1,O2,O3,r,O5],r)).

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,b],_),state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,r],r)).

 

%Оруженосец высаживается из лодки на левый берег

move(state([R1,R2,R3,R4,R5],[b,O2,O3,O4,O5],_),state([R1,R2,R3,R4,R5],[l,O2,O3,O4,O5],l)).

move(state([R1,R2,R3,R4,R5],[O1,b,O3,O4,O5],_),state([R1,R2,R3,R4,R5],[O1,l,O3,O4,O5],l)).

move(state([R1,R2,R3,R4,R5],[O1,O2,b,O4,O5],_),state([R1,R2,R3,R4,R5],[O1,O2,l,O4,O5],l)).

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,b,O5],_),state([R1,R2,R3,R4,R5],[O1,O2,O3,l,O5],l)).

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,b],_),state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,l],l)).

 

%Рыцарь садится к своему оруженосцу

move(state([X,R2,R3,R4,R5],[b,O2,O3,O4,O5],B),state([b,R2,R3,R4,R5],[b,O2,O3,O4,O5],B)):-not(X=b),

              inboat([X,R2,R3,R4,R5],[b,O2,O3,O4,O5],Y),Y<2.

move(state([R1,X,R3,R4,R5],[O1,b,O3,O4,O5],B),state([R1,b,R3,R4,R5],[O1,b,O3,O4,O5],B)):-not(X=b),

              inboat([R1,X,R3,R4,R5],[O1,b,O3,O4,O5],Y),Y<2.

move(state([R1,R2,X,R4,R5],[O1,O2,b,O4,O5],B),state([R1,R2,b,R4,R5],[O1,O2,b,O4,O5],B)):-not(X=b),

              inboat([R1,R2,X,R4,R5],[O1,O2,b,O4,O5],Y),Y<2.

move(state([R1,R2,R3,X,R5],[O1,O2,O3,b,O5],B),state([R1,R2,R3,b,R5],[O1,O2,O3,b,O5],B)):-not(X=b),

              inboat([R1,R2,R3,X,R5],[O1,O2,O3,b,O5],Y),Y<2.

move(state([R1,R2,R3,R4,X],[O1,O2,O3,O4,b],B),state([R1,R2,R3,R4,b],[O1,O2,O3,O4,b],B)):-not(X=b),

              inboat([R1,R2,R3,R4,X],[O1,O2,O3,O4,b],Y),Y<2.

 

%Оруженосец садится к кому-то в лодку

move(state([R1,R2,R3,R4,R5],[X,O2,O3,O4,O5],B),state([R1,R2,R3,R4,R5],[b,O2,O3,O4,O5],B)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[X,O2,O3,O4,O5],Y),Y=1.

move(state([R1,R2,R3,R4,R5],[O1,X,O3,O4,O5],B),state([R1,R2,R3,R4,R5],[O1,b,O3,O4,O5],B)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,X,O3,O4,O5],Y),Y=1.

move(state([R1,R2,R3,R4,R5],[O1,O2,X,O4,O5],B),state([R1,R2,R3,R4,R5],[O1,O2,b,O4,O5],B)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,X,O4,O5],Y),Y=1.

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,X,O5],B),state([R1,R2,R3,R4,R5],[O1,O2,O3,b,O5],B)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,O3,X,O5],Y),Y=1.

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,X],B),state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,b],B)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,O3,O4,X],Y),Y=1.

 

%Оруженосец садится в пустую лодку

move(state([R1,R2,R3,R4,R5],[X,O2,O3,O4,O5],X),state([R1,R2,R3,R4,R5],[b,O2,O3,O4,O5],X)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[X,O2,O3,O4,O5],Y),Y=0.

move(state([R1,R2,R3,R4,R5],[O1,X,O3,O4,O5],X),state([R1,R2,R3,R4,R5],[O1,b,O3,O4,O5],X)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,X,O3,O4,O5],Y),Y=0.

move(state([R1,R2,R3,R4,R5],[O1,O2,X,O4,O5],X),state([R1,R2,R3,R4,R5],[O1,O2,b,O4,O5],X)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,X,O4,O5],Y),Y=0.

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,X,O5],X),state([R1,R2,R3,R4,R5],[O1,O2,O3,b,O5],X)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,O3,X,O5],Y),Y=0.

move(state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,X],X),state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,b],X)):-not(X=b),

              inboat([R1,R2,R3,R4,R5],[O1,O2,O3,O4,X],Y),Y=0.

 

inboat(R,O,N):-

length(R,0,N1),

length(O,0,N2),

              N=N1+N2.

length([],N,N):-!.

length([H|L],N,M):-

                            H=b,N1=N+1,

length(L,N1,M),!.

length([H|L],N,M):-

ength(L,N,M).

outpath([]):-!. %если передан пустой список, то работа предиката завершается

outpath([S|P]):-

              outpath(P), %для хвоста списка производиться

              assertz(path_db(S),db). %голова заносится в базу данных, т.о. состояния записываются в обратном порядке в базу данных

 

outbackground(Win):-

    Picture = pict_GetFromRes(idb_fon2), %загружает картинку из ресурсов

    pict_Draw(Win,Picture,pnt(0,0),rop_MergeCopy). %выводит ее на переданное ему окно

 

    %ПРОРИСОВКА позиций и перемешений на карте

    outitem(l,r1,Win):-

    Picture = pict_GetFromRes(idb_R1),

    pict_Draw(Win,Picture,pnt(30,68),rop_MergeCopy).

  outitem(r,r1,Win):-

    Picture = pict_GetFromRes(idb_R1),

    pict_Draw(Win,Picture,pnt(470,60),rop_MergeCopy).

  outitem(b,r1,Win):-

    Picture = pict_GetFromRes(idb_R1),

    pict_Draw(Win,Picture,pnt(167,185),rop_MergeCopy).

                           

  outitem(l,r2,Win):-

    Picture = pict_GetFromRes(idb_R2),

    pict_Draw(Win,Picture,pnt(1,142),rop_MergeCopy).

  outitem(r,r2,Win):-

    Picture = pict_GetFromRes(idb_R2),

    pict_Draw(Win,Picture,pnt(400,128),rop_MergeCopy).

  outitem(b,r2,Win):-

    Picture = pict_GetFromRes(idb_R2),

    pict_Draw(Win,Picture,pnt(309,185),rop_MergeCopy).

 

  outitem(l,r3,Win):-

    Picture = pict_GetFromRes(idb_R3),

    pict_Draw(Win,Picture,pnt(1,221),rop_MergeCopy).

  outitem(r,r3,Win):-

    Picture = pict_GetFromRes(idb_R3),

    pict_Draw(Win,Picture,pnt(452,202),rop_MergeCopy).

  outitem(b,r3,Win):-

    Picture = pict_GetFromRes(idb_R3),

    pict_Draw(Win,Picture,pnt(288,188),rop_MergeCopy).

 

outitem(l,r4,Win):-

    Picture = pict_GetFromRes(idb_R4),

    pict_Draw(Win,Picture,pnt(37,142),rop_MergeCopy).

  outitem(r,r4,Win):-

    Picture = pict_GetFromRes(idb_R4),

    pict_Draw(Win,Picture,pnt(450,128),rop_MergeCopy).

  outitem(b,r4,Win):-

    Picture = pict_GetFromRes(idb_R4),

    pict_Draw(Win,Picture,pnt(330,185),rop_MergeCopy).

 

outitem(l,r5,Win):-

    Picture = pict_GetFromRes(idb_R5),

    pict_Draw(Win,Picture,pnt(30,281),rop_MergeCopy).

  outitem(r,r5,Win):-

    Picture = pict_GetFromRes(idb_R5),

    pict_Draw(Win,Picture,pnt(460,202),rop_MergeCopy).

  outitem(b,r5,Win):-

    Picture = pict_GetFromRes(idb_R5),

    pict_Draw(Win,Picture,pnt(300,188),rop_MergeCopy).

 

outitem(l,o1,Win):-

    Picture = pict_GetFromRes(idb_O1),

    pict_Draw(Win,Picture,pnt(86,81),rop_MergeCopy).

  outitem(r,o1,Win):-

    Picture = pict_GetFromRes(idb_O1),

    pict_Draw(Win,Picture,pnt(519,72),rop_MergeCopy).

  outitem(b,o1,Win):-

    Picture = pict_GetFromRes(idb_O1),

    pict_Draw(Win,Picture,pnt(218,200),rop_MergeCopy).

                           

  outitem(l,o2,Win):-

    Picture = pict_GetFromRes(idb_O2),

    pict_Draw(Win,Picture,pnt(86,155),rop_MergeCopy).

  outitem(r,o2,Win):-

    Picture = pict_GetFromRes(idb_O2),

    pict_Draw(Win,Picture,pnt(494,141),rop_MergeCopy).

  outitem(b,o2,Win):-

    Picture = pict_GetFromRes(idb_O2),

    pict_Draw(Win,Picture,pnt(237,200),rop_MergeCopy).

 

  outitem(l,o3,Win):-

    Picture = pict_GetFromRes(idb_O3),

    pict_Draw(Win,Picture,pnt(99,235),rop_MergeCopy).

  outitem(r,o3,Win):-

    Picture = pict_GetFromRes(idb_O3),

    pict_Draw(Win,Picture,pnt(502,214),rop_MergeCopy).

  outitem(b,o3,Win):-

    Picture = pict_GetFromRes(idb_O3),

    pict_Draw(Win,Picture,pnt(254,200),rop_MergeCopy).

 

outitem(l,o4,Win):-

    Picture = pict_GetFromRes(idb_O4),

    pict_Draw(Win,Picture,pnt(72,235),rop_MergeCopy).

  outitem(r,o4,Win):-

    Picture = pict_GetFromRes(idb_O4),

    pict_Draw(Win,Picture,pnt(552,214),rop_MergeCopy).

  outitem(b,o4,Win):-

    Picture = pict_GetFromRes(idb_O4),

    pict_Draw(Win,Picture,pnt(270,200),rop_MergeCopy).

 

outitem(l,o5,Win):-

    Picture = pict_GetFromRes(idb_O5),

    pict_Draw(Win,Picture,pnt(42,235),rop_MergeCopy).

  outitem(r,o5,Win):-

    Picture = pict_GetFromRes(idb_O5),

    pict_Draw(Win,Picture,pnt(492,214),rop_MergeCopy).

  outitem(b,o5,Win):-

    Picture = pict_GetFromRes(idb_O5),

    pict_Draw(Win,Picture,pnt(244,200),rop_MergeCopy).

 

%BEGIN Task Window, e_Create

  task_win_eh(_Win,e_Create(_),0):-

  win_Move(_Win,rct(50,50,640,500)),%изменение размеров окна в соответствии с размерами фоновой картинки

  dlg_about_dialog_Create(_Win),

  start(state([l,l,l,l,l],[l,l,l,l,l],l),state([r,r,r,r,r],[r,r,r,r,r],r)),

              !.%запуск алгортма решения задачи

%END Task Window, e_Create

%MARK Task Window, new events

%BEGIN Task Window, e_MouseUp

  task_win_eh(_Win,e_MouseUp(_PNT,_ShiftCtlAlt,_Button),0):-!,

              outbackground(_Win), path_db(state([R1,R2,R3],[O1,O2,O3],B)),

              retract(path_db(state([R1,R2,R3,R4,R5],[O1,O2,O3,O4,O5],B))),

              outitem(R1,r1,_Win),

              outitem(R2,r2,_Win),

              outitem(R3,r3,_Win),

              outitem(R4,r4,_Win),

              outitem(R5,r5,_Win),

             

              outitem(O1,o1,_Win),

              outitem(O2,o2,_Win),

              outitem(O3,o3,_Win),

              outitem(O4,o4,_Win),

              outitem(O5,o5,_Win),

!.

%END Task Window, e_MouseUp

%BEGIN Task Window, e_Update

  task_win_eh(_Win,e_Update(_UpdateRct),0):-!,

  outbackground(_Win),%вывод фона сразу при запуске системы

              !.

%END Task Window, e_Update

********************************************************************************

 

 

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

 

Цель испытаний

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

 

Технические средства, используемые во время испытаний

Во время испытаний использовались технические средства:

      манипулятор мышь;

      процессор Intel Pentium4 с тактовой частотой 3.0 GHz;

      оперативная память 1Гб;

      видеокарта и монитор, поддерживающие разрешение 1024x768 точек и больше при глубине цвета 32 бита;

      дисковое пространство 160 Гб.

 

Программные средства, используемые во время испытаний

Во время испытаний использовалось программное обеспечение: операционная система Microsoft Windows XP.

 

Порядок испытаний

Испытание программы проводились в следующем порядке:

      испытание на корректность (адекватно ли программа реагирует на ввод вывод информации);

      испытание на правильность;

      испытание на надежность (процент отказа системы).

 

Методы испытаний
Проверка на корректность

Проверка на корректный вывод информации:

      Запускается выполняемый модуль Rgz3.exe;

      Путём нажатия левой клавишей мыши на главном окне программы просматривается найденное решение (см. рис. 6).

При проверке на корректность, результат не отличался от ожидаемого (см. рис. 7). Поэтому можно сказать, что программа работает корректно.

 

Проверка на правильность

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

Проверка на надежность

В процессе разработки и тестирования программы процент отказа программы составил 0%. Поскольку процент отказа программы не превышает процента отказа, установленного нормами, то можно сделать вывод, что программа работает надежно.

 

 

 

 

Приложение

Эскизы экранных форм

Информация о работе Поиск решения на графах пространства состояний