计算Prolog程序中两个节点之间的路径数

Question

我需要一些帮助来计算可以到达目标节点的组合数。

我找到了寻找不同路径的程序。但最后我需要查询

%Edge List (Knowledge Base)

edge(1,2).
edge(1,4).
edge(2,4).
edge(3,6).
edge(3,7).
edge(4,3).
edge(4,5).
edge(5,6).
edge(5,7).
edge(6,5).
edge(7,5).
edge(8,6).
edge(8,7).

%Program

path(X,Y,[X,Y]):- edge(X,Y).
path(X,Y,[X|Xs]):- edge(X,W), path(W,Y,Xs).

-------------------------------------------------

%Query
path(1, 7, P).

%Results
Z = [1, 2, 4, 3, 6, 5, 7];
Z = [1, 2, 4, 3, 6, 5, 6, 5, 7];
.........................

但是，如果我想运行一个查询，告诉我这些路径的数量怎么办。

?-path(1, 7, count). 

should return 2

Answer 1

首先你的回答陷入了循环并且没有终止，你可以保留一个你访问过的列表以避免访问相同的节点两次：

path(X,Y,L):-path(X,Y,L,[X]).

path(X,Y,[X,Y],L):- \+member(Y,L),edge(X,Y).
path(X,Y,[X|Xs],L):- edge(X,W),\+ member(W,L) ,path(W,Y,Xs,[W|L]).

现在如果你查询：

?- path(1, 7, P).
P = [1, 2, 4, 3, 7] ;
P = [1, 2, 4, 3, 6, 5, 7] ;
P = [1, 2, 4, 5, 7] ;
P = [1, 4, 3, 7] ;
P = [1, 4, 3, 6, 5, 7] ;
P = [1, 4, 5, 7] ;
false.

所以有效路径不是2，因为以上6个路径都是有效的

现在计算您可以尝试的路径：

findall(P, path(1,7,P), Paths), length(Paths, N).

如评论中所建议，但这不是很有效，因为您需要首先构建所有路径的列表并计算长度。

如果您使用的是 Swipl，您可以尝试使用失败驱动循环来计算所有可能的路径并使用 nb_getval/2 和 nb_setval/2 来计算：

count(X,Y):-
            nb_setval(counter, 0),
            path(X,Y,_),
            nb_getval(counter, Value),
            New_value is Value+1,
            nb_setval(counter, New_value),
            fail;
            nb_getval(counter, Value),
            write(Value).

示例：

?- count(1,7).
6
true.

计算Prolog程序中两个节点之间的路径数

Counting number of paths between two nodes in Prolog program

algorithm

graph-theory

prolog

graph-traversal