인공지능연습문제3장풀이

목차

1. 다음과 같이 기관차 L과 객차가 철도에 놓여있는 순서를 스트링 LABCDO로 나타낸다. 기관차와 객차가 임의로 연결 또는 분리될 수 있도록 스위치가 동작될 수 있고, 기관차는 연결된 객차를 밀거나 끌 수 있다고 가정한다. 문자열에 대한 생성법칙을 이용하여 철도 위에 놓일 수 있는 모든 기관차와 객차의 가능성을 표현하도록 구성하라.

2. 어떤 노드 n 와 이의 후계 노드n 에서 n 가 n 로부터 되돌아올 수 없는 경우, n 로부터 n 로 향하는 아크를 회복불가능하다고 한다. 회복불가능한 아크를 갖는 상태공간 그래프로 표현되는 문제의 예를 두 가지 들어라.

3. 다음의 생성법칙에 의하여 정의되는 문법에서 스트링((( ), ( )), ( ), (( ), ( ))) 이 S로부터 얻어질 수 있음을 보여라. 단, 이 생성규칙은 화살표의 왼쪽에 있는 심볼은 오른쪽에 있는 심볼들을 대치할 수 있음을 나타낸다.
4. 5ℓ짜리 물이 가득한 병과 2ℓ짜리 빈 병이 있다. 어떻게 2ℓ짜리 병에 정확히 1ℓ의 물을 넣을 것인가? 단 물은 한병에서 다른 병으로 옮길 수도 있고, 버려질 수도 있다. 그러나 처음에 주어진 5ℓ이상의 물이 될 수는 없다. 이 문제의 해를 얻기 위하여 탐색한 대로 탐색트리를 그려라. 그리고 문제에 대한 상태묘사, 연산자, 목표상태의 검토방법을 정의하라.
4. 5ℓ짜리 물이 가득한 병과 2ℓ짜리 빈 병이 있다. 어떻게 2ℓ짜리 병에 정확히 1ℓ의 물을 넣을 것인가? 단 물은 한병에서 다른 병으로 옮길 수도 있고, 버려질 수도 있다. 그러나 처음에 주어진 5ℓ이상의 물이 될 수는 없다. 이 문제의 해를 얻기 위하여 탐색한 대로 탐색트리를 그려라. 그리고 문제에 대한 상태묘사, 연산자, 목표상태의 검토방법을 정의하라.

......

본문내용

4. 5ℓ짜리 물이 가득한 병과 2ℓ짜리 빈 병이 있다. 어떻게 2ℓ짜리 병에 정확히 1ℓ의 물을 넣을 것인가? 단 물은 한병에서 다른 병으로 옮길 수도 있고, 버려질 수도 있다. 그러나 처음에 주어진 5ℓ이상의 물이 될 수는 없다. 이 문제의 해를 얻기 위하여 탐색한 대로 탐색트리를 그려라. 그리고 문제에 대한 상태묘사, 연산자, 목표상태의 검토방법을 정의하라.
① 상태묘사 : 5ℓ짜리 물이 가득한 병과 2ℓ짜리 빈 병이 있다. 2ℓ짜리 병에 정확히 1ℓ의 물을 넣어야 한다. 단 물은 한병에서 다른 병으로 옮길 수도 있고, 버려질 수도 있다. 그러나 처음에 주어진 5ℓ이상의 물이 될 수는 없다.
② 연산자 :
- 5ℓ병에 있는 물을 2ℓ병에 가득 채운 다음 2ℓ짜리 물병을 비운다.
- 다시 한번 2ℓ짜리 물병에 가득 채운 후 물을 버린다.
- 그럼 5ℓ짜리 물병에는 1ℓ의 물이 남아있게 되고 2 물병에는 물이 하나도 없는 상태가 된다.
- 남은 1ℓ의 물을 2ℓ병에 담으면 2ℓ물병에 1ℓ의 물이 넣을 수 있다.
③ 목표상태 : 2ℓ의 물병에 1ℓ의 물을 넣게 된다.

참고 자료

없음