Best-First Search

Introduction

Best-First Search(최선 우선 탐색)는 평가 함수 $f(n)$ 을 기준으로 가장 유망한 노드부터 확장하는 그래프 탐색의 일반 프레임워크입니다. 평가 함수를 어떻게 정의하느냐에 따라 Uniform-Cost Search, Greedy Best-First Search, A* 등 다양한 구체 알고리즘이 탄생합니다. Best-First Search 자체는 특정 알고리즘이 아니라, "Priority Queue에 노드를 넣고 $f(n)$ 이 가장 작은 것부터 꺼낸다"는 공통 골격입니다. 이 글에서는 Best-First Search의 핵심 아이디어와 의사코드, 평가 함수에 따른 알고리즘 분류, 그리고 완전성·최적성 조건을 살펴봅니다.

핵심 아이디어

그래프 탐색 알고리즘은 어떤 노드를 먼저 확장할지 결정해야 한다. Breadth-First Search는 단순히 먼저 발견된 노드를(FIFO), Depth-First Search는 가장 나중에 발견된 노드를(LIFO) 먼저 확장한다. Best-First Search는 여기서 한 걸음 더 나아가, 각 노드에 "얼마나 유망한지"를 나타내는 평가 함수 $f(n)$ 을 부여하고, $f(n)$ 이 가장 작은 노드를 먼저 확장한다.

이를 위해 탐색 경계(frontier)를 Priority Queue로 관리한다. 노드가 발견될 때마다 $f(n)$ 을 키로 하여 큐에 삽입하고, 확장할 때는 $f(n)$ 이 가장 작은 노드를 꺼낸다.

의사코드

아래는 AIMA (Russell & Norvig, 2021)의 Figure 3.7에 기반한 의사코드다¹.

function BEST-FIRST-SEARCH(problem, f) returns solution or failure
    node ← NODE(STATE=problem.INITIAL, PATH-COST=0)
    frontier ← priority queue ordered by f, with node as the only element
    reached ← a lookup table, with one entry: {problem.INITIAL: node}

    while frontier is not empty do
        node ← POP(frontier)                    ▷ f가 가장 작은 노드
        if problem.IS-GOAL(node.STATE) then
            return SOLUTION(node)

        for each child in EXPAND(problem, node) do
            s ← child.STATE
            if s is not in reached  or  child.PATH-COST < reached[s].PATH-COST then
                reached[s] ← child
                add child to frontier

    return failure

frontier는 아직 확장하지 않은 노드들의 집합이며, reached는 이미 발견된 노드의 최선 경로 비용을 기록하는 테이블이다. reached를 통해 같은 노드를 더 비싼 경로로 중복 탐색하는 것을 방지한다.

이 의사코드에서 f를 인자로 받는다는 점이 핵심이다. 어떤 $f$ 를 넘겨주느냐에 따라 완전히 다른 알고리즘이 된다.

평가 함수에 따른 알고리즘 분류

Best-First Search 프레임워크에서 $f(n)$ 을 달리 정의하면 다음 알고리즘들이 도출된다.

Uniform-Cost Search

$f(n) = g(n)$

시작 노드부터 $n$ 까지의 실제 누적 비용 $g(n)$ 만을 기준으로 한다. 휴리스틱을 사용하지 않으며, 간선 비용이 음수가 아닌 한 최적 해를 보장한다. Dijkstra 알고리즘의 그래프 탐색 버전에 해당한다. 자세한 내용은 Uniform-Cost Search에서 다룬다.

Greedy Best-First Search

$f(n) = h(n)$

$n$ 에서 목표까지의 추정 비용 $h(n)$ 만을 기준으로 한다. 과거에 얼마나 왔는지( $g$ )는 무시하고 "목표에 가까워 보이는" 노드를 우선 확장한다. 빠르게 해를 찾을 수 있지만, 최적 해를 보장하지 못한다². 장애물 뒤에 숨은 목표를 찾을 때 긴 우회로를 택하는 경우가 대표적이다.

A*

$f(n) = g(n) + h(n)$

실제 비용 $g(n)$ 과 추정 비용 $h(n)$ 을 합산한다. Uniform-Cost Search의 최적성과 Greedy의 방향성을 결합한 알고리즘이다. $h(n)$ 이 허용 가능(admissible)하면 최적 해를 보장한다. 자세한 내용은 A*에서 다룬다.

BFS와의 관계

Breadth-First Search도 넓은 의미에서 $f(n) = \text{depth}(n)$ 인 Best-First Search로 볼 수 있다. 모든 간선 비용이 동일할 때는 깊이가 곧 경로 비용이므로 UCS와 동일한 결과를 낸다. 다만 BFS는 보통 FIFO 큐로 구현하므로, Priority Queue를 사용하는 일반적인 Best-First Search보다 오버헤드가 적다.

완전성과 최적성

Best-First Search의 완전성³과 최적성은 평가 함수 $f$ 에 의존한다. 프레임워크 자체는 완전하지도, 최적이지도 않다 — $f$ 가 어떤 성질을 만족하느냐에 따라 이 보장이 결정된다.

알고리즘	완전성	최적성	시간 복잡도	공간 복잡도
UCS	$O$ (비용 > 0)	$O$ (비용 ≥ 0)	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$
Greedy	$X$ ⁴	$X$	$O(b^m)$	$O(b^m)$
A*	$O$	$O$ (admissible $h$ )	$O(b^d)$	$O(b^d)$

여기서 $b$ 는 분기 계수, $d$ 는 최적 해의 깊이, $m$ 은 상태 공간의 최대 깊이, $C^*$ 는 최적 해 비용, $\epsilon$ 은 최소 간선 비용이다.

출처

Russell, S. and Norvig, P. (2021) Artificial Intelligence: A Modern Approach. 4th Global edn. Harlow: Pearson. Chapter 3.5, Figure 3.7.
Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 22.

Russell and Norvig (2021), Figure 3.7. AIMA 4판에서는 이 프레임워크를 모든 정보 탐색(informed search) 알고리즘과 일부 무정보 탐색(uninformed search) 알고리즘의 공통 골격으로 제시한다. ↩
Greedy Best-First Search가 비최적인 이유 — $g(n)$ 을 무시하므로 지금까지 경유한 비용을 고려하지 않는다. 목표에 가까워 "보이지만" 실제로는 먼 돌아가는 경로를 선택할 수 있다. ↩
완전성(completeness) — 해가 존재할 때 알고리즘이 반드시 해를 찾는 성질. 최적성(optimality)은 찾은 해가 최적 해임을 보장하는 성질이다. ↩
Greedy Best-First Search는 그래프에 사이클이 있으면 무한 루프에 빠질 수 있다. reached 테이블로 재방문을 방지하면 유한 그래프에서 완전해지지만, 무한 상태 공간에서는 보장되지 않는다. ↩