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

Question

因此，我试图获取树中两个节点之间的最短路径。
我有谓词path(Start,End,Path)，它将Path统一为从Start到End的所有可能路由。
因为我想要最短的路线，所以我想要最短的路径。
我应该如何“循环”通过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).

如果您在阅读时遇到麻烦，我们的意思是“在表达式路径(开始，结束，路径)中找到所有路径绑定，并将它们收集到新的变量路径中。”

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

我之前提到过，有时我们可以欺骗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不会自动使用-/2进行算术运算，也不会自动将其与,/2一起进行“与”运算，因此我们可以自由地这样做。另一个重要的细节是我们需要先走长度，因为这就是setof/3的排序依据。

第三个参数看起来确实很糟糕，所以让我们分解一下:

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

这只是嵌套在模式中的模式。我们知道至少会有一个结果，因此我们在这里使用列表模式[Head|Tail]。只是我们不在乎尾巴，所以我们有了[...|_]，所以我们将列表的第一个元素拆开了。然后，我们知道该列表中的每个项目都将具有第一个子句中的(Len, Path)结构。因此，我们在这里期望得到的结果如下:

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

并且我们只想从第一个元素中获取<path>。

请注意，我们不必处理其他情况，因为如果没有解决方案，我们还是应该失败!

现在说所有，如果您可以访问诸如Aggregate之类的库来为您完成这项工作，那么请务必使用它。我主要认为了解自己的选择具有启发性。 (此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).

逻辑上所说的是:最小的人是具有年龄的人，因此没有其他年龄小于年龄的人。这是解决问题的一种非常可爱的方法。问题在于，它必须针对每个事实遍历整个数据库，直到找到解决方案为止。可悲的是效率低下。

为了更有效地做到这一点，我们必须辞职，对自己想做的事情更加明确。现在，下一个最明确，可能最清晰的解决方案是使用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结合在一起，我们能够使用member/2为Var建立绑定，然后要求Prolog“证明” Goal。目标本来可以是任何Prolog表达式，所以此处带括号的表达式“很奏效”。重要的是，尽管Var必须与Goal中使用的变量相匹配，否则您会得到这种看上去很奇怪的行为:

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

希望这能回答您的问题!