[컴퓨터과학과] 2020년 2학기 인공지능 중간시험과제물 공통(A* 알고리즘 주요개념 등)

목차

8퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. <그림 1>은 풀이할 문제이다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 것 외에 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 움직이는 것을 포함한다. 예를 들어 <그림 2>는 빈 칸을 우측으로 두 칸 움직이는 연산자를 적용한 결과이다. 두 유형의 연산자 모두 1회의 이동으로 계산한다.

(가) A* 알고리즘의 주요 개념을 설명하라.
(나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라.
(다) <그림 1>의 문제를 풀이하는 A* 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.



- 목 차 -

(가) A* 알고리즘의 주요 개념을 설명하라.

(나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라.

(다) <그림 1>의 문제를 풀이하는 A* 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.



<< 함께 제공되는 참고자료 한글파일 >>
1. A* 알고리즘.hwp
2. A* 알고리즘과 그 응용.hwp
3. A* 알고리즘의 특징.hwp
4. A* 허용성.hwp
5. 휴리스틱 함수와 탐색의 효율성.hwp

본문내용

(가) A* 알고리즘의 주요 개념을 설명하라.

A* 알고리즘은 그래프의 시작점부터 도착점까지 도달하는 최단경로 즉, 가장 빠른 경로를 구하는 알고리즘이다. 보다 구체적으로 접근한다면 A* 알고리즘은 현재까지 계산을 한 상태의 노드의 내력 함수와 목적점에 이르는 잔여 비용의 추정치를 향한 수치를 기준 삼아서 해당 노드의 선택 여부를 결정하는 알고리즘이라고도 정의할 수 있다.
A* 알고리즘이 주로 작동하는 형태는 현재 언급하고자 하는 싸이클을 지니고 있다. 출발점(출발노드)에서 이동할 수 있는 노드를 탐색한 후 그 중 이동할 수 있는 노드의 평가함수 값을 구한 후 값이 가장 낮은 노드를 Open 노드에 추가하고 탐색대상으로는 선정되었지만 평가함수 값으로는 선정되지 않은 노드를 closed list에 추가한다. 이후 closed list에 추가된 노드들은 재확인할 필요성이 없고 다시 open노드에 추가된 노드를 기준으로 이동 가능한 노드를 위의 싸이클처럼 반복하여 최단경로를 구하면 된다.


(나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라.




- 중략 -

참고자료

· 없음