그래프에서 X에서 Y까지의 두 가지 다른 경로

Question

다음 프롤로그 질문과 함께 생겼습니다 : 사이클이없는 그래프의 가장자리를 사실로 지정하십시오. 예컨대 :

edge(a, b). 
edge(b, c). 
edge(c, d). 
edge(c, e). 
... 

내가 정점의 X와 사이에 두 개의 서로 다른 경로가 있는지 여부를 테스트하는 술어를 작성해야 Y. 예 : 노드 A에서 노드 C에 두 개의 서로 다른 경로가있는 경우 two_paths(a, c).가 true를 돌려 전화. 두 꼭지점 사이의 경로가 있는지 확인하는 방법을 알고 있습니다 :

path(X, Y) :- edge(X, Y). 
path(X, Y) :- edge(X, Z), path(Z, Y). 

그러나 두 개의 다른 경로를 확인하려면 어떻게해야합니까? 당신의 도움을 주셔서 대단히 감사합니다.

Answer 1

생성 된 경로를 반환하고 다른 두 경로를 쿼리하는 조건 자 을 만드는 것이 좋습니다. 뭔가 같이 :

?- path(a,c,L). 
L = [a, b, c] ; 
false. 

지금 당신이 술어 구성 할 수 있습니다 :

이제 path(a,c,T)

path(X,Y,[X,Y]) :- edge(X,Y). 
path(X,Y,[X|T]) :- edge(X,Z), path(Z,Y,T). 

는 당신에게 경로가 표시됩니다 즉

two_paths(X,Y) :- 
    path(X,Y,La), 
    path(X,Y,Lb), 
    dif(La,Lb). 

을, 당신은 당신을 위해 구성 할 프롤로그 요청 경로 La, 다음에 경로 Lb을 구성한 다음 동일하지 않은지 확인하십시오 (dif(La,Lb)). 첫 번째로 구성된 Lb은 La과 같지만 Prologs 역 추적 메커니즘으로 인해 조건이 성공할 수있는 다른 경로를 구성하려고 시도합니다. 이것은 오히려 순수한 Prolog 구현입니다 (잘라 내기 (!), once/1 등). 두 번째 호출에서 작업을 "다시 실행"하기 때문에보다 효율적인 방법이 존재합니다.

보다 효율적인 접근 방법은 조건부에 대한 첫 번째 생성 된 경로를 입력하여 주어진 시점에서 적어도 어느 시점에서 프로그램을 강제 실행하는 조건부 path_avoid/3 (또는 path_avoid/4)을 구성하는 것입니다. 나는 이것을 잠재적 인 운동으로 열어 둔다.