2

我被分配在 Prolog 中编写 Dijkstra 最短路径。

首先，我不想要源代码或完整实现，因为我正在尝试理解代码（评估的一部分将解释代码）。我在这里和那里看到了一些实现，但我真的不知道它是如何工作的。

到目前为止，我有这个：

edge(1,2,12). %edge(From,To,Cost)
...
edge(1,4,13).

vertex(1,100000,nil,false).%vertex(Id, Weight, Over, Closed).
...
vertex(5,100000,nil,false).

neigh(V1, V2):-edge(V1,V2,_).

open_neigh(V1,V2):-edge(V1,V2,_),vertex(V2,_,_,P),not(P).

nearest_neighbor(From,Who,Cost):-findall(Node,neigh(From, Node),NeighL),
    nearest_in_list(From,Who,NeighL,Cost).

n_hood(From,NeighList):-findall(Node, neigh(From,Node), NeighList).

open_n_hood(From,NeighList):-findall(Node, open_neigh(From,Node), NeighList).

nearest_in_list(_,Who,[Who],_).
nearest_in_list(From,Who,[H,K|T],Cost) :-
    edge(From,H,C1),
    edge(From,K,C2),
    C1 =< C2,
    Cost is C1,
    nearest_in_list(From,Who,[H|T],Cost).

nearest_in_list(From,Who,[H,K|T],Cost) :-
    edge(From,H,C1),
    edge(From,K,C2),
    C1 > C2,
    Cost is C2,
    nearest_in_list(From,Who,[K|T],Cost).

问题是，我不知道如何更新有关顶点的信息。我已经尝试过 assert/1 和retract/1 但它不起作用。我收到无法修改静态过程 vertex/4 的错误。

我目前正在使用 SWI Prolog，但该程序应该可以在 Amzi 上运行！Prolog 也是如此，所以我想让它尽可能接近基本的 Prolog。

谢谢。

4

1 回答 1

1

如果您确实需要更新值，我建议您使用flag/3. 但是，正如评论中所建议的那样，Prolog 程序通常没有您通过算法步骤更新的“全局变量”。

相反，我建议您找到一种计算 Dijkstra 成本的正确方法。请注意，Dijkstra 算法中的初始参数始终是“未访问”节点，即列表 ( [a,b,c,d|...])。在每一步，您都通过“访问”其中一个节点并更新其成本来更新此列表。我在这里看到了一个清晰的递归调用！

于 2014-02-15T13:57:10.060 回答