path - 在 Prolog 的 Graph 中查找所有可能的路径 w/o loops

Question

我收到了逻辑课的家庭作业，但或多或​​少不知道如何解决它...像这样的查询

  ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
  r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],Path).

Prolog 应该返回给定图中所有可能的路径。术语 r(X,List) 定义了图，这意味着可以从节点 X 到达 List 中的节点。在这种情况下，输出将是:

Path = [a,b,c] ;
Path = [a,b,e,d] ;
Path = [a,b,e,f,g] ;
Path = [a,d,e,b,c] ;
Path = [a,d,e,f,g] ;
false.

尽管我掌握了 SE 和网络上针对类似问题的众多解决方案，但我还是太笨了，无法弄清楚如何使用此作业中的图形定义。

我认为 find(Start,...) 应该用 r(Start,List) 中列表的所有成员递归调用，但作为 Prolog 的新手(我们只是做了标准的家谱...... .) 我不知道该怎么做。

任何帮助将不胜感激。我知道我没有太多可以开始的事实，但我已经花了半个晚上试图弄清楚一些事情，直到现在我还没有任何线索。

/编辑:

对于初学者，我认为我需要某种基本情况来中止递归。我觉得应该是吧

find([],_,_).

因为我猜想最后的递归调用没有任何东西可以开始，或者

find(_,[],_).

假设当程序完成处理时，定义相邻节点的术语列表应该是空的。

现在是真正的调用。大概是这样的

find(Start,[r(Start,[Adjacent|Restadj])|Rest],Path):-
           find(???).

我的问题如下:

-如何让程序使用 r(...) 项中列表的成员作为下一个开始？

-如何检查节点是否已被“访问”/如何从 r 中的特定列表中删除节点

-如何将找到的节点放入路径列表中？简单追加？或者使用 [Path|Start] 之类的东西执行递归调用？

如您所见，它并不多。一些有启发性的问题会很好，因为 Prolog 看起来很有趣，因此学习起来很有趣......

---

在使用简洁的 PDT-Eclipse 跟踪工具一段时间后，我想我明白了程序在做什么。我现在不明白的是为什么最后一个节点总是丢失。回溯失败后，例如因为 r(c,[b]) 是下一个找到的项，而 memberchk(b,[b]) 失败是因为否定(这就是我所做的 + 所做的)并且没有其他项与 r(c ,X) 可以找到，它从寻找从节点 b 出发的其他可能性开始，该节点在 r(b,[...]) 中留下了相邻节点。但是为什么程序会忘记将节点c放入Path列表中呢？是否有可能做某种 if-then-else 以防万一

 member(r(Node, Adjacent), Graph),
member(AdjNode, Adjacent),
\+ memberchk(AdjNode, Seen),

失败，仍然将最后一个节点附加到 Path？

Answer 1

我怀疑这里让您感到困惑的是，您必须从显式数据结构中查找数据，而不是从数据库中获取数据。第一次破解可能看起来像这样:

find(_, _, []).
find(Node, Graph, [Node|Path]) :-
    member(r(Node,Adjacent), Graph),
    member(AdjNode, Adjacent),
    find(AdjNode, Graph, Path).

看看我是如何使用 member/2 从图中查找数据的。但是这个解决方案是不正确的，因为它会循环。一个改进可能是这样的:

find(Node, Graph, Path) :- find(Node, Graph, Path, []).

find(_, _, [], _).
find(Node, Graph, [Node|Path], Seen) :-
    member(r(Node, Adjacent), Graph),
    member(AdjNode, Adjacent),
    \+ memberchk(AdjNode, Seen),
    find(AdjNode, Graph, Path, [Node|Seen]).

这个版本与上面的版本基本相同，除了它有一个“已见”列表来跟踪它已经去过的地方。这仍然不会产生您想要的输出，但我认为这足以让您走上正轨。

编辑以响应您的编辑，

For starters, I think I'll need some kind of base case to abort the recursion.

是的。我选择了您的第一个案例，因为我认为您无法在遍历过程中安全地“使用”该图。我想您可以使用 select/3 代替 member/2 并向前传递无此节点的图。这可能是一件有趣的尝试(建议!)。

• How do I make the program use the members of the list in the r(...) term as the next Start?

如前所述，使用 member/2 从图中检索内容。这很有趣，因为您为所需的谓词使用了确切的词。 :)

• How do I check if a node has already been "visited"/ How can I remove a node from a specific list in r

正如我在第二组代码中所演示的，您的辅助谓词有另一个参数，并使用 memberchk/3 或 member/3。

• How do I put the found nodes into the Path list? Simply append? Or execute the recursive call with something like [Path|Start]?

我进行了递归调用。 append/3 会更昂贵。

编辑:根据 Will 的评论使用 findall/3，我们可以一次找到所有路径:

all_paths(From, Graph, Paths) :- findall(Path, find(From, Graph, Path), Paths).

你可以像这样调用它:

?- all_paths(a, [r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
                 r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], AllPaths).

我还没有测试过，但它应该可以工作。