prolog - 带有先决条件的 Prolog 路径查找

Question

所以我试着自己制作这个程序，但我真的坚持下去了。问题如下：

给定网络中的任务 T，到 T 的路径是一个任务列表，从没有先决条件的任务 X 开始，以 T 结束，并且列表中的每个元素，除了 X，都有它的前任作为先决条件.

• 如果任务 T 没有先决条件，则列表 [T] 给出了它的单一路径。

• 否则，可以通过计算到 T 的先决条件的所有路径的列表并用元素 T 扩展这些路径来找到到 T 的路径。

• 可以通过从空列表开始并附加通向每个连续元素的路径来计算列表 Ts 中任务的所有路径的列表。

定义谓词路径和所有路径以分别计算单个任务和列表中给定任务的路径，例如

?- paths(f,Paths).

Paths = [[b, c, f]]

?- paths(g,Paths).

Paths = [[e, g], [b, c, f, g], [k,h,g]].

先决条件是这样的：

prereqs(e,[]).
prereqs(f,[c]).
prereqs(g,[e,f,h]).

我试图定义路径谓词，但不是一个列表，而是嵌套列表。

add(X, List, [X|List]).

path(T, [H|Hs]) :-
    prereqs(T, []),
    add(T, [], [H|Hs]).

path(T, [H|Hs]) :-
    prereqs(T, [N|_]),
    add(T,[] , Hs),
    path(N, H).

询问时我得到以下答案：

?- path(f, Path).
Path = [[[b], c], f] .

?- path(e, Path).
Path = [e] .

在这一点上，我不明白如何使它正确。

标签： prolog

Answer 1

你很接近，但列表语法似乎让你有点困惑。而且，不幸的是，您的add谓词没有帮助。

让我们尝试了解add在您使用它的两种情况下的含义。在第一个子句中path，你有目标add(T, [], [H|Hs])。我们可以问 Prolog 这意味着什么：

?- add(T, [], [H|Hs]).
T = H,
Hs = [].

所以第一个子句path只能适用Hs于空列表（因此[H|Hs]与 相同[H]）且T与 相同H。因此，我们可以像这样重写该子句：

path(T, [T]) :-
    prereqs(T, []).

这看起来很合理，实际上它是规范相关部分的直接翻译成Prolog：

如果任务 T 没有先决条件，则列表 [T] 给出了它的单一路径。

现在让我们尝试add在 的第二个子句中使用相同的方法path。它采用以下形式：

?- add(T, [], Hs).
Hs = [T].

使用这个等式简化path上面的第二个子句，得到：

path(T, [H, T]) :-
    prereqs(T, [N|_]),
    path(N, H).

请注意，head 中的第二个参数是[H, T]，因为[H|Hs]= [H|[T]]= [H, T]。因此，这只能对二元素列表成功，这就是您所看到的。（每个列表的第一个元素可以是另一个嵌套的二元素列表。）

相反，您正在寻找的是更多类似的东西：

path(T, Path) :-
    prereqs(T, [N|_]),
    path(N, PathToPrerequisite),
    append(PathToPrerequisite, [T], Path).

这仍然有一个错误，它不会找到所有路径，但它至少可以生成它找到的正确格式的路径：

?- path(f, Path).
Path = [b, c, f] ;
false.