API tools faq
paste
Advertisement
Guest User

EJSTAR

a guest
Mar 25th, 2019
127
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.50 KB | None | 0 0
raw download clone embed print report
  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.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!