1. 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하시오.
  (가) 문제를 상태공간에서 표현하기 위해서 정의해야 할 것은 무엇인가?
  (나) 그래프 탐색 알고리즘의 전반적인 골격에 대하여 설명하시오.
  (다) 깊이우선 탐색, 넓이우선 탐색, 언덕 오르기 탐색, 균일비용 탐색, A* 알고리즘을 탐색에 사용되는 정보의 종류와 탐색의 목적에 따라 어떻게 분류할 수 있는지 설명하시오.

2. 계수 최적화 문제에서 발생할 수 있는 지역최대치 문제, 고원 문제, 능선문제에 대하여 논하시오.


1. 우측 그림과 같은 미로를 빠져나오는 문제를 상태공간 탐색 방식으로 풀이하고자 한다. 실선으로 표시된 곳은 통과할 수 없는 벽이며, 한 번의 이동으로 상, 하, 좌, 우 방향 중 한 방향으로 점선으로 구분된 격자 하나를 통과할 수 있다. 입구는 (0, 0) 위치이고, 출구는 (4, 4) 위치이다.

    (가) 상태공간 탐색으로 문제를 풀이하기 위해 이 문제를 표현하시오.
    (나) 깊이우선 탐색 방법으로 이 문제를 풀이하는 과정을 설명하고 탐색 트리를 보이시오.

2. 경험적 탐색 방법에 대해 설명하고, 언덕오르기 탐색과 A* 알고리즘을 비교하여 설명하시오.


1. 다음 용어에 대해 설명하시오. (배점 : 40%)
     (가) 상태 및 상태 묘사
     (나) 문제축소에 의한 문제풀이 방식
     (다) 경험적 탐색
     (라) 지역최대치 문제



1. 다음을 각각 100자 내외로 설명하시오. (배점 : 40%)
    (가) 기호처리 시스템 가설
    (나) 맹목적 탐색 및 경험적 탐색
    (다) 고원 문제
    (라) 상태묘사

2. 균일비용 탐색, 언덕오르기 탐색,  A* 탐색 알고리즘에 대한 다음 질문에 답하시오. (배점 : 60%)
    (가) 각각의 탐색 방법에서 사용하는 평가함수에 대하여 설명하시오.
    (나) 각각의 탐색 알고리즘에서 최적 경로를 탐색하는 것을 보장할 수 있는지에 대하여 설명하시오.