(2020-2학기)방송통신대학교 컴퓨터과학과 인공지능 중간고사 출석대체과제물

소개

(2020-2학기)방송통신대학교 컴퓨터과학과 인공지능 중간고사 출석대체과제물

29점/30점

*) ppt파일은 (다)의 탐색트리를 그린 파일이다.

목차

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

본문내용

(가)A* 알고리즘의 주요 개념을 설명하라.
A* 알고리즘은 출발노드로부터 목표노드까지의 최적경로를 탐색하는 탐색 알고리즘이다.
출발 노드에서 시작하여 노드 n을 거쳐 목표 노드까지 도달하는 비용을 f(n)이라고 평가 함수로 정의한다. 노드 n까지는 탐색하면서 진행하고, 이후 n부터 목표노드까지의 경로비용은 탐색하지 않은 경로이기에 정확히 계산하기 어렵거나 불가능하다.

< 중 략 >

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

문제표현 :
A*알고리즘을 사용하여 최소비용으로 목표상태에 도달하는 것을 목적으로 하는 8퍼즐 문제이다. 초기상태에서 조각을 이동시켜서 목표상태를 만들며, 최소비용이란 조각의 이동 횟수를 최소로 하여 목표상태를 만드는 것을 의미한다. 초기상태와 목표상태는 다음과 같다.

참고자료

· 없음