幼稚解决方案的问题在于，如果不消除循环，则从 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 3 规则的 arity 2 规则。我们去过的地方列表最初总是空的。现在我们需要一个基本案例：
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 中，谓词由名称和数量唯一地定义，就像 C++ 或 Java 中的重载一样，其中“有效方法”由参数的数量和名称决定，而不仅仅是名称。
您的直觉是正确的 - 中的空列表canTravel(From, To) :- canTravel(From, To, [])正在为访问过的地点列表建立初始绑定。与其说是分配存储，不如说是建立一个基本案例。
canTravel 本身有两种用途。其中之一是canTravel/3从调用canTravel/2。在这种情况下，canTravel/3它真的有点像一个助手，做 的实际工作canTravel/2，但使用我们初始化为空列表的内部变量。另一个用途是canTravel/3from inside 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），也可能用于将隐式列表分解为 headX和 tail Xs。看看我可以从 repl 中使用它的所有方式：
?- X = hello, Xs = [world, new, user], Y = [X|Xs].
Y = [hello, world, new, user].
这基本上就是我们在 中使用它的方式canTravel：我们有 Through 和 Visited，所以我们正在创建一个新列表，其中以 Through first 和 Visited 作为尾部，这是递归调用的第三个参数。在程序方面，我们只是将通过添加到我们在循环中使用的变量中。
但是因为这是 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)为真：
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] .
您可以看到那里发生了什么：_第二个子句中的 the 被制成匿名变量，因此它生成列表，其中 1 在第一个位置，然后是第二个，然后是第三个，等等。
很多 Prolog 都是这样工作的。这一个也很令人惊讶：
?- length(X, 3).
X = [_G273, _G276, _G279].
希望这有助于澄清一些事情！:)