recursion - 查看是否有可能通过Prolog到达火车

我正在使用Prolog处理的问题是，看看火车是否可以从一个目的地到达另一个目的地。有两个规则。

火车可以通过一个或多个中介从一个目的地到达另一个目的地。
例如：旧金山到洛杉矶
洛杉矶飞往尔湾
尔湾飞往圣地亚哥
这给出了一条从旧金山到圣地亚哥的路线。
火车可以往返目的地。因此，如果火车可以从旧金山到洛杉矶，那么它也可以从洛杉矶到旧金山。

这是我目前拥有的代码。

nonStopTrain(sandiego,oceanside).
nonStopTrain(lasvegas,sandiego).
nonStopTrain(sanfrancisco,bakersfield).
nonStopTrain(bakersfield,sandiego).
nonStopTrain(oceanside,losangeles).
nonStopTrain(portland,sanfrancisco).
nonStopTrain(seattle,portland).

canTravel(From, To) :- nonStopTrain(From, To); nonStopTrain(To, From).
canTravel(From, To) :-
    canTravel(From, Through), canTravel(Through, To).

问题是双向旅行的能力。当我运行该程序时，我会在同一位置之间连续第四次运行，但我不确定为什么。

最佳答案

天真的解决方案的问题在于，如果您不消除循环，则有无数种方法可以从A点到达B点。假设我要从西雅图去旧金山。如果没有处理周期，我们将把每个周期作为一个独特的解决方案：

seattle ->  portland -> seattle -> portland -> sanfrancisco
seattle ->  portland -> seattle -> portland -> seattle -> portland -> sanfrancisco
seattle -> (portland -> seattle) x N -> sanfrancisco

对自己重新加倍的次数没有限制，因此，只要连接三个节点，实际上就有无限数量的解决方案。在实践中，您不希望任何解决方案会重蹈覆辙，但是Prolog并不知道这一点，并且没有直觉和天真的方法来阻止它。

前进的更好方法之一是简单地跟踪您去过的地方。为此，我们将需要使谓词有一个额外的论点。首先，我还介绍了一个辅助谓词。

connectedDirectly(From, To) :- nonStopTrain(From, To) ; nonStopTrain(To, From).

当我们真的只想再增加一段路程时，将其分开将减少递归调用canTravel的需求。现在用于canTravel：

canTravel(From, To)    :- canTravel(From, To, []).

这是一个arity 2规则，它映射到我们的新arity 3规则。我们去过的地方清单一开始总是空的。现在我们需要一个基本案例：

canTravel(From, To, _) :- connectedDirectly(From, To).

这应该是显而易见的。现在归纳的情况有所不同，因为我们需要做两件事：找到一条新的路段来附加到旅程中，确保我们之前从未经历过该路段，然后再次出现，将新路段添加到列表中我们去过的地方。最后，我们要确保在开始的地方不会出现较大的循环，因此我们在结尾处添加一条规则以确保我们不会。

canTravel(From, To, Visited) :-
  connectedDirectly(From, Through),
  \+ memberchk(Through, Visited),
  canTravel(Through, To, [Through|Visited]),
  From \= To.

现在，如果运行它，您会找到98个解决方案，并且所有解决方案都是对称的：

?- forall(canTravel(X, Y), (write(X-Y), nl)).
sandiego-oceanside
lasvegas-sandiego
sanfrancisco-bakersfield
... etc.

因此，很高兴，我们能够避免使用广度优先的搜索解决方案。

编辑

我显然通过将名称canTravel重载给两个单独的谓词而使情况感到困惑。在Prolog中，谓词由名称和Arity唯一地定义，就像C ++或Java中的重载一样，其中的“有效方法”由参数和名称的数量而不是名称决定。

您的直觉是正确的-canTravel(From, To) :- canTravel(From, To, [])中的空白列表正在为访问的地点列表建立初始绑定。它并没有像建立基本案例那样精确地分配存储。

实际上，canTravel本身有两种用法。其中之一是从canTravel/3调用canTravel/2。在这种情况下，canTravel/3确实像一个助手，完成canTravel/2的实际工作，但是带有一个内部变量，我们正在将其初始化为空列表。另一个用途是canTravel/3中的canTravel/3，为此我们都使用它来实现相同的目标：递归，Prolog的主要“循环”构造。

