[방송통신대학교]인공지능_중간평가_과제물시험(30점 만점)

과제정보

학과	컴퓨터과학과	학년	4학년
과목명	인공지능	자료	6건
공통	(1) (10점) 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라. (나) 탐색 알고리즘에서 고려할 수 있는 경로의 비용 및 평가함수에 대하여 설명하라. (2) (20점)... 더보기 (1) (10점) 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라. (나) 탐색 알고리즘에서 고려할 수 있는 경로의 비용 및 평가함수에 대하여 설명하라. (2) (20점) A* 알고리즘을 이용하여 다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 이동 거리가 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다. (가) 이 문제를 해결하기 위한 평가함수를 정의하라. (나) 이 문제에 대한 탐색트리 및 그 결과에 해당되는 이동 경로를 구하라. 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라(강의자료 32쪽 참고). 접기

목차

1. (1)(가)
1) 맹목적 탐색(blind search)
2) 경험적 탐색(heuristic search)
3) 맹목적 탐색과 경험적 탐색을 탐색의 목적 및 경험적 정보사용에 따라 분류해보면 아래 표와 같다.

2. (1)(나)
1) 경로의 비용
2) 평가함수
3) 알고리즘 별 경로의 비용 및 평가함수

3. (2)(가)

4. (2)(나)

본문내용

상태공간 탐색에 의한 문제풀이에 있어 어떤 순서로 후계 노드를 선택해서 탐색을 하느냐에 따라 여러 가지 방법이 존재하는데, 크게는 아래와 같이 맹목적 탐색과 경험적 탐색으로 나눌 수 있다.

1) 맹목적 탐색(blind search)
확장할 다음 노드를 선택할 때 목표 노드의 위치에 대한 정보를 사용하지 않고, 그와 무관한 규칙이나 틀, 정해진 순서를 통해 노드를 확장하는 탐색 방식이다. 이에 많은 시간과 자원을 소비하는 매우 소모적인 탐색을 할 가능성이 높고, 경우에 따라서는 목표에 도달하지 못할 가능성도 있다. 맹목적 탐색에는 탐색의 진행 방향 즉, 깊이 방향으로 계속 전진하여 목표를 탐색하는 방법인 깊이우선 탐색, 트리의 레벨 순서에 따라 노드를 확장하여 탐색하는 방법인 너비우선 탐색, 출발 노드로부터의 경로 비용이 가장 작은 노드를 우선 선택하여 검사하고 확장하는 균일비용 탐색이 있다.

2) 경험적 탐색(heuristic search)
문제영역에서 사용할 수 있는 목표 노드의 위치와 관련해서 절대적으로 확실한 것은 아니지만, 정답일 가능성이 어느 정도 있어 많은 경우에 잘 들어맞는 경험적인 정보를 사용하여 탐색하는 방법으로, 목표 상태를 보다 신속하게 탐색하기 위해 경험적 지식을 활용한다고 할 수 있다. 경험적 탐색에는 임의의 상태에서 시작하여 목표에 가장 근접한 후계 상태로 이동하는 알고리즘인 언덕 오르기 탐색, 평가함수의 값이 전역 최소치 또는 전역 최대치에 해당되는 해를 구하기 위한 확률적 접근방법인 모의 담금질, 확장할 다음 노드를 결정할 때 그 노드까지 도달하는 경로의 비용과..

<중 략>

(1)(나)
1) 경로의 비용
한 상태에서 다른 상태 또는 어떤 노드에서 다른 노드로 이동하기 위해 필요한 비용을 노드 사이의 경로비용이라고 한다. 이때 비용은 어떤 에너지를 사용하는 것일 수도 있고, 거리를 이동하여 위치를 바꾸는 것일 수도 있는 등 상황에 따라 여러 가지가 될 수 있다.

참고 자료

없음