2

我的逻辑课程有一个家庭作业，但或多或​​少不知道如何解决它......用一个像这样的查询

  ?- 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 和 Web 上获得了针对类似问题的众多解决方案的窍门，但我不知何故太愚蠢了，无法弄清楚如何在此作业中使用图形的定义。

我认为 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 出发的其他可能性，节点 b 在 r(b,[...]) 中留下了相邻的节点。但是为什么程序忘记将节点 c 放入 Path 列表中呢？是否有可能做某种 if-then-else 以防万一

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

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

4

2 回答 2

3

我怀疑在这里让您感到困惑的是，您不必从数据库中获取数据，而是必须从显式数据结构中找到它。对此的第一次破解可能如下所示：

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]).

这个与上面的版本基本相同，只是它有一个“已看到”列表来跟踪它已经在哪里。这仍然不会产生您想要的输出，但我认为这足以让您走上正轨。

编辑以响应您的编辑，

对于初学者，我想我需要某种基本情况来中止递归。

是的。我选择了您的第一个案例，因为我认为您不能在遍历期间安全地“使用”图表。我想您可以使用该图select/3来代替member/2并继续传递无此节点的图。这可能是一个有趣的尝试（建议！）。

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

如图所示，用于member/2从图中检索事物。这很有趣，因为您使用了您需要的谓词的确切词。:)

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

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

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

我选择了递归调用。append/3会更贵。

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

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).

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

于 2013-05-08T15:04:31.197 回答
2

基于 Daniel Lyons 非常清晰的代码，广度优先搜索：

all_paths(Node, Graph, Paths) :- 
   bfs(Graph, [[Node]-[]], R, []),      % or dfs(...)
   maplist( fst, Paths, R).

fst(A, A-_).        % utility
pair(B, A, A-B).    %  helpers
add(LS,H,[H|LS]).   %   

bfs(_G, [], Z, Z).                % queue is empty
bfs(Graph, [H|Q], [H|R], Z) :- 
    H = Path-Seen, Path = [Node|_],
    findall( Next, member(r(Node, Next), Graph), NS),
    flatten_diff( NS, Seen, WS),  % working set of nodes
    maplist( add(Path), WS, PS),  % new paths
    maplist( pair([Node|Seen]), PS, QH),  % new addition to the queue
    %% append( QH, Q, Q2),        % DFS
    append(    Q, QH, Q2),        % BFS
    bfs(Graph, Q2, R, Z).

（未测试）。flatten_diff(A,B,C)应该展平列表列表A，同时删除列表中也出现的元素B，生成列表C作为结果。

正如 PeterPanter 所注意到的，Daniel Lyons 的代码需要稍作调整，以不排除其结果路径中的最后一个节点。

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

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

现在没有产生空路径，它按预期工作：

11 ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),    r(d,[a,g]), 
              r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], Path).
Path = [a] ;
Path = [a, b] ;
Path = [a, b, c] ;
Path = [a, b, e] ;
Path = [a, b, e, d] ;
Path = [a, b, e, d, g] ;
Path = [a, b, e, d, g, f] ;
Path = [a, b, e, f] ;
Path = [a, b, e, f, g] ;
Path = [a, d] ;
Path = [a, d, g] ;
Path = [a, d, g, f] ;
Path = [a, d, g, f, e] ;
Path = [a, d, g, f, e, b] ;
Path = [a, d, g, f, e, b, c] ;
false.
于 2013-05-08T17:59:03.333 回答