4

我有一个 Prolog 函数path(A,B,Path)，它产生板上从 A 到 B 的所有有效路径。

此函数的输出如下所示：

?- path(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
Path = [0, 1, 4, 2] ;
Path = [0, 3, 4, 2] ;
Path = [0, 1, 4, 5, 3, 2] ;

等等等等

它生成包含有效路径的无限列表集。我只是想获得这些路径中最短的路径（不管有多少）。也就是说，我想要一个shortest(A,B,Path)能够在板上产生从 A 到 B 的最短有效路径的函数。

我想要的输出是：

?- shortest(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
false.

我一直在使用setofProlog 中的函数来将所有路径绑定到我对其施加一些长度限制的集合，但我还没有让它工作。

到目前为止，我糟糕的工作看起来像这样。这绝对是错误的，我将不胜感激任何帮助理解如何setof工作以及如何从这组中找到最短的列表。谢谢！

shortest(A,B,MinPath) :-
    setof(Path,path(A,B,Path),MinPath),
    min(length(Path), length(MinPath)).
4

1 回答 1

6

这是迭代深化的经典案例。只需在顶层输入：

?- length(Path, N), path(0, 2, Path).

第一个答案的长度最短。这就是你可以在 Prolog 中非常优雅地做的事情：你开始枚举一个无限集，希望你能在有限的时间后找到你正在搜索的东西。

由于您可能对该长度的所有路径都感兴趣，因此您想要所有路径。否则，您对以上内容感到满意。此外，您可以枚举不同节点的最短路径，node/1图中出现的节点也应该如此。比如说，你有节点 0 到 10，那么node/1可以定义为：

node(N) :-
   between(0,10,N).

shortest(A,B, Minpath) :-
   setof(Min, Path ^ ( node(A), node(B),
                       once( ( length(Path, Min), path(A, B, Path) ) ) ), [Min]),
   length(Minpath, Min),
   path(A, B, Minpath).

然而，这个解决方案有一个问题；确实是一个非常丑陋的捕获。你说：

（不管有多少）

如果根本没有路径，这个解决方案将永远循环。你被警告了。

编辑：为了完整性：我假设path/3如果列表的长度是固定的，则终止。

并得出结论：对于一个具体的简单图，避免循环的更明确的方法是可取的。然而，在很多情况下根本不清楚循环到底是什么（想想模拟一些简单的机器），在这种情况下，迭代深化是非常有效的：头脑中没有聪明的想法，只是利用序言。

最后一点是关于循环的，以防根本没有路径。为了克服这个问题，您需要某种资源有限的计算。SICStus Prolog 提供library(timeout)，其他系统或多或少具有可比性的功能。SWI（最近）call_with_inference_limit/3为此引入（具有相当神秘的界面）。

于 2014-04-20T22:54:58.050 回答