(A+, 만점취득) 방송통신대학교 컴퓨터과학과 인공지능

과제정보

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

소개글

"방송통신대학교 컴퓨터과학과 인공지능"에 대한 내용입니다.

목차

없음

본문내용

상태공간 탐색에서의 탐색 방법은 크게 2가지로 분류할 수 있는데
‘맹목적 탐색’과‘경험적 탐색’이 있다.

- ‘맹목적 탐색’이란‘목표 노드가 어디 즈음에 있을 것이다’라는 식의 고려를 전혀 하지 않고 단순히 미리 정해진 틀에 따라서 탐색 순서를 진행하는 방식을 말한다.
그러므로 이러한 방식의‘맹목적 탐색’은 해에 도달하지 못하게 되는 경우가 발생 될 수 있으며, 또는 해에 도달하는데 많은 자원이나 시간을 소비하게 될 가능성이 있다.
즉, ‘맹목적 탐색’이란 소모적인 탐색을 하게 될 수도 있는 탐색 방법이다.

‘맹목적 탐색’의 대표적인 종류에는
‘깊이우선 탐색’과 ‘너비우선 탐색’ 그리고 ‘균일비용 탐색’이 있다.

우선‘깊이우선 탐색’에 대해 살펴보겠다.
‘깊이우선 탐색’이란 탐색의 진행 방향이 깊이 방향으로 전진하면서 목표를 탐색하는 방법이다. 즉‘깊이우선 탐색’은 후계 노드 중에서 다음 탐색할 노드를 선택할 때
OPEN에 있는 노드들 중에서 가장 최근에 생성된 노드를 확장하도록 하여서 깊이
방향으로 진행하며 이동을 하는 것이다. 그러므로 후입선출의 스택 구조라고 할 수 있다. 이러한‘깊이우선 탐색’을 진행할 때 현재 진행 방향으로 가다가 그 안에서 바로
목표 노드를 찾을 수 있으면 다행이지만, 만약에 목표 노드가 없는 현재 진행 방향 쪽으로 계속해서 탐색을 진행하는 엉뚱한 방향으로 탐색하게 되는 경우가 발생할 수 있다.
그러므로 이러한 불상사를 방지하는 방법으로‘깊이 제한’이라는 것을 정하게 되는데‘깊이 제한’이란 어느 깊이 이상으로 진행하지 않도록 하는 것으로 마냥 무한하게 해가 없는 경로로 소모적으로 탐색하는 것을 막기 위한 것이다. 그래서‘깊이우선 탐색’은
깊이 제한에 도달하거나 더는 진행할 경로가 없는 상태에 도달하게 되면 다른 방향으로의 탐색이 가능한 최근의 상태로 복귀하는 백트래킹을 해서 다시 탐색을 시도하게 된다.

참고 자료

없음