프롤로그를 사용하여 경로 찾기

Question

한 지점에서 다른 지점으로가는 경로가 있는지 여부를 찾고 싶습니다. 예를 들어

, 2 -> 4 -> 7 1 -> 3 -> 2 -> 9 5 -> 1 -> 6 -> 8

이러한 경로이다. 프리디 케이트 경로 (시작, 끝)를 작성하고 호는 호 (From, To) 사실 집합으로 표현됩니다.

예를 들어, path (1, 7)가 주어지면이 값은 true를 반환해야합니다. path (6, 1)가 주어 졌을 때 이것은 false를 반환해야합니다. 호가 지시되기 때문에.

Answer 1

1. X와 Y 사이에 호가있는 경우 Path = arc (X, Y)입니다. 즉, arc (X, Y)이면 path (X, Y))이면 입니다. 또는 Prolog에서 다음과 같습니다.

   경로 (X, Y, [호 (X, Y)]) : - 호 (X, Y)

2. 그렇지 않으면 X와 다른 노드 Z 사이에 호가 있고 경로가 Z에서 Y이면 경로가 X에서 Y까지 있습니다. 즉, arc (X, Z) 및 경로 (Z, Y) 다음에 path (X, Y)이면 입니다. 프롤로그에서는 다음과 같습니다 :

   경로 (X, Y, [호 (X, Z) | P]) : - 호 (X, Z), 경로 (Z, Y, P).

취재 this 사이트.

또한 단순히 경로 초등학교 문제가이 문제를 분할 답변을

Answer 2

시도에 대한 아크의 목록을 소요하고 반복적으로 검색 한 술어로이 번들 수 있습니다.

path(From, To) :- 
    arc(From, Intermediate), 
    path(Intermediate, To). 

하지만 경로를 중지해야하는 위치를 알고 계십니까? 그리고 사이클이 있다면, 어떻게됩니까?

그것은 항상 사실 인 path(X, X)이라는 간단한 사례입니다. 위의 규칙에 추가

path(To, To). 

우리는이 사실 보이지만 내 경로 만이 매개 변수를 사용합니다 그럼 그렇지

path(From, To) :- 
    ( From \= To 
    -> arc(From, Intermediate), 
     path(Intermediate, To) 
    ; true 
).