canTravel(From, To, _) :- connectedDirectly(From, To)中的第三个参数使该子句成为canTravel/3的一部分。这是递归的基本情况，因此不需要考虑到目前为止我们访问过的地方（尽管归纳法可以防止往返）。我们也可以在这里检查它，但是结果更昂贵，并且对结果集没有影响：

canTravel(From, To, Visited) :- connectedDirectly(From, To), \+ memberchk(To, Visited).

我得出的结论是，如果在不改变答案的情况下增加了费用和复杂性，我们可以省略该检查，从而将基本情况减少为带有匿名第三个变量的原始情况。

在没有过载的情况下看到它可能更有意义，在这种情况下，它看起来像这样：

canTravel(From, To) :- canTravel_loop(From, To, []).

canTravel_loop(From, To, _) :- connectedDirectly(From, To).
canTravel_loop(From, To, Visited) :-
  connectedDirectly(From, Through),
  \+ memberchk(Through, Visited),
  canTravel_loop(Through, To, [Through|Visited]),
  From \= To.

编辑2

关于“酒吧经营者”，您的直觉再次是正确的。 :)我在这里使用它来将项目添加到列表的前面。让您感到困惑的是，在Prolog中，大多数表达式都是统一的，而不是过程。因此，根据上下文，[X|Xs]可能用于构造新列表（如果您手边有X和XS），或者可能用于将隐式列表分为头X和尾Xs。从REPL看一下我可以使用它的所有方式：

?- X = hello, Xs = [world, new, user], Y = [X|Xs].
Y = [hello, world, new, user].

基本上，这就是我们在canTravel中使用它的方式：我们具有“通过”和“已访问”，因此我们以“通过第一”和“被访问”作为尾部创建了一个新列表，这是递归调用的第三个参数。用程序术语来说，我们只是将“通过”添加到循环中使用的变量中。

但是因为这是Prolog，所以我们不仅仅局限于一个方向：

?- Y = [hello, world, new, user], Y = [X|Xs].
X = hello,
Xs = [world, new, user].

?- Y = [hello, world, new, user], [X|Xs] = Y.
X = hello,
Xs = [world, new, user].

请注意，Prolog不在乎分配发生的方向，但是它设法“向后工作”以找出X和Xs应该使用Y。这是Prolog的神奇之处之一。（请注意，在本节的示例中，我省略了由于使点模糊而回显的变量。）

通常，您需要可以解决不同参数的谓词。例如，member/2可用于测试成员资格或枚举项目。 append/3可以从两个旧列表中构建一个新列表，或者可以枚举将列表分为两部分的所有方法，或者可以找到给定列表的前缀或后缀以及后缀或前缀。

当您逐渐习惯了此功能后，您将不再认为Prolog规则就像其他语言中的函数一样，而是开始将它们视为关系：存在于某些结构之间的逻辑“真相”。 member/2并非通过尝试枚举项目或通过查找特定值的列表来编写。它的实现是这样说的：当Item是List中的第一件事时，关系member(Item, List)为true：

member(Item, [Item|_]).

否则，当Item在列表的其余部分中时：

member(Item, [_|Tail]) :- member(Item, Tail).

该定义对于所有可能的用途都是足够的。如果未实例化Item，它将实例化到列表中的第一项，然后实例化到该列表尾部的第一项，依此类推。如果实例化了Item，则如果Item是列表中的第一项或它是尾部的第一项，则为true。令人惊讶的是，member/2甚至可以用于生成包含值的列表：

?- member(1, X).
X = [1|_G274] ;
X = [_G8, 1|_G12] ;
X = [_G8, _G11, 1|_G15] .

您可以看到发生了什么：第二个子句中的_被设置为匿名变量，因此它生成的列表的第一个位置是1，第二个位置，然后是第三个位置，依此类推。

许多Prolog都是这样的。这也很令人惊讶：

?- length(X, 3).
X = [_G273, _G276, _G279].

希望这有助于澄清更多事情！ :)

关于recursion - 查看是否有可能通过Prolog到达火车，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15101123/