fork download
copy 
  1. edges(s,a,1).
  2. edges(s,b,3).
  3. edges(a,b,1).
  4. edges(a,f,6).
  5. edges(b,c,6).
  6. edges(b,f,6).
  7. edges(b,h,3).
  8. edges(c,d,5).
  9. edges(c,h,2).
  10. edges(c,l,4).
  11. edges(d,l,2).
  12. edges(e,a,1).
  13. edges(f,e,7).
  14. edges(f,h,2).
  15. edges(h,l,1).
  16. edges(h,g,7).
  17. edges(l,g,5).
  18.  
  19.  
  20. hs(s,8).
  21. hs(a,7).
  22. hs(b,4).
  23. hs(c,6).
  24. hs(d,4).
  25. hs(e,2).
  26. hs(f,3).
  27. hs(h,4).
  28. hs(l,2).
  29. hs(g,0).
  30.  
  31. min_search([Temp|Rest],[],Result):-
  32.     !,
  33. 	min_search(Rest,Temp,Result).
  34.  
  35. min_search([],MinCost,MinCost):-!.
  36. min_search([[P,Cost]|Rest],[_,TempMin],Result):-
  37. 	Cost<TempMin,!,min_search(Rest,[P,Cost],Result).
  38. min_search([_|Rest],MinP,Result):-
  39. 	   min_search(Rest,MinP,Result).
  40.  
  41. calc_cost(From,To,G_Costs,Result1,Result2):-
  42. 	member([From,G1],G_Costs),
  43. 	edges(From,To,C1),
  44. 	hs(To,H),
  45. 	Result1 is G1+C1+H,
  46. 	Result2 is G1+C1.
  47.  
  48. updateG(G_Costs,ReG_Costs,To,Cost):-
  49. 	select([To,_],G_Costs,RestG),!,
  50. 	ReG_Costs=[[To,Cost]|RestG].
  51. updateG(G_Costs,ReG_Costs,To,Cost):-
  52. 	ReG_Costs=[[To,Cost]|G_Costs].
  53.  
  54. updatePath(Pathes,RePathes,From,To):-
  55. 	select([_,To],Pathes,RestPathes),!,
  56. 	RePathes=[[From,To]|RestPathes].
  57. updatePath(Pathes,RePathes,From,To):-
  58. 	RePathes=[[From,To]|Pathes].
  59.  
  60. path_print([],_).
  61. path_print(P,Pathes):-member([Old,P],Pathes),path_print(Old,Pathes),write([P,'->']).
  62.  
  63. one_search(From,To,
  64. 	  Opend,Closed,Pathes,G_Costs,
  65. 	  ReOpend,ReClosed,RePathes,ReG_Costs):-
  66. 	not(member([To,_],Opend)),
  67. 	not(member([To,_],Closed)),
  68. 	!,
  69. 	calc_cost(From,To,G_Costs,C1,C2),
  70. 	ReOpend=[[To,C1]|Opend],
  71. 	ReClosed=Closed,
  72. 	updatePath(Pathes,RePathes,From,To),
  73. 	updateG(G_Costs,ReG_Costs,To,C2).
  74.  
  75.  
  76. one_search(From,To,
  77. 	  Opend,Closed,Pathes,G_Costs,
  78. 	  ReOpend,ReClosed,RePathes,ReG_Costs):-
  79. 	select([To,NowCost],Opend,RestOpend),
  80. 	calc_cost(From,To,G_Costs,C1,C2),
  81. 	C1<NowCost,
  82. 	!,
  83. 	ReOpend=[[To,C1]|RestOpend],
  84. 	ReClosed=Closed,
  85. 	updatePath(Pathes,RePathes,From,To),
  86. 	updateG(G_Costs,ReG_Costs,To,C2).
  87.  
  88. one_search(From,To,
  89. 	  Opend,Closed,Pathes,G_Costs,
  90. 	  ReOpend,ReClosed,RePathes,ReG_Costs):-
  91. 	select([To,NowCost],Closed,RestClosed),
  92. 	calc_cost(From,To,G_Costs,C1,C2),
  93. 	C1<NowCost,
  94. 	ReOpend=[[To,C1]|Opend],
  95. 	ReClosed=RestClosed,
  96. 	updatePath(Pathes,RePathes,From,To),
  97. 	updateG(G_Costs,ReG_Costs,To,C2).
  98. next_search(_,[],Opend,Closed,Pathes,G_Costs):-!,
  99. 	nl,
  100. 	write(Opend),nl,
  101. 	write(G_Costs),nl,
  102. 	write(Pathes),nl,
  103. 	a_star(Opend,Closed,Pathes,G_Costs).
  104.  
  105. next_search(From,[To|Rest],Opend,Closed,Pathes,G_Costs):-
  106. 	one_search(From,To,Opend,Closed,Pathes,G_Costs,
  107. 		  ReOpend,ReClosed,RePathes,ReG_Costs),!,
  108. 	next_search(From,Rest,ReOpend,ReClosed,RePathes,ReG_Costs).
  109. next_search(From,[_|Rest],Opend,Closed,Pathes,G_Costs):-
  110. 	next_search(From,Rest,Opend,Closed,Pathes,G_Costs).
  111.  
  112.  
  113. a_star(Opend,_,Pathes,_):-
  114. 	min_search(Opend,[],[From,_]),
  115. 	From==g,
  116. 	path_print(g,Pathes).
  117.  
  118.  
  119. a_star(Opend,Closed,Pathes,G_Costs):-
  120. 	min_search(Opend,[],[From,_]),
  121. 	select([From,Cost],Opend,RestOpend),
  122. 	NextClosed=[[From,Cost]|Closed],
  123. 	findall(To,edges(From,To,_),Tos),
  124. 	next_search(From,Tos,RestOpend,NextClosed,Pathes,G_Costs).
  125. main:-a_star([[s,8]],[],[[[],s]],[[s,0]]).
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AxYfXJ
language:
Prolog (swi 7.6.4)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!