序言上的性能问题

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