2020년도 2학기 인공지능 중간 과제물(참고용, 온라인 평가)

과제정보

학과	컴퓨터과학과	학년	4학년
과목명	인공지능	자료	5건
공통	8퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. <그림 1>은 풀이할 문제이다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 것 외에 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 ... 더보기 8퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. <그림 1>은 풀이할 문제이다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 것 외에 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 움직이는 것을 포함한다. 예를 들어 <그림 2>는 빈 칸을 우측으로 두 칸 움직이는 연산자를 적용한 결과이다. 두 유형의 연산자 모두 1회의 이동으로 계산한다. (가) A* 알고리즘의 주요 개념을 설명하라. (나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라. (다) <그림 1>의 문제를 풀이하는 A* 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라. 접기

소개글

2020년도 2학기 인공지능 중간 과제물(참고용, 온라인 평가)

답만 간단히 기술했습니다. 참고용으로만 사용하시고 그림이나 표 등은 따로 만들어서 첨부하세요.

목차

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

본문내용

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

언덕오르기 탐색이나 최적우선 탐색방법에서는 어떠한 노드n으로부터 목표노드까지 도달하기 위한비용을 평가함수로 사용하고 있다. 이때 출발노드로부터 노드n까지 도달하는 데 소비한 비용은 고려하지 않는다. 따라서 출발노드에서 시작하여 목표노드까지 도달하는 최적의 경로를 탐색하는 것은 보장하지 못한다.
A*알고리즘은 출발노드로부터 목표노드까지의 최적경로를 탐색하는 탐색 알고리즘이다. 그러려면 각각의 노드에 대한 평가함수를 정의해야 한다. 이를 위해 함수 f(n)을 살펴보자
f(n) = g(n) + h(n)
g(n)은 출발노드로부터 노드 n까지의 경로비용이며 h(n)은 노드 n으로부터 목표노드까지의 경로비용이다. 이때 g(n)은 노드 n까지 탐색하면서 진행한 경로이므로 거쳐 온 노드 사이의 경로비용을 합산하면 쉽게 계산이 가능하다.

참고 자료

없음