인공지능-2023년 1학기-30점

과제정보

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

소개글

"인공지능-2023년 1학기-30점"에 대한 내용입니다.

목차

1. 3개 탐색기법 설명 및 특성 비교
2. A* 알고리즘을 이용한 8퍼즐 문제풀이

본문내용

1. 3개 탐색기법 설명 및 특성 비교
1) 서론
컴퓨터과학에서 탐색 알고리즘은 문제해결에 매우 중요한 역할을 한다. 탐색 기법은 여러가지가 있고, 기법마다 그 특성이 달라서 해결하고자 하는 문제에 맞는 기법을 사용하면 된다. 예를 들면, 단순히 해가 존재하는지만을 알고 싶어하는 경우라면 신속한 알고리즘을, 해에 도달할 수 있는 최소 비용을 알고싶어 하는 경우라면 신속하지 않아도 정확한 결과를 보장하는 알고리즘을 사용해야 한다. 탐색은 목표노드의 정보를 활용하지 않는 맹목적 탐색과, 효율성을 위해 목표노드에 대한 정보를 활용하는 경험적 탐색방법이 있다. 여러가지 탐색 기법 중, 본 문항에서는 균일비용 탐색과 언덕오르기 탐색, A* 알고리즘에 대해 상호 비교하며 서술하고, 마지막에는 표로 비교점을 정리하겠다.
2) 본론
(1)균일비용 탐색(Uniform Cost Search)
● 정의
균일비용 탐색은 최적의 경로를 찾기 위한 탐색 알고리즘이다. 목표노드의 정보를 활용하지 않는 맹목적 탐색에 속하지만, 탐색할 다음 노드를 찾을 때 가장 적은 경로비용을 가진 노드부터 탐색을 시작한다. 같은 맹목적 탐색에 속하는 DFS와 BFS가 각각 Stack과 Queue를 OPEN의 자료구조로 사용하고 그 특성을 이용하여 다음 탐색할 노드를 선택할 때 단순히 후입선출, 선입선출이라는 담은 순서에 따르는 임의경로 탐색인 것과 비교되는 점이다. 다만, BFS는 특성상 출발노드에서 인접한 노드부터 동일한 depth에 있는 노드들을 하나씩 방문하는 방식이므로, 처음 찾는 해가 최단 경로를 갖는 해가 된다.
● 확장 노드 선택 기준
균일비용 탐색에서는 여러개의 노드들 중 출발노드에서부터의 경로비용이 가장 작은 노드를 탐색한다. 현재 노드 n을 확장한 상태에서 이 노드의 후계노드 n1, n2, …, ni 중 출발노드에서부터의 비용이 최소인 노드를 다음으로 확장하는 것이다. 비용은 노드 n까지 오는데 들었던 경로비용에 n부터 후계노드 ni까지의 경로비용을 더한 값으로 계산하며, g(ni) = g(n) + C(n, ni)으로 정리할 수 있다. 만약 노드들 사이의 경로비용이 모두 같은 값이라면 균일비용 탐색은 BFS와 같은 순서대로 노드를 탐색한다.

참고 자료

이광형⋅이병래 공저(2018), 인공지능, 서울: 한국방송통신대학교출판문화원