0

如何在无向图中找到所有结束的方法？

Graph :

    Node : S, Y, F, T                visualization :    S ----- Y ---- T
    Edge : S --- Y                                       \     /
           Y --- F                                        \   /
           S --- F                                         \ /
           Y --- T                                          F


Assume that

       Start   S 
       Finish  F

       after run   go 

       result will be :

              S F
              S Y F

我不想多次访问一个节点。如果我访问，这个问题将成为 NP 问题之一。

编辑：

输入可以是任何形式

example:

       edge (S,Y).     OR          edge (Y,S).
       edge (Y,F).                 edge (F,Y).
       edge (S,F).                 edge (F,S).
       edge (Y,T).                 edge (T,Y).

但输出必须相同

4

1 回答 1

1

跟踪访问过的节点，并在下一步添加可能的目的地时排除这些节点。

我更改了一些边缘并添加了一个，以确保当边缘以从 S 到 F 的“错误”顺序列出时它也可以工作。

edge('S','Y').    visualization:    S -- Y -- T
edge('F','Y').                     / \  /
edge('S','F').                    /   \/
edge('Y','T').                   A --- F
edge('A','S').
edge('F','A').

在 prolog 中，这应该大致如下所示：

pathBetween(A,A,_):- !, fail.
pathBetween(S,F,Visited) :- (edge(S,F) ; edge(F,S)),
    append(Visited,[S,F],L),
    write(L).
pathBetween(S,F,Visited) :-
    (   edge(S,A) ; edge(A,S)  ),
    not(member(A,Visited)),
    pathBetween(A,F,[S|Visited]).

您可以使用;手动查找所有解决方案或findall。

?- findall(Visited, pathBetween('S', 'F', []), _).
[S,F][S,Y,F][S,A,F]
true.
于 2012-06-02T10:49:15.877 回答