Dijkstra在Prolog

我已經被賦予在Prolog中編寫Dijkstra最短路徑的任務。Dijkstra在Prolog

首先，我不想要源代碼或完整的實現，因爲我試圖理解代碼（評估的一部分將解釋代碼）。我已經看到了一些實現here和there，但我不知道它是如何工作的。

到目前爲止，我有這樣的：

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).

的事情是，我不知道如何更新關於頂點信息。我試過斷言/ 1和收回/ 1，但它不起作用。我得到錯誤，我無法修改靜態程序頂點/ 4。

我目前使用SWI Prolog，但程序應該在Amzi上工作！ Prolog也是如此，所以我想盡可能地使它接近基本的Prolog。

謝謝。

來源

2012-12-10 jnovacho

'： - dynamic vertex/4.' – m09

那麼要麼沒有工作，要麼我用它錯了。我在文件的開始處添加了它。仍然是同樣的錯誤 - 不能修改靜態變量。你能提供更多關於這個的信息嗎？ SWI具體還是一般？ – jnovacho

始終讓您的程序無需先聲明，然後使用它進行優化。序言的要點是你不存儲數據。你想要的是某種你作爲參數傳遞的數據結構，以及一個接受該數據結構並返回其修改版本的函數。然後，當你得到它的工作時，使用斷言不會改變你的代碼的語義（也就是說，如果以前成功的謂詞成功了） – jmite

如果你確實需要更新值，我建議你使用flag/3。但是，正如評論所建議的那樣，Prolog程序通常沒有通過算法步驟更新的「全局變量」。

相反，我會建議你找到一個合適的方法來計算Dijkstra成本。請注意，Dijkstra算法中的初始參數始終是「未訪問」節點，列表（[a,b,c,d|...]）。在每一步中，您都需要「訪問」其中一個節點並更新其成本來更新此列表。我在這裏看到一個明確的遞歸調用！

來源

2014-02-15 13:57:10

請注意，'flag/3'謂詞是一個SWI-Prolog專有謂詞。但是，在其他Prolog實現中，它可能會被仿效。 –

回答

相關問題