prolog - 如何从无限集中找到最短长度的列表(Prolog)

Question

我有一个 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 的最短有效路径。

输出 I 想要是:

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

我一直在玩 setof Prolog 中的函数将所有路径绑定(bind)到我对其施加一些长度限制的集合，但我还没有让它工作。

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

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

Answer 1

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

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

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

(however many there are)

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

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

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

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