如何在SWI-Prolog中使用优先级队列？

Question

我正在尝试在SWI-Prolog中实现A *算法。我有一个图表，其每个状态都包含以下值（Cost_So_Far，Heuristic，“不重要”，“不重要”，“不重要”），并且我想根据以下内容将状态插入优先级队列启发式，这是一个整数。我该怎么办？

Answer 1

一种简单的方法是使用Key-Value对列表，其格式为：

[1-state(Cost_so_far, ...), 2-state(...), 3-state(...)]

您的启发式整数值将是关键，函子状态（无论您需要什么）都将是该值。请注意，这是保留对列表的常规方法。您可以使用匹配将其删除，例如，队列开头的状态为：
[Heuristic-state(A, B, C)|QueueRest]

每次在队列顶部添加新状态时，您都应该使用内置的keysort/2对它进行排序（非常高效）。

Answer 2

您可以使用“堆”库，该库是“优先队列”概念的实现。理查德·奥基夫（Richard O'Keefe）有个堆式的Prolog实现。 SWI-Prolog在Lars Buitinck的“堆”库中还提供了堆实现。 Logtalk（可在包括SWI-Prolog在内的多个Prolog系统上运行）还包括从Richard的原始实现派生的最大和最小堆。使用鲍里斯（Boris）建议的启发式值作为关键字，堆应该比每次添加新对时都要使用的列表更有效率。

一些有用的链接：

SWI-Prolog heaps library

Logtalk heap protocol

Logtalk min-heap and max-heap implementations

Answer 3

这是优先级队列的基本实现。我刚刚开始学习序言。如果有更好的方法来实现优先级队列。请在下方留言。

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 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.
*/