如何从无限集合中查找最短长度的列表（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的最短有效路径。

我希望得到的输出为：

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

我一直在尝试使用Prolog中的setof函数来将所有路径绑定到一个集合上，其中我对其设置了一些长度限制，但是我还没有让它工作起来。

到目前为止，我的工作很糟糕。它肯定是错误的，我希望能得到任何帮助，理解setof如何工作以及如何从这个集合中找到最短的列表。谢谢！

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

- Ryan Erdmann

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

然而，这个解决方案有一个缺陷；一个非常丑陋的缺陷。你说过：

(无论有多少条路径)

如果没有任何路径，这个解决方案将会一直循环下去。你已经被警告了。

编辑：为了完整起见：我假设当列表长度固定时，path/3 会终止。

最后总结：对于一个具体的简单图，避免循环的更明确的方法更可取。然而，在许多情况下，什么是循环并不清楚（想象一下模拟一些简单的机器），在这种情况下，迭代加深法非常有效：不需要在脑海中进行 clever thinking，只需利用 Prolog 的强大功能即可。

关于循环的最后一点是，如果没有路径，则需要克服这个问题，你需要某种资源有限的计算。SICStus Prolog提供library(timeout)，其他系统具有更多或更少相当的功能。SWI（最近）引入了call_with_inference_limit/3（接口相当晦涩）以此为目的。

- false