프롤로그 프로그램에서 두 노드 사이의 경로 수를 계산하십시오.

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(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, count). 

should return 2 

Answer 1

먼저 당신이주기에 응답 가을이고 종료되지 않습니다, 당신은 두 번 방문 같은 노드를 방지하기 위해 방문한 것의 목록을 유지할 수 검색어 :

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

위의 6 개 경로가 유효하므로 올바른 경로는 2가 아닙니다.

이제 당신이 시도 할 수있는 경로를 계산하기 : 의견 제안하지만 당신은 모든 경로의 목록을 구축하고 길이를 계산 먼저 필요하기 때문에 이것은 매우 효율적인 아니므로

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

.

당신이 계산하기 위해 가능한 모든 경로를 계산하고 nb_getval/2 및 nb_setval/2를 사용하는 당신이 실패 기반 루프를 시도 할 수 Swipl를 사용하는 경우 :

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.