0

我有以下工作程序：（可以在此站点上进行测试：http: //swish.swi-prolog.org，我删除了指向已保存程序的直接链接，因为我注意到任何人都可以编辑它。）

它在无向图中搜索两点之间的路径。重要的部分是结果在“主”谓词的范围内返回。（在 Track 变量中）

edge(a, b).
edge(b, c).
edge(d, b).
edge(d, e).
edge(v, w).

connected(Y, X) :-
    (
        edge(X, Y);
        edge(Y, X)
    ).

path(X, X, _, []) :-
    connected(X, _).

path(X, Y, _, [X, Y]) :-
    connected(Y, X).

path(X, Z, Visited, [X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], Track).

main(X, Y) :-
    path(X, Y, [], Track),
    print(Track),
    !.

结果：

?- main(a, e).
[a, b, d, e]
true

?- main(c, c).
[]
true

?- main(b, w).
false

我的问题：

  1. 访问节点列表以两种不同的方式传递给谓词。在绑定的 Visited 变量和未绑定的 Track 变量中。这两种不同形式的参数传递的名称是什么？

  2. 通常我只想使用未绑定的参数传递（跟踪变量），将结果放在主谓词的范围内。但是我也必须添加 Visited 变量，因为成员检查对 Track 变量不起作用（我不知道为什么）。是否有可能仅以无限制的方式通过 Track 使其工作？（没有 Visited 变量）

非常感谢！

4

1 回答 1

1

简短的回答：不，你不能避免额外的争论而不使一切变得更加混乱。这是因为这种寻找路径的特定算法需要保持状态；基本上，您的额外论点就是您的状态。

可能还有其他方法可以保持状态，例如使用全局可变变量或动态更改 Prolog 数据库，但两者都更难正确处理，并且会涉及更多代码。

这个额外的参数通常称为累加器，因为它会在您沿着证明树向下移动时累积一些东西。最简单的例子是遍历一个列表：

foo([]).
foo([X|Xs]) :-
    foo(Xs).

这很好，除非您在到达这里之前需要知道您已经看过哪些元素：

bar(List) :-
    bar_(List, []).

bar_([], _).
bar_([X|Xs], Acc) :-
    /* Acc is a list of all elements so far */
    bar_(Xs, [X|Acc]).

这与您在代码中所做的大致相同。如果你特别看这个：

path(X, Z, Visited, /* here */[X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], /* and here */Track).

的最后一个参数在证明树的深度上path/4多了一个元素！而且，当然，第三个参数更长（它随着你沿着证明树向下而增长）。

例如，您可以通过向bar上面的愚蠢谓词添加另一个参数来反转列表：

list_reverse(L, R) :-
    list_reverse_(L, [], R).

list_reverse_([], R, R).
list_reverse_([X|Xs], R0, R) :-
    list_reverse_(Xs, [X|R0], R).

我不知道最后一个参数的任何特殊名称，它在开始时是免费的，并在最后保留了解决方案。在某些情况下，它可能是一个输出参数，因为它意味着在以某种方式转换输入之后捕获输出。在许多情况下，最好避免将参数视为严格的输入或输出参数。例如length/2：

?- length([a,b], N).
N = 2.

?- length(L, 3).
L = [_2092, _2098, _2104].

?- length(L, N).
L = [],
N = 0 ;
L = [_2122],
N = 1 ;
L = [_2122, _2128],
N = 2 . % and so on

注意：您的代码有很多不重要的小问题，在 Stackoverflow 上提供这么多建议并不是一个好主意。如果您愿意，可以将此作为问题提交到Code Review。

编辑：你绝对应该研究这个问题。

我还在这里提供了一个更简单的解决方案。请注意term_expansion/2在编译时使用 for 从无向边生成有向边。更重要的是：你不需要main，只需从顶层调用你想要的谓词。当您放弃切割时，当您的 From 和 To 参数中的一个或两个是自由变量时，您将获得所有可能的解决方案。

于 2016-10-12T06:41:07.510 回答