4

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

4

2 回答 2

5

一个更“经典”的答案是使用一个超逻辑谓词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].

语法有一种告诉 Prolog的Child^方法：有一些值绑定了这个变量，但我不在乎它是什么，我不希望我的结果受到它的约束。这样我们就得到了预期的结果。

所以现在我们可以在一个地方获得 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 不会自动进行算术运算，-/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和是标准 Prolog bagof/3，findall/3应该随处可用。这与其说是一个库例程，不如说是一个内置例程。

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

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 建立绑定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...

希望这能回答你的问题！

于 2013-01-25T07:41:22.043 回答
3

您可以使用库（聚合）。

shorter_path(Start, End, MinPath) :-
   aggregate(min(Len, Path),
     (path(Start, End, Path), length(Path, Len)),
     min(Len, MinPath)).
于 2013-01-25T06:53:58.257 回答