SHARE
TWEET

EJSTAR

a guest Mar 25th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. % Best First Search - A*     Eight puzzle                          
  2.  
  3. a_star(Start,Goal):-                       
  4.         estimate(Start,Goal,0,_,H),             % [State,Parent,G,H,F]
  5.     path([[Start,nil,0,H,H]],[],Goal).      % path(Open,Closed,Goal)
  6.  
  7. path([ ],_,_):-
  8.     write('No solution was found.'),!.
  9. path(Open,Closed,Goal):-
  10.     dequeue([Goal,Parent|_],Open,_),
  11.     write('Solution was found. The path is:'),nl,
  12.     print_solution([Goal,Parent|_],Closed),
  13.     length(Open,L_open),nl,write('L_open: '),write(L_open),nl,
  14.     length(Closed,L_closed),write('L_closed: '),write(L_closed).
  15. path(Open,Closed,Goal):-
  16.     dequeue([State,Parent,G,H,F],Open,Rest_open),
  17.         get_children(State,G,F,Rest_open,Closed,Goal,[],Children),
  18.     insert_to_open(Rest_open,Children,New_open),
  19.     append([[State,Parent,G,H,F]],Closed,New_closed),
  20.     path(New_open,New_closed,Goal).
  21.  
  22. dequeue(E,[E|T],T).
  23.  
  24. get_children(State,G,F,Rest_open,Closed,Goal,Temp,Children):-
  25.     move(State,Next),
  26.     not(member([Next|_],Closed)),
  27.     not(member([Next|_],Temp)),
  28.     estimate(Next,Goal,G,Gnew,H),
  29.     Ftemp is Gnew+H,
  30.     max(F,Ftemp,Fnew),
  31.         get_children(State,G,F,Rest_open,Closed,Goal,
  32.              [[Next,State,Gnew,H,Fnew]|Temp],Children),!.
  33. get_children(_,_,_,_,_,_,L,L).
  34.  
  35. max(A,B,A):-A>=B.
  36. max(A,B,B):-A<B.
  37.  
  38. insert_to_open(Open,[],Open).
  39. insert_to_open(Open,[H|T],Open_new):-
  40.     insert(Open,H,Temp_open),
  41.         insert_to_open(Temp_open,T,Open_new).
  42.                  
  43. insert([],H,[H]).
  44. insert(Open,[Next,P,G,H,F],New_open):-member([Next,_,_,_,_],Open),!,
  45.                                   insert_change(Open,[Next,P,G,H,F],New_open).
  46.  
  47. insert([[S1,P1,G1,H1,F1]|T1],[S2,P2,G2,H2,F2],
  48.     [[S2,P2,G2,H2,F2],[S1,P1,G1,H1,F1]|T1]):-
  49.     F1>=F2.
  50. insert([[S1,P1,G1,H1,F1]|T1],[S2,P2,G2,H2,F2],[[S1,P1,G1,H1,F1]|T3]):-
  51.     F1<F2,
  52.     insert(T1,[S2,P2,G2,H2,F2],T3).
  53.  
  54. %insert_change(Open,Child,Open_new)
  55. insert_change(Open,[Node,Pnew,Gnew,Hnew,Fnew],Open):-
  56.         remove(Open,[Node,Pnew,Gnew,Hnew,Fnew],[Node,_,_,_,Fold],_),
  57.         %write(Open_temp),nl,write(Fold),nl,write(Fnew),nl,
  58.         Fold=<Fnew.
  59. insert_change(Open,[Node,Pnew,Gnew,Hnew,Fnew],Open_new):-
  60.         remove(Open,[Node,Pnew,Gnew,Hnew,Fnew],[Node,_,_,_,Fold],Open_temp),
  61.         %write(Open_temp),nl,write(Fold),nl,write(Fnew),nl,
  62.     Fold>Fnew,
  63.         %write('jsem zde'),nl,
  64.         insert(Open_temp,[Node,Pnew,Gnew,Hnew,Fnew],Open_new).
  65.  
  66. remove([[Node,Pold,Gold,Hold,Fold]|T],[Node,_,_,_,_],
  67.     [Node,Pold,Gold,Hold,Fold],T).
  68. remove([H|T],[Node,_,_,_,_],[Node,Pold,Gold,Hold,Fold],[H|Ttemp]):-
  69.     remove(T,[Node,_,_,_,_],[Node,Pold,Gold,Hold,Fold],Ttemp).
  70.  
  71. member(H,[H|_]).
  72. member(H,[_|T]):-member(H,T).
  73.  
  74. append([],S,S).
  75. append([H|T1],T2,[H|T3]):-
  76.     append(T1,T2,T3).
  77.  
  78. print_solution([State,nil|_],_):-
  79.     write1(State),nl.
  80. print_solution([State,Parent|_],Closed):-
  81.     member([Parent,Grandparent|_],Closed),
  82.     print_solution([Parent,Grandparent|_],Closed),
  83.     write1(State),nl.
  84.  
  85. estimate(State,Goal,G,Gnew,H):-
  86.     size(N),
  87.     NN is N*N,
  88.     evaluate(State,Goal,OK),H is NN-1-OK,Gnew is G+1.
  89.  
  90. evaluate([],[],0).
  91. % evaluate([o],[o],0).
  92. % evaluate([A],[B],0):-A\=B.
  93. % evaluate([H],[H],1):-H\=o.
  94. evaluate([o|TState],[o|TGoal],OK):-evaluate(TState,TGoal,OK).
  95. evaluate([A|TState],[B|TGoal],OK):-A\=B,
  96.                                    evaluate(TState,TGoal,OK).
  97. evaluate([H|TState],[H|TGoal],OK):-H\=o,
  98.                                    evaluate(TState,TGoal,TOK),
  99.                                    OK is TOK+1.
  100.  
  101. %write1([A,B,C,D,E,F,G,H,I]):-
  102. %   write(A),write(B),write(C),nl,
  103. %   write(D),write(E),write(F),nl,
  104. %   write(G),write(H),write(I),nl.
  105.  
  106. write1([]).
  107. write1(L):-size(N),write2(L,N).
  108.  
  109. write2([H|T],M):-M>0,write(H),MM1 is M-1,write2(T,MM1).
  110. write2(L,_):-nl,write1(L).
  111.  
  112.  
  113. move(State,Next):- size(N),
  114.     find_pos(State,SP),
  115.     SP>N,
  116.     NP is SP-N,
  117.         change(State,NP,SP,Next).
  118. move(State,Next):- size(N),
  119.     find_pos(State,SP),
  120.     R is SP mod N,
  121.     R\=0,
  122.     NP is SP+1,
  123.         change(State,NP,SP,Next).
  124. move(State,Next):- size(N),
  125.     find_pos(State,SP),
  126.     NN is N*(N-1)+1,
  127.     SP<NN,
  128.     NP is SP+N,
  129.         change(State,NP,SP,Next).
  130. move(State,Next):- size(N),
  131.     find_pos(State,SP),
  132.     R is SP mod N,
  133.     R\=1,
  134.     NP is SP-1,
  135.         change(State,NP,SP,Next).
  136.  
  137. find_pos([o|_],1).
  138. find_pos([H|T],SP):-
  139.     H\=o,
  140.     find_pos(T,SPM1),
  141.     SP is SPM1+1.
  142.  
  143. change(State,NP,SP,Next):-
  144.     move_sp(State,NP,Piece,Temp_State),
  145.     move_piece(Temp_State,SP,Piece,Next).
  146.  
  147. move_sp([H|T],1,H,[o|T]).
  148. move_sp([H|T],N,Piece,[H|TN]):-
  149.     N>1,
  150.     NM1 is N-1,
  151.     move_sp(T,NM1,Piece,TN).
  152.  
  153. move_piece([_|T],1,H,[H|T]).
  154. move_piece([H|T],N,Piece,[H|TN]):-
  155.     N>1,
  156.     NM1 is N-1,
  157.     move_piece(T,NM1,Piece,TN).
  158.  
  159.  
  160. %**************************************************************
  161.  
  162. aa0:-assert(size(0)),retractall(size(_)),assert(size(4)),
  163.     a_star([1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o],
  164.     [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]).
  165. aa1:-assert(size(0)),retractall(size(_)),assert(size(4)),
  166.     a_star([1,2,3,4,5,6,7,8,9,a,b,o,d,e,f,c],
  167.     [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]).
  168. aa2:-assert(size(0)),retractall(size(_)),assert(size(4)),
  169.     a_star([1,2,3,4,5,6,7,8,9,a,o,b,d,e,f,c],
  170.     [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]).
  171. aa3:-assert(size(0)),retractall(size(_)),assert(size(4)),
  172.     a_star([1,2,3,4,5,6,o,8,9,a,7,b,d,e,f,c],
  173.     [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]).
  174. aa4:-assert(size(0)),retractall(size(_)),assert(size(4)),tell('as4_aa4.vysl'),
  175.     a_star([1,2,3,4,5,6,o,8,9,a,7,b,d,e,f,c],
  176.         [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]),told.
  177. aa5:-assert(size(0)),retractall(size(_)),assert(size(4)),tell('as4_aa5.vysl'),
  178.     a_star([1,2,o,4,5,6,3,8,9,a,7,b,d,e,f,c],
  179.         [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]),told.
  180. aa6:-assert(size(0)),retractall(size(_)),assert(size(4)),tell('as4_aa6.vysl'),
  181.     a_star([o,1,2,4,5,6,3,8,9,a,7,b,d,e,f,c],
  182.         [1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,o]),told.
  183.  
  184.  
  185. a0:-assert(size(0)),retractall(size(_)),assert(size(3)),
  186.     a_star([1,2,3,8,o,4,7,6,5],[1,2,3,8,o,4,7,6,5]).
  187. a1:-assert(size(0)),retractall(size(_)),assert(size(3)),
  188.     a_star([1,2,3,8,4,o,7,6,5],[1,2,3,8,o,4,7,6,5]).
  189. a2:-assert(size(0)),retractall(size(_)),assert(size(3)),
  190.     a_star([1,2,o,8,4,3,7,6,5],[1,2,3,8,o,4,7,6,5]).
  191. a3:-assert(size(0)),retractall(size(_)),assert(size(3)),
  192.     a_star([8,1,3,o,2,4,7,6,5],[1,2,3,8,o,4,7,6,5]).
  193. a4:-assert(size(0)),retractall(size(_)),assert(size(3)),tell('as3_a4.vysl'),
  194.     a_star([1,4,2,8,o,3,7,6,5],[1,2,3,8,o,4,7,6,5]),told.
  195. a5:-assert(size(0)),retractall(size(_)),assert(size(3)),tell('as3_a5.vysl'),
  196.     a_star([1,4,2,o,8,3,7,6,5],[1,2,3,8,o,4,7,6,5]),told.
  197. a6:-assert(size(0)),retractall(size(_)),assert(size(3)),tell('as3_a6.vysl'),
  198.     a_star([1,4,2,7,8,3,o,6,5],[1,2,3,8,o,4,7,6,5]),told.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top