소개

Pascal의 책에 있던 경로 탐색 문제를 해결했습니다. Prolog의 일반적인 응용 예입니다.

문제

그림과 같은 도로망이 있었을 때에 1에서 6으로 같은 점을 2번 이상 통과하지 않고 가는 길을 모두 구하라는 문제입니다.

Pascal과 Prolog의 대비

Pascal의 답변 예에서는 인접 행렬을 사용했습니다. 인접 행렬은 그림과 같은 것으로, 도로의 연결 상태를 나타낸 것입니다.



Pascal의 경우, 이 인접 행렬에 의한 것이 일반적일 것이라고 생각합니다. Prolog의 경우 술어로 도로를 나타낼 수 있습니다.

root(1,2).

무향 그래프와 같습니다. 2에서 1로 이동할 수 있습니다. 1,2를 반대로 판정하면 간단하네요.

코드

그래서 Prolog로 쓰면 깔끔하게 쓸 수 있습니다. 아래와 같습니다.

root(1,2).
root(1,3).
root(2,3).
root(2,4).
root(3,4).
root(3,5).
root(4,6).
root(4,5).
root(5,6).

run :- solve(1,[1]),fail.

solve(6,R) :- reverse(R,R1),write(R1),nl.
solve(N,R) :-
  root(N,O),
  \+(member(O,R)),
  solve(O,[O|R]).
solve(N,R) :-
  root(O,N),
  \+(member(O,R)),
  solve(O,[O|R]).

실행

실행하면 다음과 같습니다.

| ?- ['keiro.pl'].
yes
| ?- run.
[1,2,3,4,6]
[1,2,3,4,5,6]
[1,2,3,5,6]
[1,2,3,5,4,6]
[1,2,4,6]
[1,2,4,5,6]
[1,2,4,3,5,6]
[1,3,4,6]
[1,3,4,5,6]
[1,3,5,6]
[1,3,5,4,6]
[1,3,2,4,6]
[1,3,2,4,5,6]
no

Prolog의 특징

백 트랙, 통합은 Prolog의 특징입니다. 이들이 살릴 수 있는 문제일 때에는 무수한 힘을 발휘합니다.

끝에

잠시 Prolog를 떠날 것입니다. Elixir에 집중합니다. Lisp도 Prolog도 훌륭한 프로그래밍 언어입니다. 그러나 그것은 라틴어 같은 존재입니다. 계산기 과학을 습득하기 위해서는 모두 필수라고 생각합니다. 한편, 현대에 있어서의 현대적인 프로그래밍 언어로 현실의 프로그래밍에 도전해 보고 싶습니다. Lisp·Prolog의 습득으로 배운 것을 살려보고 싶습니다. 지금까지 읽어 주셔서 감사합니다.

탄하의 아저씨, 타버렸어… 새하얀데…