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

문서 내 토픽

1. 균일비용 탐색

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

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

A* 알고리즘(A* Algorithm)은 출발노드에서 목표노드까지의 최적한 경로를 탐색하는 알고리즘이다. 한 노드에 대한 함수는 출발부터 한 노드까지의 탐색을 진행한 경로비용과, 한 노드부터 목표노드까지의 아직 탐색되지 않은 경험적 지식에 따른 예측 경로 비용을 포함한다. 경험적 규칙의 정확성에 기인하여 함수 결과의 근접성과 효율성에 비례하는 경험적 탐색 방법이다. 노드에 대한 평가함수는 f(n) = g(n) + h(n)으로 정의되며, f(n)의 최소 노드값을 선택하여 최소 비용 경로를 발견한다. g(n)는 출발 노드에서 시작하여 노드 n 까지의 경로비용이며, h(n)는 노드 n에서 시작하여 목표노드까지의 예측치 경로 비용이다.
4. 8퍼즐 문제 풀이

A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하는 과정을 나타내는 탐색트리를 구하였다. 초기상태와 목표상태가 주어졌으며, 연산자는 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 개의 연산자를 사용하였다. 상태의 비용은 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수로 정의하였다. 평가함수 f(n) = g(n) + h(n)을 사용하여 최소 비용 경로를 찾았으며, g(n)은 빈칸의 이동횟수, h(n)은 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수이다.

Easy AI와 토픽 톺아보기

1. 균일비용 탐색

균일비용 탐색(Uniform Cost Search)은 그래프 탐색 알고리즘의 한 종류로, 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 각 노드까지의 비용이 동일하다는 가정 하에 작동하며, 비용이 가장 낮은 경로를 선택합니다. 이는 다익스트라 알고리즘과 유사하지만, 다익스트라 알고리즘은 가중치가 있는 그래프에 적용되는 반면, 균일비용 탐색은 가중치가 없는 그래프에 적용됩니다. 균일비용 탐색은 단순하고 직관적이며, 최단 경로를 찾는 데 효과적이지만, 그래프의 크기가 크거나 복잡한 경우에는 다른 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.
2. 언덕오르기 탐색

언덕오르기 탐색(Hill Climbing Search)은 그래프 탐색 알고리즘의 한 종류로, 현재 상태에서 가장 좋은 상태로 이동하는 방식으로 작동합니다. 이 알고리즘은 지역 최적해를 찾는 데 효과적이지만, 전역 최적해를 찾는 데는 한계가 있습니다. 언덕오르기 탐색은 간단하고 빠르게 실행되지만, 문제의 복잡도가 높거나 해당 문제에 적합하지 않은 경우에는 최적의 해를 찾지 못할 수 있습니다. 따라서 문제의 특성을 잘 파악하고, 적절한 알고리즘을 선택하는 것이 중요합니다.
3. A* 알고리즘

A* 알고리즘은 그래프 탐색 알고리즘의 한 종류로, 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 현재 상태에서 목표 상태까지의 실제 비용과 추정 비용을 합한 값을 기준으로 탐색을 수행합니다. A* 알고리즘은 다익스트라 알고리즘과 유사하지만, 추정 비용을 사용하여 더 효율적으로 탐색을 수행할 수 있습니다. 이 알고리즘은 다양한 분야에서 널리 사용되며, 특히 경로 계획, 게임 AI, 로봇 제어 등의 분야에서 중요한 역할을 합니다. A* 알고리즘은 최적의 해를 찾을 수 있으며, 다른 알고리즘에 비해 더 빠른 수행 속도를 보입니다.
4. 8퍼즐 문제 풀이

8퍼즐 문제는 그래프 탐색 알고리즘을 활용하여 해결할 수 있는 대표적인 문제입니다. 이 문제는 3x3 격자에 숫자 1부터 8까지가 배치되어 있고, 빈 공간이 하나 있는 상태에서 특정 목표 상태로 만드는 것이 목적입니다. 이를 위해 다양한 알고리즘, 예를 들어 BFS(너비 우선 탐색), DFS(깊이 우선 탐색), A* 알고리즘 등을 사용할 수 있습니다. 각 알고리즘은 문제 해결 방식과 성능이 다르므로, 문제의 특성과 요구사항에 따라 적절한 알고리즘을 선택해야 합니다. 8퍼즐 문제는 그래프 탐색 알고리즘을 이해하고 구현하는 데 있어 좋은 실습 문제가 될 수 있습니다.

주제 연관 토픽을 확인해 보세요!

주제 연관 리포트도 확인해 보세요!