인공지능-2023년 1학기-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), 인공지능, 서울: 한국방송통신대학교출판문화원