추론 과정
질문을 받은 Prolog는 어디서부터 찾기 시작할까?
목표와 연쇄
목표까지 이어지는 길을 찾습니다
Prolog는 질의를 목표(goal)라고 부릅니다. 목표가 참임을 증명하려면, 사실에서 목표까지 이어지는 규칙의 연쇄를 찾아야 합니다.
P1, P2, Q는 명제 하나씩입니다. 이렇게 맞춰 가는 일을 매칭 또는 해결(4편의 해결과 같은 것)이라고 합니다.
전방 연쇄
사실에서 출발해 올라갑니다
전방 연쇄(forward chaining)는 창고의 사실과 규칙에서 출발합니다. 규칙으로 새 사실을 만들어 가다가 목표에 닿으면 끝납니다. 아래에서 위로 가서 상향식이라고도 합니다.
6편에서 모은 창고의 father 사실 셋과 규칙 셋을 썼습니다. 맞는 답이 많을 때 잘 맞는 방식입니다.
후방 연쇄
목표에서 출발해 내려갑니다
후방 연쇄(backward chaining)는 목표에서 출발합니다. 규칙의 몸을 부분 목표(subgoal)로 삼아 내려가 사실에 닿으면 끝납니다. 맞는 답이 적을 때 잘 맞고, Prolog가 쓰는 방식입니다.
하향식이라고도 합니다. 맨 위는 6편의 규칙이고, Y에 fred를 먼저 넣어 보는 과정은 다음 장에서 봅니다.
백트래킹
막히면 갈림길로 되돌아갑니다
부분 목표 하나를 증명하지 못하면, 앞의 부분 목표로 되돌아가 다른 답을 찾습니다. 이것이 4편에서 본 백트래킹입니다. 되돌아갈 때 변수에 묶었던 값도 풉니다.
앞 장의 Y를 정하는 자리입니다. 규칙 단계는 빼고 father로 적었습니다. 이렇게 한 갈래를 끝까지 내려가 본 뒤 다음 갈래로 가는 것을 깊이 우선 탐색이라고 합니다.
되돌아온 뒤
멈춘 곳에서 이어 찾습니다
되돌아왔을 때 창고를 처음부터 다시 보지 않습니다. 앞서 멈춘 줄의 다음 줄부터 이어서 맞춰 봅니다.
앞 장의 첫 부분 목표 father(bill, Y)를 창고와 맞춰 보는 모습입니다.
백트래킹의 값
길이 많으면 오래 걸립니다
백트래킹은 모든 부분 목표의 가능한 증명을 빠짐없이 찾아볼 수 있습니다. 그 대신 갈래가 많으면 시간과 메모리가 많이 듭니다.
갈래가 아홉인 예시입니다. 마지막 갈래에서야 답이 나오는 경우를 그렸습니다. 횟수 12는 가운데 마디 셋과 맨 아래 마디 아홉을 더한 것입니다.
다음 편