如何从无限集中找到最短长度列表(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.

我一直在玩setofProlog中的函数将所有路径绑定到一个集合,我对它施加了一些长度限制,但我还没有完成它的工作.

到目前为止我的糟糕工作看起来像这样.这绝对是错的,我很感激任何帮助,了解如何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).

然而这个解决方案有一个问题; 确实非常难看.你说:

(但有很多)

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

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

并得出结论:对于具体的简单图表,更明确的方法是避免循环.然而,在很多情况下,根本不清楚一个周期究竟是什么(想想模拟一些简单的机器),在这种情况下,迭代加深是非常有效的:没有聪明的想法在你的头脑中,只是使用的力量序言.

如果根本没有路径,最后会有关于循环的说明.要克服这个问题,你需要某种资源有限的计算.SICStus Prolog提供library(timeout),其他系统具有或多或少的可比功能.SWI(最近)call_with_inference_limit/3为此目的引入了(具有相当神秘的界面).