• API
• FAQ
• Tools
• Archive
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.

Top