Основные стратегии решения задач

Министерство образования РФ

Новосибирский государственный технический университет

Кафедра программных систем и баз данных

Лабораторная работа №2

"Стратегии решения задач"

Факультет: ПМИ

Группа: ПМ-01

Студенты: Кирюшина Е.С.

Русакова Ю.М.

Хижняк О.А.

Преподаватель: Целебровская М.Ю.

Новосибирск 2004

Цель работы: Изучение основных стратегий решения задач. Приобретение  навыков  выбора  адекватных  стратегий в зависимости от типа задач. Выбор инструмента для реализации этих стратегий.

Задание: "Игра в восемь". В  головоломке используется 8 перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в 9 ячейках, образующих матрицу 3 на 3. Одна из ячеек всегда пуста, и любая смежная с ней фишка может быть передвинута в эту пустую ячейку. Конечная ситуация – некоторая заранее заданная конфигурация фишек.

Вершина пространства состояний задается списком текущих положений фишек. Текущее положение определяется парой координат (X,Y). Элементы списка располагаются в следующем порядке: 1) текущее положение пустой клетки, 2) текущее положение фишки 1, . . . , 9) текущее положение фишки 8. Путь поиска – список вершин пространства состояний.

Используется поиск с предпочтением (эвристический поиск).

Эвристическая оценка вершины определяется как sum+3*up, где

sum – суммарное расстояние 8 фишек, находящихся в текущей позиции от их положений в целевой позиции.

up – степень упорядоченности фишек в текущей позиции по отношению к тому порядку, в котором они должны находиться в целевой позиции. Вычисляется как сумма очков, приписываемых фишкам: фишка в центре – 1 очко, фишка не в центре и непосредственно за ней следует та фишка, какая и должна следовать в целевой позиции – 0 очков, за фишкой следует "не та" фишка – 2 очка.

Текст программы:

domains

k=k(integer,integer)

listk=k*

list=listk*

c=c(listk,integer)

listc=c*

file=fi

predicates

ne(k,k);

ppos(integer,listk,listk);

presh(list);

find(integer,listk,k,integer);

w(integer);

posle(listk,listk,integer);

perest(k,k,listk,listk);

r(k,k,integer);

r1(integer,integer,integer);

sum(listk,listk,integer);

ochki(k,k,integer);

up(listk,integer);

up1(listk,k,integer);

value(listk,integer);

start(listk,list,list);

start1(listk,listk);

member(listk,list);

memb(c,listc);

sp(listk,list);

sp1(listk,list,list);

insert(c,listc,listc);

evalute(list,listk,listc,listc);

final_state(listk);

clauses

w(0):-write("  ").

w(I):-I<>0,write(I).

presh([]).

presh([P|S]):nl,write(" -------------"),nl,

ppos(0,P,[k(1,3),k(2,3),k(3,3),k(1,2),k(2,2),k(3,2),,k(1,1),k(2,1),k(3,1)]),   presh(S).

ppos(3,_,[]):-  write(" |"),nl, write(" -------------"),nl,!.

ppos(3,P,Y):-   write(" |"),nl, write(" -------------"),nl, ppos(0,P,Y).

ppos(K,P,[X|Y]):- I=0, find(I,P,X,J), write(" | "), w(J),

K1=K+1, ppos(K1,P,Y).

ne(k(X,Y),k(A,Y)).

ne(k(X,Y),k(X,B)).

ne(k(X,Y),k(A,B)).

find(I,[k(X,Y)|_],k(X,Y),I).

find(I,[X|Y],Z,C):- ne(X,Z), J=I+1, find(J,Y,Z,C).

posle([P|S],[F|S1],1):- perest(P,F,S,S1).

perest(P,F,[F|S],[P|S]):- r(P,F,1).

perest(P,F,[F1|S],[F1|S1]):-  perest(P,F,S,S1).

r(k(X,Y),k(X1,Y1),P):r1(X,X1,PX),

r1(Y,Y1,PY),

P=PX+PY.

r1(A,B,P):-  P=A-B, P>=0, !; P=B-A.

value([P1|S],H):final_state([P2|S1]),

sum(S,S1,P),

up(S,U),

H=P+3*U.

sum([],[],0).

sum([F|C],[F1|C1],P):r(F,F1,P1),

sum(C,C1,P2),

P=P1+P2.

up([X|C],U):-   up1([X|C],X,U).

up1([F1,F2|C],X,U):ochki(F1,F2,U1),

up1([F2|C],X,U2),

U=U1+U2.

up1([Y],X,U):- ochki(Y,X,U).

ochki(k(2,2),_,1):-!.

ochki(k(1,3),k(2,3),0):-!.

ochki(k(2,3),k(3,3),0):-!.

ochki(k(3,3),k(3,2),0):-!.

ochki(k(3,2),k(3,1),0):-!.

ochki(k(3,1),k(2,1),0):-!.

ochki(k(2,1),k(1,1),0):-!.

ochki(k(1,1),k(1,2),0):-!.

ochki(k(1,2),k(1,3),0):-!.

ochki(_,_,2).

sp(X,Cs):-sp1(X,[],Cs).

sp1(X,A,Cs):posle(X,C,1),

not(member(C,A)),

!,

sp1(X,[C|A],Cs).

sp1(X,Cs,Cs).

member(X,[X|_]).

member(X,[_|Ys]):- member(X,Ys).

memb(X,[X|_]).

memb(X,[_|Ys]):- memb(X,Ys).