프롤로그 경로 찾기

Question

다음 술어가 있다면 문, 두 방 사이에 문이 있다고 선언합니다.

door(office, hall).
door(kitchen, office).
door(hall, "dining room").
door(kitchen, cellar).
door("dining room", kitchen).

그리고 술어 문 상태 문의 상태를 선언합니다.

doorstate(hall, office, closed).
doorstate(hall, "dining room", opened).
doorstate("dining room", kitchen, opened).
doorstate(kitchen, office, opened).
doorstate(kitchen, cellar, opened).

그들 사이의 모든 문이 열려있는 경우 두 방 사이에 통로가 있습니다.

두 방 사이에 그러한 통로가 있는지 발견하기 위해 규칙을 어떻게 작성할 수 있습니까?

Answer 1

Prolog의 공포가 너무 빨리 돌아옵니다.

wayopen(Room1,Room2) :- doorstate(Room1, Room2, opened).
wayopen(Room1,Room2) :- doorstate(Room1, RoomX, opened), wayopen(RoomX,Room2).

그래서 나는 단지 당신을 위해 당신의 숙제를하는 것이 아니라, 그것을 이해하는 방법은 다음과 같습니다.

• 문이 결합되어 문이 열린 경우 두 방 사이에 길이 열립니다.
• 첫 번째 길에 다른 방으로 문을 열고 다른 방에서 두 번째 방에 이르는 길이 있다면 두 방 사이에 길이 열려 있습니다.

이 규칙은 한 방향으로 만 문을 통과 할 수 있습니다. 당신의 숙제는 양방향으로 작동하도록하는 것입니다.

홀에서 어디로 갈 수 있습니까?

?- wayopen(hall, X).
X = diningroom ;
X = kitchen ;
X = office ;
X = cellar ;
false.

다음은 다음과 같이 얻을 수있는 모든 객실입니다.

?- wayopen(Room1,Room2).
Room1 = hall,
Room2 = diningroom ;
Room1 = diningroom,
Room2 = kitchen ;
Room1 = kitchen,
Room2 = office ;
Room1 = kitchen,
Room2 = cellar ;
Room1 = hall,
Room2 = kitchen ;
Room1 = hall,
Room2 = office ;
Room1 = hall,
Room2 = cellar ;
Room1 = diningroom,
Room2 = office ;
Room1 = diningroom,
Room2 = cellar ;
false.

Answer 2

관계를 설명해야합니다 (exists_way/2) 그것은 대칭적이고 전이적입니다.

% Base cases
exists_way_(hall, 'dining room').
exists_way_('dining room', kitchen).
exists_way_(kitchen, office).
exists_way_(kitchen, cellar).

% Symmetric
exists_way(R1, R2) :- exists_way_(R1, R2) ; exists_way_(R2, R1).

% Transitive
exists_way(R1, R2) :-
    exists_way_(R1, R3),
    exists_way(R3, R2).

이 코드는 솔루션을 과도하게 생성합니다. 따라서 중복을 나중에 필터링해야합니다.

Answer 3

관계를 설명해야합니다 (exists_way/2) 그것은 대칭적이고 전이적입니다. 표제를지지하는 프롤로그에서 (예 : XSB), 당신은 이러한 관계를 매우 자연스럽게 표현할 수 있습니다.

:- table exists_way/2.

% Open doors
exists_way(hall, 'dining room').
exists_way('dining room', kitchen).
exists_way(kitchen, office).
exists_way(kitchen, cellar).

% Symmetry
exists_way(R1, R2) :-
    exists_way(R2, R1).

% Transitivity
exists_way(R1, R2) :-
    exists_way(R1, R3),
    exists_way(R3, R2).

이 경우 쿼리입니다 exists_way(R1, R2) 정확히 25 개의 고유 한 솔루션을 제공합니다.

Answer 4

학습의 정신으로 : 이것은 프롤로그 코스의 첫 주에했던 조부모 문제와 같은 문제입니다.

Prolog에서 할 수있는 많은 것들이 구조에서 상당히 유사 할 것입니다. 따라서 재귀 사전에 대한 아이디어와 조항이 어떻게 가야하는지, 수정 및 성능을 위해 어떻게 해야하는지 이해하십시오.

예를 들어, 가능한 경우 테일 비 복구를 피해야합니다.