Игра в Восемь, Изучение основных стратегий решения задач (Лабораторная работа № 3), страница 3

      broad(_,der(_,_,[]),_,_,"never",_):-!.% тупиковое дерево – нет решений

      broad(_,Tr,Lim,Tr,"no",_):-

             f(Tr,F),F>Lim.% рост остановлен

      continue(_,_,_,_,"yes","yes",Resh).                

      continue(P,der(B,num(F,G),[T1|TT]),Lim,Tr1,IsResh1,IsResh,Resh):-

             Help(IsResh1,[T1|TT],NTT),

             opt_f(NTT,F1),

             broad(P,der(B,num(F1,G),NTT),Lim,Tr1,IsResh,Resh).

      Help("no",[T1|TT],NTT):-ins(T1,TT,NTT).

      Help("never",[T1|TT],TT).

      make_next(_,[],[]).

      make_next(G0,[rang(B,C)|BB],TT):-

             G=G0+C, h(B,H),F=G+H,showp(B),write(" F=",F," G= ",G," H= ",H),make_next(G0,BB,TT1),

             ins(ver(B,num(F,G)),TT1,TT).

%Вставка дерева Т в список деревьев ТТ с сохранением упорядоченности по f-%оценкам

      ins(T,TT,[T|TT]):-

             f(T,F),opt_f(TT,F1), F <= F1,!.

      ins(T,[T1|TT],[T1|TT1]):-

             ins(T,TT,TT1).

%получение f- оценки

      f(ver(_,num(F,_)),F).% f- оценкалиста

      f(der(_,num(F,_),_),F). % f- оценка дерева

      opt_f([T|_],F):-         % наилучшая f- оценка для списка деревьев

             f(T,F).

      opt_f([],Fmax):-              %нет деревьев:

             maxf(Fmax).              %плохая f- оценка

      maxf(1000).

      min(X,Y,X):-X<=Y,!.

      min(X,Y,Y).

      after([Fr|List],[El|List1],1):- %стоимости всех дуг =1

             change(Fr,El,List,List1).%переставив Fr и El получаем List1

      change(F,El,[El|L],[F|L]):-

             r(F,El,1).

      change(F,El,[El1|L],[El1|L1]):-

             change(F,El,L,L1).

      r(xy(X,Y),xy(X1,Y1),P):-  %манхеттеновское расстояние

             r1(X,X1,Px), r1(Y,Y1,Py), P = Px+Py.

      r1(A,B,P):-

             Q=B,

             P=A-Q,P>=0,!;

             Q=B,P=Q-A.

      h([Fr|List],H):-

             aim([Fr1|AimL]),

             sumr(List,AimL,P),

            ord(List,Ord),

             H=P+3*Ord.

      sumr([],[],0).

      sumr([E|L],[E1|L1],P):-

             r(E,E1,P1),

             sumr(L,L1,P2),

             P=P1+P2.

      ord(L,Res):-

             ord(L,Res,1).

      ord(L,Res,I):-

             I<8,

             J=I+1,

             ord(L,R1,J),

             get_score(L,R2,I),

             Res=R1+R2,!.

      ord(L,Res,8):-

             get_score(L,Res,8).

% вычисление очков

      next(xy(1,3),xy(2,3)).

      next(xy(2,3),xy(3,3)).

      next(xy(3,3),xy(3,2)).

      next(xy(3,2),xy(3,1)).

      next(xy(3,1),xy(2,1)).

      next(xy(2,1),xy(1,1)).

      next(xy(1,1),xy(1,2)).

      next(xy(1,2),xy(1,3)).

      get_xy(1,[A|L],A).

      get_xy(I,[A|L],Coord):-J=I-1,J>0,get_xy(J,L,Coord).

      get_i(Coord,[],-100,-1).

      get_i(Coord,[Coord|L],1,1).

      get_i(Coord,[C|L],I,Fl):-get_i(Coord,L,I1,Fl),I=I1+1.

      get_score(L,Sc,I):-

             get_xy(I,L,XY),XY=xy(2,2),Sc=1.

      get_score(L,Sc,I):-

             get_xy(I,L,XY_I),

             next(XY_I,XY_J),

             get_i(XY_J,L,J,Flag),

             checker(Flag,I,J,Sc).

      checker(-1,I,J,2).

      checker(1,I,J,Sc):-

             aim([Fr|AL]),

             get_xy(I,AL,XY_I1),

             get_xy(J,AL,XY_J1),

             test(XY_I1,XY_J1,Sc).

      test(XY1,XY2,Sc):-next(XY1,XY2),!,Sc=0.

      test(XY1,XY2,Sc):-Sc=2.

        member(X,[X|_]).

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

      member_i(X,[X|_]).

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

      member_s(X,[X|_]).

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

      member_p(X,[X|_]).

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

%целевая позиция

      aim([xy(2,2),xy(1,3),xy(2,3),xy(3,3),xy(3,2),xy(3,1),xy(2,1),xy(1,1),xy(1,2)]).

%вывод результата и дерева решения в файлы  

      show([],0).

      show([P|L],I):-

             show(L,J),I=J+1,write(I),nl,

             showp(P).

      showp([A1,A2,A3,A4,A5,A6,A7,A8,A9]):-

             member_i(Y,[3,2,1]),nl,member_i(X,[1,2,3]),

            member_s(sh(N,xy(X,Y)),[sh("0",A1),sh("1",A2),sh("2",A3),sh("3",A4),

            sh("4",A5),sh("5",A6),sh("6",A7),sh("7",A8),sh("8",A9)]), write(N," "),

             fail.

      showp(_):-nl,nl.

goal

      openwrite(fi1,"Z:\\tree.txt"),writedevice(fi1),

       BEG=[xy(2,2),xy(1,3),xy(3,2),xy(2,3),xy(3,3),xy(3,1),xy(2,1),xy(1,1),xy(1,2)],

%      BEG=[xy(2,1),xy(1,2),xy(1,3),xy(3,3),xy(3,2),xy(3,1),xy(2,2),xy(1,1),xy(2,3)],

%      BEG=[xy(2,2),xy(2,3),xy(1,3),xy(3,1),xy(1,2),xy(2,1),xy(3,3),xy(1,1),xy(3,2)],

      poisk(BEG,RES),

      closefile(fi1),

      openwrite(fi2,"Z:\\result.txt"),writedevice(fi2),

      show(RES,_),

      closefile(fi2)