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

1. 3개 탐색기법 설명 및 특성 비교

인공지능의 탐색 기법은 문제 해결을 위한 중요한 방법론으로, 다양한 유형의 문제를 해결하는 데 사용된다. 여러 탐색 기법 중 세 가지 대표적인 기법인 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS), 그리고 A 탐색에 대해 설명하고 이들 간의 특성 비교를 통해 이해를 돕겠다. 깊이 우선 탐색은 그래프의 한 노드에서 시작해 해당 노드의 자식 노드를 깊이 있게 탐색하는 방식으로, 한쪽 방향으로 최대한 깊숙이 들어간 후 더 이상 갈 수 없게 되면 마지막으로 방문한 노드로 되돌아가 다른 자식을 탐색하는 방식이다. DFS는 스택을 이용해 구현할 수 있으며, 재귀적으로 호출되는 방식으로 직관적으로 이해할 수 있다. 이 기법은 경로가 길거나 솔루션이 깊은 경우 효과적이지만, 가지치기가 없는 상황에서는 무한 루프에 빠질 수도 있다. 또한, 최적의 솔루션을 보장하지 않기 때문에 동등한 깊이를 가진 노드 중에 더 나은 경로를 찾을 수 없다. 넓이 우선 탐색은 탐색 시작 노드에서 인접한 모든 노드를 먼저 탐색한 후, 그 노드들의 각각의 자식 노드를 탐색하는 방식이다. BFS는 큐를 이용하여 구현된다. 이 방식은 먼저 탐색한 …