1

我正在尝试在SWI-Prolog中实现A* 算法。我有一个图，它的每个状态都由以下值组成，我想根据 Heuristic 将状态插入优先级队列，这是一个整数。我怎样才能做到这一点？(Cost_So_Far, Heuristic, "Doesn't Matter", "Doesn't Matter", "Doesn't Matter")

4

3 回答 3

4

您可以使用“堆”库，它是“优先队列”概念的实现。Richard O'Keefe 有一个堆 Prolog 实现。SWI-Prolog 还在 Lars Buitinck 的“堆”库中提供了堆实现。Logtalk（在多个 Prolog 系统上运行，包括 SWI-Prolog）还包括源自 Richard 原始实现的最大堆和最小堆。正如Boris建议的那样，使用启发式值作为键，堆应该比每次添加新对时都必须使用的列表更有效。

一些有用的链接：

SWI-Prolog 堆库

Logtalk 堆协议

Logtalk 最小堆和最大堆实现

于 2013-08-28T10:45:09.957 回答
2

一种简单的方法是使用Key-Value具有以下形式的对列表：

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

您来自启发式的整数值将是关键，与state函子（您需要的任何数量）的复合术语将是值。请注意，这是保存对列表的传统方式。您可以使用匹配将它们取出，例如，队列头部的状态将是：

[Heuristic-state(A, B, C)|QueueRest]

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

于 2013-08-28T09:54:17.550 回答
0

这是优先级队列的基本实现。我刚开始学习Prolog。如果有更好的方法来实现优先级队列，请在下面评论。

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.
*/
于 2019-11-22T13:25:21.757 回答