如何从 prolog 中列表变量的所有统一选项中获取最短列表？

Question

所以我试图获得树中两个节点之间的最短路径。我有path(Start,End,Path)将 Path 统一为从开始到结束的所有可能路线的谓词。因为我想要最短的路线，所以我想获得最短的路径。我应该如何“循环” Path 可以获得的所有选项？谢谢

Answer 1

一个更“经典”的答案是使用其中一个逻辑外谓词setof/3,bagof/3和findall/3。setof/3特别是可以通过巧妙的技巧重新用于计算最小值，但是根据内部变量是否存在量化setof/3，bagof/3可以有点违反直觉地返回不止一次。

假设我们正在使用经典的圣经亲子关系数据库。我们可以有：

father(abraham, isaac).
father(isaac, jacob).
father(jacob, joseph).
father(jacob, benjamin).

等等。假设您想要父亲的列表。这是一种方式：

?- findall(Father, father(Father, _), Fathers).
Fathers = [abraham, isaac, jacob, jacob].

但是你会注意到它jacob在那里两次。你认为，我知道，我会使用setof/3. 然后你得到这个：

?- setof(Father, father(Father, _), Fathers).
Fathers = [jacob] ;
Fathers = [abraham] ;
Fathers = [isaac] ;
Fathers = [jacob].

这里发生的是 Prolog_与某个值统一，而该值限制了结果。换句话说，jacob出现两次是因为他有两个孩子，每个孩子都是_. 解决方案是使用一些特殊语法指定存在量化：

?- setof(Father, Child^father(Father, Child), Fathers).
Fathers = [abraham, isaac, jacob].

该Child^语法有讲的Prolog的一种方式：有一些结合该变量的值，但我不在乎它是什么，我不希望我的结果通过它的限制做的。这样我们就得到了预期的结果。

所以现在我们可以在一个地方获得 path(Start, End, Path) 的所有解决方案：

?- findall(Path, path(Start, End, Path), Paths).

如果您在阅读时遇到问题，我们的意思是“在表达式 path(Start, End, Path) 中找到所有 Path 绑定，并将它们收集到一个新的变量 Paths 中。”

从这里开始，我们可以像对待任何其他列表一样对待它，并通过手动排序或扫描列表来找到最小值，或两者兼而有之。

我之前提到过我们有时会欺骗setof/3进行最小化。如果您确信path/3将在合理的时间内终止——换句话说，findof/3应用到path/3不会产生无限循环——我们可以执行以下技巧：

setof((Len,Path), (path(Start, End, Path), length(Path, Len)), [(_,ShortestPath)|_]).

再让我放纵一下。早些时候我提到的第一个参数setof/3是要查找的变量，它实际上是一个与第二个参数的每个成功结果统一的表达式。所以我们说要在表达式 (Len,Path) 中收集 Len 和 Path 变量。注意：这不是元组！这只是使用,/2运算符的表达式构建。我更倾向于这样写：

setof(Len-Path, (path(Start, End, Path), length(Path, Len)), [_-ShortestPath|_]).

使用 Len-Path 或 (Len,Path) 或任何其他语法来组合 Len 和 Path 之间没有区别。重要的是它们以某种表达方式——任何表达方式——在一起。Prolog 不会自动对 with 进行算术运算，也不会自动与 with-/2进行“和”运算，,/2因此我们可以自由地这样做。另一个重要的细节是我们首先需要长度，因为这setof/3是要排序的。

第三个参数看起来很糟糕，让我们分解一下：

[(_, ShortestPath)|_]   % or: [_-ShortestPath|_]

这只是嵌套在模式中的模式。我们知道至少会有一个结果，所以我们在[Head|Tail]这里使用列表模式。只是我们不关心尾部，所以我们有[...|_]，所以我们要拆开列表的第一个元素。然后我们知道这个列表中的每一项都将具有(Len, Path)第一个子句的结构。所以我们在这里做的是期望得到一个看起来像这样的结果：

[(3, <path>), (4, ...), (5, ...), ...]

我们只想<path>摆脱第一个元素。

请注意，我们不必处理其他情况，因为如果没有解决方案，我们无论如何都应该失败！

综上所述，如果您可以访问像聚合这样的库来为您完成这项工作，请务必使用它。我主要认为了解一个人的选择是有益的。（这个seto/3技巧来自Covington 等人的Prolog Programming in Depth一书）。

编辑：直接走解决方案列表

一个关于Prolog的好东西-甚至在漂亮的东西-是与回溯它会生成所有的解决方案。这使得编写最小化查询变得非常简单，例如：

age(abraham, 103).  age(isaac, 45).
age(jacob, 88).     age(joseph, 46).

youngest(Person) :-
    age(Person, Age),
    \+ (age(_, Younger), Younger < Age).

逻辑上所说的是：最年轻的人是年龄为 Age 的人，这样就没有其他人的年龄小于 Age 。这是解决问题的一种非常可爱的方法；问题是它必须为每个事实遍历整个数据库，直到找到解决方案。这是可悲的低效。

为了更有效地做到这一点，我们必须让自己更明确地表达我们想要做的事情。现在，下一个最明确且可能最清晰的解决方案是使用findall/3生成所有可能性，然后通过递归处理列表来选择正确的可能性。代码可能如下所示：

youngest(Youngest) :-
    findall((Person, Age), age(Person, Age), [(FirstPerson,FirstAge)|People]),
    youngest_loop(FirstPerson, FirstAge, People, Youngest).

youngest_loop(Youngest, _, [], Youngest).
youngest_loop(CurrentPerson, CurrentMinimumAge, [(NextPerson,NextAge)|People], Youngest) :-
    (   (CurrentMinimumAge > NextAge) ->
        youngest_loop(NextPerson, NextAge, People, Youngest)
    ;   youngest_loop(CurrentPerson, CurrentMinimumAge, People, Youngest)).

第一条规则简单地将事实数据库转换成对列表，第二条规则以预期的方式处理该列表，通过携带当前最小值并将每个与当前最小值进行比较来决定是否替换它. 这取决于你在做什么，这可能更有效率或更低，但这是一个更大的话题。

注意: setof/3,bagof/3和findall/3是标准的 Prolog，应该随处可用。这与其说是内置程序，不如说是库程序。

现在，关于在中间带有可调用目标的奇怪行为。这里实际上没有魔法，它只是常规的统一。您可以通过编写一个类似的谓词来证明这一点，比如用数字重复调用一个目标，就像一个循环：

loopy(Start, Stop, Var, Goal) :-
    numlist(Start, Stop, Numbers),
    member(Var, Numbers),
    Goal.

?- loopy(1, 10, X, (write('Generating '), write(X), nl)).
Generating 1
X = 1 ;
Generating 2
X = 2 ;
...etc...

通过将 Var 和 Goal 放在一起，我们能够为 Var using 建立绑定member/2，然后让 Prolog 来“证明”Goal。目标可以是任何 Prolog 表达式，因此括号中的表达式“有效”。但是，Var 与 Goal 中使用的变量匹配很重要，否则您会得到这种看起来很奇怪的行为：

?- loopy(1, 10, Y, (write('Generating '), write(X), nl)).
Generating _G811
Y = 1 ;
Generating _G811
Y = 2 ;
...etc...

希望这能回答您的问题！