Uniform-Cost Search

BFS의 한계와 UCS의 필요성

Breadth-First Search는 얕은 깊이의 노드부터 차례대로 확장한다. 이 전략은 모든 간선의 비용이 동일할 때는 최적이지만, 간선 비용이 다르면 문제가 생긴다. BFS는 "몇 번 이동했는가"만 보지, "얼마나 비용을 썼는가"는 보지 않기 때문이다.

예를 들어, 출발지에서 목적지까지 고속도로(비용 1)와 국도(비용 5)가 있다면, BFS는 둘 다 "한 번 이동"으로 취급하여 국도를 선택할 수 있다. UCS는 누적 비용 $g(n)$을 기준으로 하므로 고속도로를 먼저 탐색한다.

알고리즘 동작 원리

UCS는 Best-First Search에 $f(n) = g(n)$을 넘긴 것과 같다. AIMA (Russell & Norvig, 2021)에서는 단 한 줄로 정의한다¹.

function UNIFORM-COST-SEARCH(problem) returns solution or failure
    return BEST-FIRST-SEARCH(problem, PATH-COST)

내부 동작을 풀어쓰면 다음과 같다.

1. 시작 노드를 Priority Queue에 삽입한다. 키는 $g = 0$이다.
2. 큐에서 $g(n)$이 가장 작은 노드를 꺼낸다.
3. 꺼낸 노드가 목표이면 경로를 반환한다.
4. 그렇지 않으면 인접 노드 각각에 대해 $g(\text{neighbor}) = g(n) + c(n, \text{neighbor})$를 계산한다.
5. 아직 방문하지 않았거나, 기존보다 더 짧은 경로를 발견했으면 큐에 삽입(또는 갱신)한다.
6. 큐가 빌 때까지 반복한다.

핵심은 노드를 큐에서 꺼내는 시점에 그 노드까지의 최단 비용이 확정된다는 것이다. 이미 확장된 노드는 다시 처리하지 않아도 된다 — 비용이 음수가 아닌 한, 나중에 더 싼 경로로 도달하는 것은 불가능하기 때문이다.

탐색 예시

아래 가중 그래프에서 S에서 G까지의 최단 경로를 UCS로 찾는 과정을 보자.

Step 1 — S를 확장한다 ($g = 0$). 인접한 A ($g = 1$)와 B ($g = 4$)가 큐에 들어간다.

Step 2 — 큐에서 $g$가 가장 작은 A ($g = 1$)를 꺼내 확장한다. C ($g = 1 + 5 = 6$)와 D ($g = 1 + 8 = 9$)가 큐에 들어간다.

Step 3 — B ($g = 4$)를 확장한다. D까지의 새 경로 비용이 $4 + 1 = 5$로, 기존 경로($g = 9$)보다 저렴하므로 D의 $g$를 5로 갱신한다.

Step 4 — D ($g = 5$)를 확장한다. G ($g = 5 + 3 = 8$)가 큐에 들어간다.

Step 5 — C ($g = 6$)를 확장한다. G까지의 새 경로 비용이 $6 + 1 = 7$로, 기존 경로($g = 8$)보다 저렴하므로 G의 $g$를 7로 갱신한다.

Step 6 — G ($g = 7$)를 꺼낸다. 목표 노드이므로 탐색 종료. 최적 경로는 S → A → C → G (비용 7)이다.

이 과정에서 주목할 점은 두 가지다. Step 3에서는 B를 경유하는 경로가 D에 더 저렴하게 도달하여 $g$가 9에서 5로 갱신되었고, Step 5에서는 C를 경유하는 경로가 G에 더 저렴하게 도달하여 $g$가 8에서 7로 갱신되었다. UCS는 이처럼 매 단계마다 최소 비용 노드를 확장하면서 더 저렴한 경로를 발견하면 즉시 갱신하기 때문에, 여러 경로 중 실제로 가장 저렴한 것을 올바르게 선택한다.

Python 구현

