재귀를 통해 단계를 세고 싶습니까?

Question

이 입방체는 가장자리입니다. 왼쪽에서 오른쪽으로, 앞뒤로 그리고 위에서 아래로 갈 수 있습니다.

edge(a,b). 
edge(a,c). 
edge(a,e). 
edge(b,d). 
edge(b,f). 
edge(c,d). 
edge(c,g). 
edge(d,h). 
edge(e,f). 
edge(e,g). 
edge(f,h). 
edge(g,h). 

아래의 방법으로 우리는 A-H에서 갈 수 있는지 확인할 수 있습니다. cango (A, H).

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

move2를 사용하면 필요한 단계를 계산할 수 있습니다.

move2(X,Y,N):- N is N+1, edge(X,Y). 
move2(X,Y,N):- N is N+1, edge(X,Z), move2(Z,Y,N). 

어떻게 구현하나요?

Answer 1

move2(X,Y,1):- edge(X,Y), ! . 
move2(X,Y,NN):- edge(X,Z), move2(Z,Y,N), NN is N+1 . 

Answer 2

Prolog에서 평소처럼 산술 평가를 수행하지만 지정은 평소대로 작동하지 않습니다.

move2(X,Y,N,T):- T is N+1, edge(X,Y). 
move2(X,Y,N,T):- M is N+1, edge(X,Z), move2(Z,Y,M,T). 

을하고 첫 번째 통화에서 0 N 초기화 : 그럼 당신은 값을 증가하는 새로운 변수를 도입 할 필요가있다. 그러한 추가 변수 (우리의 경우 T)는 종종 누적 기이라고합니다.

Answer 3

(is)/2은 두 번째 인수에서 인스턴스화에 매우 민감합니다. 이는 완전히 관계형으로 사용할 수 없다는 것을 의미합니다. X is 1+1.에게 물어볼 수도 있습니다. 2 is 1+1.에게 물어볼 수도 있지만 물어볼 수는 없습니다 : 2 is X+1.

따라서 (is)/2과 같은 술어로 프로그래밍 할 때 술어와 함께 사용할 모드를 상상해보십시오. 이러한 고려 사항으로 인해 오류가 발생하기 쉽습니다 (특히 방금 시작한 경우). 하지만 걱정하지 마라. 더 능숙한 프로그래머는 여전히 그런 문제에 빠져 든다.

몇 가지 Prolog 시스템에는 깨끗한 대안이 있습니다. SICStus, YAP, SWI에는 정수 사이의 관계를 표현할 수있는 library(clpfd)이 있습니다. 보통이 라이브러리는 제약 프로그래밍에 사용되지만 정수로 (is)/2을 안전하고 깨끗한 대체물로 사용할 수도 있습니다. 더군다나,이 라이브러리는 종종 결과 코드가 (is)/2과 비슷한 속도로 매우 효율적으로 컴파일됩니다. 그래서 지금 다시 프로그램

 
?- use_module(library(clpfd)). 
true. 

?- X #= 1+1. 
X = 2. 

?- 2 #= 1+1. 
true. 

?- 2 #= X+1. 
X = 1. 

, 당신은 간단하게 쓸 수 있습니다 : 필요에 따라

 
move2(X,Y,1):- edge(X,Y). 
move2(X,Y,N0):- N0 #>= 1, N0 #= N1+1, edge(X,Z), move2(Z,Y,N1). 

이제 모든 거리를 얻을.

그러나 더있다 ...

가 move2/3이 실제로 종료 있는지 확인하려면, 시도 :

 
?- move2(A, B, N), false. 
false. 

이제 우리는 move2/3 항상 종료 확신 할 수 있습니다. 항상? 당신이 더 우위를 추가 한 가정 :

이

edge(f, f). 

이제 위의 질의가 반복됩니다.그러나 여전히 당신은 당신의 프로그램을 당신의 이익을 위해 사용할 수 있습니다! 노드의 수를 결정 :

 
?- setof(C,A^B^(edge(A,B),member(C,[A,B])),Cs), length(Cs, N). 
Cs = [a, b, c, d, e, f, g, h], 
N = 8. 

그래서 가장 긴 경로는 7 조치를 취할 것입니다!

이제하지만 지금은 값으로 N을 제한함으로써, 쿼리를 다시 요청할 수 있습니다 같거나 내지 7 이하 :이 추가 제약 조건으로

 
?- 7 #>= N, move2(A,B, N), false. 
false. 

, 다시 종단 정의가! 루프가 없습니다.