1. 균일비용 탐색, 언덕오르기 탐색, A 알고리즘을 설명하고, 각 기법의 특성을 서로 비교하라. 2. A 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다. 초기상태와 목표상태는 다음 그림과 같다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 개의 연산자를 사용하며, 어떠한 상태의 비용 역시 교재 및 강의에서처럼

소개

방통대 2023년 1학기 <인공지능> 중간과제물입니다. 직접작성하였습니다. 글과 탐색트리 그림 모두 그대로 사용하셔도 됩니다.

목차

1. 균일비용 탐색, 언덕오르기 탐색, A* 알고리즘을 설명하고, 각 기법의 특성을 서로 비교하라.
2. A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다. 초기상태와 목표상태는 다음 그림과 같다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 개의 연산자를 사용하며, 어떠한 상태의 비용 역시 교재 및 강의에서처럼 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수로 정의한다. 조각의 이동 횟수를 최소화하여 문제를 해결하기 위해 A* 알고리즘에 의해 탐색을 하는 과정을 나타내는 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라(강의 3강 30번 슬라이드 참고).

본문내용

1) 균일비용 탐색
균일비용 탐색(uniform-cost search)는 너비우선탐색이 변형된 것으로, 노드가 시작 노드에서부터 같은 깊이가 아닌 같은 비용의 등심선을 따라 탐색하는 것이다. 만일 그래프의 모든 아크 값이 동일하면 균일비용 탐색은 너비우선 탐색과 같다. 균일비용 탐색은 또한 휴리스틱 탐색의 특수한 경우이다. 경로 비용이 최소인 노드를 선택해 확장하기 때문에 선택된 노드가 목표 노드라면 그 경로는 최소비용 경로이다. 최소비용의 경로 찾기를 보장하며, 8-퍼즐 문제에서는 이동 횟수가 비용이며, 모든 연산자의 적용 비용이 동일하기 때문에 균일비용 탐색은 여기서는 넓이우선 탐색과 동일한 탐색을 한다.

2) 언덕오르기 탐색
언덕오르기 탐색은 평가함수를 사용해 평가함수 값을 감소(증가)시키는 방향으로 탐색하는 방법이다. 깊이우선 탐색에 평가함수를 활용한 형태이다. 언덕오르기 탐색은 최단 경로를 보장해주지는 않으며, 국부최대가 존재할 수 있다. 현재 노드에서 확장할 수 있는 이웃 노드들 중 휴리스틱 평가 값이 좋은 것 하나만을 선택해 확장하므로, 지역 탐색 또는 그리디 알고리즘이라고도 한다. 확장 중인 노드 여러 개를 관리하지는 않으며, 현재 확장 중인 노드만 관리한다. 또한 고도 값이 증가하는 방향으로 이동하여 산의 정상 또는 문제의 최상 솔루션을 찾는 탐색 방법이다. 더 높은 값의 이웃이 없는 소위 피크 값에 도달하면 탐색을 종료한다.

참고자료

· 이수진, et al. 최적경로 탐색을 위한 개선된 양방향 A* 알고리즘. 한국인터넷정보학회 학술발표대회 논문집, 2002, 3.1: 42-45.
· 김영훈; 이상원. A* 알고리즘에 방향 가중치를 적용한 최단거리 경로탐색에 관한 연구. 한국통신학회 학술대회논문집, 2015, 1001-1002.