import heapq
from typing import Optional


def ucs(
    graph: dict[str, list[tuple[str, int]]],
    start: str,
    goal: str,
) -> Optional[tuple[int, list[str]]]:
    """Uniform-Cost Search.

    Args:
        graph: 인접 리스트. {노드: [(이웃, 비용), ...]}.
        start: 시작 노드.
        goal:  목표 노드.

    Returns:
        (최소 비용, 경로 리스트) 또는 경로 없으면 None.
    """
    # (g값, 삽입순서, 노드)
    counter = 0
    frontier = [(0, counter, start)]
    came_from: dict[str, Optional[str]] = {start: None}
    g_score: dict[str, int] = {start: 0}
    closed: set[str] = set()

    while frontier:
        g, _, current = heapq.heappop(frontier)

        if current in closed:
            continue
        if current == goal:
            # 경로 역추적
            path = []
            node: Optional[str] = goal
            while node is not None:
                path.append(node)
                node = came_from[node]
            return g, path[::-1]

        closed.add(current)

        for neighbor, cost in graph.get(current, []):
            if neighbor in closed:
                continue
            new_g = g + cost
            if new_g < g_score.get(neighbor, float("inf")):
                g_score[neighbor] = new_g
                came_from[neighbor] = current
                counter += 1
                heapq.heappush(frontier, (new_g, counter, neighbor))

    return None

A* 구현과 구조가 거의 동일하다. 유일한 차이는 heappush에 넣는 키가 g 하나뿐이라는 점이다 — 휴리스틱 $h(n)$를 더하지 않는다. 사실상 A*에서 $h(n) = 0$으로 설정한 것과 같다.

시간 복잡도와 공간 복잡도

UCS의 시간 및 공간 복잡도는 $O(b^{1 + \lfloor C^* / \epsilon \rfloor})$이다. 여기서 $C^*$는 최적 해의 비용, $\epsilon$은 가장 작은 간선 비용이다. 이 표현은 "최적 비용 이하의 모든 노드를 확장해야 할 수 있다"는 의미로, 간선 비용이 아주 작으면($\epsilon \to 0$) 탐색 공간이 급격히 커진다.

모든 간선 비용이 동일하면 $C^* / \epsilon = d$(최적 해의 깊이)가 되어 BFS와 같은 $O(b^d)$이 된다. 이것이 "비용이 동일하면 UCS = BFS"라는 직관과 일치한다.

Dijkstra 알고리즘과의 관계

Dijkstra 알고리즘과 UCS는 본질적으로 같은 알고리즘이다. 차이는 맥락에 있다. Dijkstra는 단일 출발점에서 모든 노드까지의 최단 거리를 구하는 문제에서 주로 언급되고, UCS는 출발점에서 특정 목표까지의 최단 경로를 찾는 탐색 문제에서 언급된다. UCS는 목표에 도달하면 즉시 종료하므로, 모든 노드를 처리하는 Dijkstra보다 일반적으로 더 일찍 끝난다.

또한 UCS는 Best-First Search 프레임워크의 인스턴스로 기술되므로, A*으로 자연스럽게 확장된다. $g(n)$에 휴리스틱 $h(n)$을 더하면 A*가 되는 것이다.

---

출처

• Russell, S. and Norvig, P. (2021) Artificial Intelligence: A Modern Approach. 4th Global edn. Harlow: Pearson. Chapter 3.4.2, Figure 3.9.
• Dijkstra, E. W. (1959) 'A note on two problems in connexion with graphs', Numerische Mathematik, 1(1), pp. 269–271.
• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 22.3 (Dijkstra's algorithm).

Footnotes

1. Russell and Norvig (2021), Figure 3.9. AIMA 4판에서는 UCS를 BEST-FIRST-SEARCH에 PATH-COST를 평가 함수로 전달하는 한 줄짜리 함수로 정의한다. 이는 UCS가 Best-First Search의 특수한 경우임을 명확히 보여준다. ↩