방송대 인공지능 중간과제물 2024학년도 1학기 A`알고리즘과 균일비용 탐색을 이용하여 상태공간 문제 풀이

1. 균일 비용 탐색 경로비용과 노드확장 과정

균일 비용 탐색은 그래프 탐색 알고리즘 중 하나로, 목표 상태에 도달하는 경로의 비용이 동일한 경우에 효과적으로 최적 경로를 찾는 방법이다. 이 알고리즘은 일반적으로 비용이 동등한 노드를 탐색하는 데 집중하므로, 탐색 과정에서 비용이 가장 낮은 경로를 우선적으로 고려하는 방식으로 진행된다. 이 알고리즘의 특정한 구조는 다익스트라 알고리즘과 유사하다. 처음에는 시작 노드를 큐에 추가하고, 그 노드에서 갈 수 있는 인접 노드들로 탐색을 확장해 나간다. 이 과정에서 각 노드까지의 비용을 저장하고, 해당 비용이 더 적은 경로가 발견되면 기존의 경로를 업데이트한다. 초기 설정에서 모든 노드의 비용은 무한대로 설정하고, 시작 노드의 비용은 0으로 둔다. 큐에는 비용이 가장 낮은 노드가 항상 먼저 탐색될 수 있도록 구현해, 최적 경로를 확보하는 것이 핵심이다. 균일 비용 탐색에서의 노드 확장 과정은 다음과 같다. 첫 번째로, 시작 노드를 큐에서 꺼내어 그 노드와 연결된 모든 이웃 노드를 탐색한다. 이웃 노드까지 가기 위한 비용을 계산한 후, 이 비용이 이전에 저장된 비용보다 낮다면 노드의 비…