1

Prolog でグラフ内のパスを見つけようとしています。オンラインで見つけたスニペットを使用して、これを機能させることができました。ただし、同じエッジに 2 回アクセスしないようにする必要がある一方で、2 回アクセスしないようにノードを追跡します。これはおそらくほとんどのグラフで同じことになりますが、エッジ上のポイントからエッジ上の他のポイントへのパスを計算するために使用したいので、ポイントから隣接するノードへのパスを返してはなりません。反対側のノード (たとえば、ノード A からノード C へのエッジ AC があり、点 B が中間にある場合、ACB は AC を 2 回移動するため、受け入れられるパスではありません)。

これが私の現在のコードです：

path(A,B,Nodes,Edges) :- path1(A,[B],Nodes,Edges).
path1(A,[A|P1],[A|P1],[]).
path1(A,[Y|P1],Nodes,Edges) :- 
   connected(X,Y,Edge), \+ memberchk(X,[Y|P1]), path1(A,[X,Y|P1],N1,E1), append(E1,[Edge],Edges).

connected(a,c,ac). % connected(Node1,Node2,Edge) need not represent an edge:
connected(a,b,ac). % it may also refer to a point on the edge.
connected(b,c,ac).

上記の例では、たとえば次のように返されます。

path(a,b,[a,b],[ac])
path(a,b,[a,c,b],[ac,ac])

これで、同じエッジがパスに 2 回入らないようにするために\+ memberchk(X,[Y|P1])を単純に置き換えることができると考えました。これで問題は解決します。\+ memberchk(Edge,S)しかし、私がそうすると、Prologはパスがないと言っています。

誰かがこれがどこで間違っているのか説明できますか?

4

1 に答える 1

0

この答えは私を大いに助けてくれました.ループをチェックするためにまだインスタンス化されていないパスを使用できないためです. の使用を提案してfreeze\2いますが、JIProlog でそれを処理する方法がわかりません。そのために新しい質問を開きます。

于 2012-10-04T18:32:18.077 に答える