I am trying to implement the A* algorithm in SWI-Prolog. I have a graph whose each state consists of the following values (Cost_So_Far, Heuristic, "Doesn't Matter", "Doesn't Matter", "Doesn't Matter") and I want to insert the state into a priority queue according to Heuristic which is an integer. How can I do this?
Asked
Active
Viewed 2,161 times
1
Guy Coder
- 24,501
- 8
- 71
- 136
user2424276
- 591
- 1
- 5
- 24
-
2Please read "[Stack Overflow question checklist](https://meta.stackoverflow.com/questions/260648)". – the Tin Man Dec 31 '19 at 04:32
-
Since [A*](https://en.wikipedia.org/wiki/A*_search_algorithm) is an enhancement to [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) why not start with that? At RosettaCode is [Dijkstra's algorithm](http://www.rosettacode.org/wiki/Dijkstra%27s_algorithm) in many programming languages including [Prolog](http://www.rosettacode.org/wiki/Dijkstra%27s_algorithm#Prolog) – Guy Coder Feb 07 '20 at 10:02
-
A check of RosettaCode for [A*](http://www.rosettacode.org/wiki/A*_search_algorithm) shows that there is no entry for Prolog. – Guy Coder Feb 07 '20 at 10:05
-
This claims to have A* in Prolog in the [question](https://stackoverflow.com/questions/41020596/astar-prolog), did not verify. – Guy Coder Feb 07 '20 at 10:07
-
Another question show A* in Prolog in the [question](https://stackoverflow.com/q/24630245/1243762) – Guy Coder Feb 07 '20 at 10:09
3 Answers
4
You can use a "heap" library, which is an implementation of the concept of "priority queue". There's a heap Prolog implementation by Richard O'Keefe floating around. SWI-Prolog also comes with a heap implementation in its "heaps" library by Lars Buitinck. Logtalk (which runs on several Prolog systems, including SWI-Prolog) also includes max- and min-heaps derived from Richard's original implementation. Using the heuristic value as the key as Boris suggested, a heap should be more efficient than a list that you would have to resort every time you add a new pair.
Some useful links:
Will Ness
- 70,110
- 9
- 98
- 181
Paulo Moura
- 18,373
- 3
- 23
- 33
2
One easy way is to use a Key-Value pair list, which has the form:
[1-state(Cost_so_far, ...), 2-state(...), 3-state(...)]
Your integer value from the heuristic would be the key, compound term with the state functor (of whatever arity you need) would be the value. Note that this is the conventional way of keeping a list of pairs. You can use matching to get them out, for example, the state at the head of the queue would be:
[Heuristic-state(A, B, C)|QueueRest]
You should probably use the built-in keysort/2 for sorting it (very efficiently) every time you have added new states at the top of the queue.
Will Ness
- 70,110
- 9
- 98
- 181
0
This is a basic implementation of priority queues. I just started learning Prolog. If any better way to implement priority queues, please comment down below.
takeout(X,[X|R],R).
takeout(X,[F|Fs],[F|S]):- takeout(X,Fs,S).
delete_elem([H|T]):- min_p([H|T],99,MinP) , search_minp(MinP , [H|T] , Num) ,
takeout((Num,MinP),[H|T],Z) , write(Z).
ins([],L,L).
ins([(Num,Priority)|T],L,[(Num,Priority)|Z] ):- ins(T,L,Z).
/* here i used ins function to append (Num,Priority) to a existing queue
if [(99,2) , (90,1) , (96, 3)] this is priority queue. if want to add (93,4)
ins([(93,4)] , [(99,2) , (90,1) , (96, 3)] ,Z).
Z = [(99,2) , (90,1) , (96, 3) , (93,4)]
*/
min_p([],Min,Min).
min_p([(Num,Priority)|Z],X,Y):- Priority < X , Min is Priority , min_p(Z,Min,Y).
min_p([(Num,Priority)|Z],X,Y):- Priority > X , min_p(Z,X,Y).
/* min_p here I used to find the minimum priority from the given priority queue.
X should be INT_MAX
min_p([(99,2) , (90,1) , (96, 3) , (93,4)],999,Y).
Y = 1 .
*/
search_minp(Priority,[(Num,P)|T],Num):- Priority is P.
search_minp(Priority,[(Num,P1)|T],X):- search_minp(Priority,T,X).
/* search_minp is used to search element corresponding to minimum priority.
if this is our priority queue [(99,2) , (90,1) , (96, 3) , (93,4)]
search_minp(1,[(99,2) , (90,1) , (96, 3) , (93,4)],Z).
Z = 90.
*/
