선교사와 식인종 문제

소개글

인공지능 과목 리포트!!

목차

없음

본문내용

■ 선교사와 식인종 문제
* 문제:
- 세 명의 선교사와 세 명의 식인종이 강의 한 쪽에 있다.
- 강에는 한 명 또는 두 명을 태울 수 있는 보트가 있다.
- 모든 사람을 강의 반대편으로 보내야 한다.
- 강의 어느 한 쪽이던 식인종의 숫자가 선교사의 숫자를 넘으면 안된다.
* 풀이:
1. 초기상태
선교사를 x, 식인종을 y로 두고 배의 상태 z 로 정한다.
처음 초기상태는 3명의 선교사와 3명의 식인종과 출발지점에 배가 있으므로,xxx yyy
z
으로 표현할 수 있다.
2. 목표상태
모든 사람(3명의 선교사와 3명의 식인종)이 강을 건너가 있는 상태이어야 하고, 배가 그쪽에 정박해있어야 한다. 즉,
xxx yyy
z
상태로 되어야한다.
3. 연산자 및 트리
위의 문제에 조건 중에 강에는 한 명 또는 두 명을 태워야 하므로, x, y, xx, xy, yy로 배로 옮겨서 갈 수 있다. 하지만 조건 중에도 강의 한쪽에 식인조의 숫자가 선교사보다 많다면 선교사가 잡아먹히므로 조건에 위배된다. 따라서 쉽게 트리로 표현한다면,
xxx yyy

참고 자료

없음