프롤로그 무한 루프 (순환 그래프)

Question

이것은 간단한 문제 일 수 있지만 다르게해야합니다. 문제는 내가 비행 기록에서 가능한 비행 경로를 찾아야한다는 것입니다.

route(X,Y):-from_to(X,Y). 
route(X,Y):-from_to(X,Z), route(Z,Y). 

: 나는이 지식 기반

from_to(fresno,seattle). 
from_to(fresno,albany).   
from_to(albany,dallas).  
from_to(fresno,boston). 
from_to(dallas,seattle).   
from_to(dallas,albany). 
from_to(seattle,dallas).   
from_to(seattle,omaha).   
from_to(atlanta,albany). 
from_to(atlanta,dallas). 
from_to(atlanta,boston). 
from_to(omaha,atlanta).   
from_to(omaha,albany). 
from_to(albany,seattle). 

이 그리고 나는 우리가 내가 무슨 짓을 Y로 X에서 갈 수 있는지 확인하는 술어 경로 (X, Y)를 확인해야하는 것은 이것이다

그러나 그래프가 순환하기 때문에 작동하지 않습니다. 나는 인터넷에서 검색했고 모두가 말한 유일한 것은 목록을 사용하고 방문 경로를 확인하는 것입니다. 하지만 목록을 사용할 수는 없습니다! 목록을 사용하지 않고 술어 경로 (X, Y)를 만들어야합니다. 목록없이 이것을 수행하려면 어떻게해야합니까? 는

Answer 1

route(X0,X) :- 
    from_to(X0,X1), 
    closure0(from_to,X1,X). 

closure0/3의 정의에 대한 this question을 참조하십시오 감사합니다. 그래프는 소스 코드에 정의되어 있기 때문에

1 ?- route(fresno, omaha). 
true ; 
false. 

2 ?- route(fresno, omaha). 
true ; 
false. 

3 ?- route(fresno, fresno). 
false. 

4 ?- route(atlanta, atlanta). 
true ; 
false. 

가 대안이 될 수있다 :

Answer 2

내가

:- dynamic visited/1. 

route(X,Y) :- retractall(visited(_)), route_(X,Y). 
route_(X,Y) :- from_to(X,Y). 
route_(X,Y) :- from_to(X,Z), \+ visited(Z), asserta(visited(Z)), route_(Z,Y). 

테스트를 시도 할 것

:- dynamic from_to/2. 

route(X,Y):-retract(from_to(X,Y)). 
route(X,Y):-retract(from_to(X,Z)), route(Z,Y). 

하지만 첫 번째 호출 후

, KB를 다시로드해야합니다.

Answer 3

SWI-Prolog의 사용이 엄격히 요구되지 않는 경우, 표를 지원하는 Prolog 시스템에서 쉽게 수행 할 수 있습니다. B-프롤로그에서, 난 그냥 :- table route/2.을 추가하고 지금은 작동합니다

?- route(fresno, omaha). 
yes 

?- route(fresno, fresno). 
no 

?- route(atlanta, atlanta). 
yes 

?- route(atlanta, X). 
X = albany ?; 
X = dallas ?; 
X = boston ?; 
X = seattle ?; 
X = omaha ?; 
X = atlanta 
yes 

Answer 4

그래서 당신이 목록을 사용할 수 없습니다 (I 이유가 궁금)하지만 당신은 카운터 변수를 사용할 수 있습니까? iteratively deepening search을 먼저 시도해보십시오. 먼저 깊이 1에서 깊이 우선 검색을 수행 한 다음 2 등으로 시도하십시오. 그렇게하면 사이클이 무한 루프를 막을 수 있습니다.

연결이없는 경우 무한 루프가 발생하지 않도록 검색 깊이의 상한선을 기억하십시오.