Prolog를 이용한 Hanoi Tower 및 FWGC Problem
분야
hwp1. 서론
2. 본론
2.1 Hanoi Tower Problem
2.1.1 설명
2.1.2 소스 파일
2.1.3 실행 결과
2.1 FWGC Problem
2.2.1 설명
2.2.2 소스 파일
2.2.3 실행 결과
3. 결론
4. 참고문헌
Prolog는 1973년 프랑스의 Alan Colmerauer가 개발한 논리형 프로그래밍 언어이다. 이 언어는 사실(Fact)와 규칙(Rule)로 이루어진 술어 논리식을 통해 데이터베이스를 구축하고, 이를 기반으로 증명을 계산하는 새로운 형태를 띄고 있다. 즉 프로그램 자체는 논리식의 형태이며, 해당 프로그램을 실행하는 처리기(Interpreter 혹은 Compiler)가 그것을 증명하는 것이다.
프로그램을 순차적인 작업이 아니라 논리식으로 작성하는 특징 때문에, 추상적인 분야를 간결하게 표현할 수 있다. 이에 따라 인공지능, 계산 언어학, 자연어 처리등의 항목에서 많이 사용된다.
이 Prolog를 이용해 Hanoi Tower Problem과, FWGC(Farmer-Wolf-Goat-Cabbage) Problem을 해결하는 프로그램을 작성해보고, 그 특징을 알아보고자 한다.
2. 본론
문제에 대한 간략한 해제와 실행 프로그램 및 결과이다.
2.1 Hanoi Tower Problem
2.1.1 설명
Hanoi Tower Problem은 세개의 기둥과 이 기둥에 꽂을 수 있는 원판이 있고, 이 원판은 큰 것부터 작은 것 까지 순서대로 한 기둥에 꽂혀 있을 때, 이 원판들을 다른 기둥에 원래 순서대로 위치하게 이동하는 것이 목적인 문제이다. 이는 다음 두가지 조건을 만족해야 한다.
(1) 한번에 하나의 원판만 옮길 수 있다.
(2) 큰 원판이 작은 원판위에 있어서는 안된다.
이 문제는 재귀를 이용한 대표적인 문제이다.
2.1.2 소스 파일
/* 실행용 */
test(X) :- move(X,left,right,center).
/* 디스크 이동 */
move(1,X,Y,_) :-
write('Move top disk : '),
write(X), write(' -> '), write(Y), nl.
move(N,X,Y,Z) :-
N>1, M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
George F. Luger, 2005, Artificial Intelligence : Structure and Strategies for Complex Problem Solving 5th E. , ADDISON WESLEY
