방통대 인공지능 중간과제물

소개

"방통대 인공지능 중간과제물"에 대한 내용입니다.

목차

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

본문내용

균일비용 탐색 (uniform-cost search)은 그래프에서 시작하는 노드에서 대상으로 하는 노드까지의 최적 경로를 찾기 위해서 가장 낮은 경로 비용을 사용하는 알고리즘이다. 그러므로, 균일비용 탐색은 최소의 비용에 의거하여 우선순위 큐의 방식을 참조해 트리의 가장 높은 곳의 정점인 루트의 노드부터 확장한다. 확장한 노드에서 후계노드가 발생하며, 경로비용은 g(ni) = g(n) + C (n, ni)로 확인된다. 이 때, g(n)은 출발노드부터 노드까지의 경로비용이며, 발생한 후계노드 중 C (n, ni)은 노드(n)에서 노드 (ni) 로 이동하며 발생하는 비용이다 (이광형, 이병래, 2023).

언덕오르기 탐색 (hill climbing)은 출발노드에서 한 노드까지의 소비 경로 비용을 제외하고, 한 노드로부터 목표노드에까지의 최소 경로 비용을 평가함수로 사용한다. 그러므로, 출발부터 목표 노드의 최적의 경로 탐색이 아닌 한 노드부터 목표노드까지만의 예측 경로 비용이 포함되는 임의의 경로를 탐색한다. 노드를 확장하고 후계노드를 구분하기 위해, 방향의 거리와 높이, 목표상태 등을 판단한다. 진행방향을 고려하는 탐색방법으로 현재 상태를 개선해 나갈 수 없는 지역최대치 문제, 고원문제, 능선문제가 있다.

A* 알고리즘 (A* Algorithm)은 출발노드에서 목표노드까지의 최적한 경로를 탐색하는 알고리즘이다. 한 노드에 대한 함수는 출발부터 한 노드까지의 탐색을 진행한 경로비용과, 한 노드부터 목표노드까지의 아직 탐색되지 않은 경험적 지식에 따른 예측 경로 비용을 포함한다. 경험적 규칙의 정확성에 기인하여 함수 결과의 근접성과 효율성에 비례하는 경험적 탐색 방법이다.

참고자료

· 이건명 (2019), 인공지능 튜링 테스트에서 딥러닝까지, 생능출판사.
· 이광형, 이병래 (2023), 인공지능, 한국방송통신대학교 출판문화원.
· 이관용, 김진욱 (2023), 알고리즘, 한국방송통신대학교 출판문화원.
· 이병래 (2023, 03 02). 탐색에 의한 문제풀이 (2) [멀티미디어 강의]. 한국방송통신대학교 U-KNOU 캠퍼스. https://ucampus.knou.ac.kr/ekp/user/lecture/retrieveUCRLecture.do