2

我目前正在实施一个序言程序来计算两点之间的最短路径。该框架已存在于 Java 项目中。作为要求，路径必须在 prolog 中实现。因此我使用 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 个元素的路径列表需要 19 毫秒来计算，但 6 秒用于仅包含 38 个元素的列表。

您能提出任何改进建议吗？

提前感谢您的帮助！

4

1 回答 1

2

您可以使用 Dijkstra 算法。我实现了它来回答这个问题。我的代码使用属性变量，我认为应该在 GnuProlog 中工作（我现在将测试）。无论如何，在那里你会找到一个工作纯 Prolog 实现的链接。

编辑好，我认为你可以更正你的代码，因为有一个问题：

Path2在searchPath/3 中它是一个单例：那么您显然将始终以第一个路径结束，并且因为第二个 findPath/3 将始终找到（如果数据库没有更改）与第一个相同的成本和路径，Cost1=<Cost2,将是总是正确的。你可以试试如果

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

对您的任务来说足够快。否则，您将需要实现增量搜索，这并不容易，因为 Prolog 在回溯时“返回”替代路径，然后强制使用某种副作用来选择最小值。

more edit 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).
于 2013-04-04T10:32:19.627 回答