序言上的性能問題

Question

我目前正在實施prolog程序來計算兩點之間的最短路徑。 該框架已經存在於Java項目中。作爲要求，路徑必須在序言中實現。 所以我用gnu.prolog（http://www.gnu.org/software/gnuprologjava/）

的Java應用我稱之爲searchPath(1,5,Path)的將返回Path=[5,4,3,2,1]

這裏是我的序言代碼：

:- dynamic(path/3). 

findPath([Goal | Rest], Goal, Temp, Temp, [Goal | Rest]). 

findPath([A | Rest], Goal, Cost, Temp, Path) :- 
    path(A,B,C), 
    \+member(B, [A | Rest]), 
    NewCosts is (Temp + C), 
    findPath([B, A | Rest], Goal, Cost, NewCosts, Path). 

searchPath(Start,Goal,Path_to_goal) :- 
    findPath([Start], Goal, Cost1, 0, Path), 
    findPath([Start], Goal, Cost2, 0, Path2), 
    Cost1=<Cost2, 
    Path_to_goal = Path. 

我有兩個問題與：

1. searchPath方法應該返回最短路徑。然而它 確實不是。這導致我的幻影「決定」在某點處切換 方向，導致幻影從左邊的 向右抖動。

2. 我的序言代碼最多需要6秒才能返回結果。我不需要告訴你這是太多的時間。不過有時prolog只需要19ms。我無法弄清楚這取決於哪些情況。例如，一個包含99個元素的路徑列表需要19ms的時間來計算，但是在一個僅包含38個元素的列表上花費了6秒。

你能提出任何改進建議嗎？

感謝您的幫助提前！

Answer 1

您可以使用Dijkstra算法。我實施了answering至this的問題。我的代碼使用attributed variables，我認爲應該在GnuProlog中工作（我現在會測試）。無論如何，你會發現link到一個可行的純Prolog實現。

編輯好了，我想你可以糾正你的代碼，因爲有一個問題：

在searchPath/3 Path2它是一個單：那麼你顯然要總是末與第一個路徑，並且因爲第二個findPath/3將始終發現總是（如果數據庫不更改）與第一個相同的Cost和Path，Cost1=<Cost2,將始終爲真。你可以嘗試，如果

searchPath(Start,Goal,Path_to_goal) :- 
    findall(Cost-Path, findPath([Start], Goal, Cost, 0, Path), Paths), 
    sort(Paths, [_-Path_to_goal|_]). 

是足夠快的任務。否則，您需要實現增量搜索，這不容易，因爲Prolog會在回溯中「返回」替代路徑，然後強制使用某種副作用來選擇最小值。

更多編輯 findall/3會導致代碼太慢。我使用非可回溯分配編寫了更高效的東西（我使用了SWI-Prolog nb_setarg/3，您應該在GProlog中使用setarg/3）。

findPath(_Limit, [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]) :- !. 

findPath(Limit, [A | Rest], Goal, Cost, Temp, Path) :- 
    path(A,B,C), 
    \+member(B, Rest), 
    NewCosts is (Temp + C), 
    NewCosts < Limit, 
    findPath(Limit, [B, A | Rest], Goal, Cost, NewCosts, Path). 

% ?- searchPath(aberdeen, glasgow, Path, Length). 
% 
searchPath(Start, Goal, Path_to_goal, L) :- 
    S = path_len([], 1000000), 
    repeat, 
    arg(2, S, Limit), 
    ( findPath(Limit, [Start], Goal, Cost, 0, Path) 
    -> ( Cost < Limit 
     -> nb_setarg(1, S, Path), 
     nb_setarg(2, S, Cost), 
     fail 
     ) 
    ; true 
    ), 
    arg(1, S, Rev), 
    reverse(Rev, Path_to_goal), 
    arg(2, S, L).