인공지능 지점을 연결하는 도로망에서 각 지점간 도로의 거리를 나타내는 그림

1. [그림1]은 a~g 지점을 연결하는 도로망에서 각 지점간 도로의 거리를 나타내는 그림이고, [그림2]는 각 지점에서 목적지인 g까지의 직선거리로, 각 도시에서 목적지까지 도달하는 거리의 예측 치로 사용할 수 있다. a 지점에서 출발하여 g 지점에 도착하는 경로를 탐색하려고 할 때, 다음 질문에 답하라.

(가) a 지점에서 g 지점으로 향하는 최단 경로를 찾으려고 한다. 균일비용 탐색 알고리즘으로 문제를 풀이하는 방법을 설명하고, 풀이 과정을 보여주는 탐색트리를 작성하라.

풀이 방법 설명
균일비용 탐색은 시작 노드로부터 현재 노드까지의 누적 경로 비용 g(n)이 가장 작은 노드를 우선적으로 확장하는 방식이다. 목표 노드 g가 추출될 때까지 비용이 낮은 경로를 차례로 탐색하며, 이는 가중치가 있는 그래프에서 최적해를 보장하는 알고리즘이다.
탐색 과정 및 트리 (확장 순서 및 누적 비용 g 표시)
(1) a [0]: 시작 노드 a를 확장한다.
(2) c [3]: a에서 연결된 b(6), c(3) 중 비용이 낮은 c를 확장한다.
(3) d [5]: c에서 연결된 d(3+2=5), b(3+6.5=9.5), e(3+8=11) 중 가장 낮은 d를 확장한다.
(4) b [6]: 남은 후보 b(6), f(5+3=8), e(11) 중…