Best-First Search

Introduction

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

핵심 아이디어

그래프 탐색 알고리즘은 어떤 노드를 먼저 확장할지 결정해야 한다. 너비 우선 탐색는 단순히 먼저 발견된 노드를, 깊이 우선 탐색는 가장 나중에 발견된 노드를 먼저 확장한다. Best-First Search는 여기서 한 걸음 더 나아가, 각 노드에 점수를 매기는 평가 함수Evaluation Function $f(n)$ 을 부여하고, 현재 시점에서 가장 점수가 높은 쪽부터 먼저 탐색을 진행한다.

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

의사코드

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

\begin{array}{l} \textbf{function } \text{Best-First-Search}(problem, f) \textbf{ returns } \textit{solution or failure} \\ \quad node \leftarrow \text{Node}(\text{State}=problem.\text{Initial},\ \text{Path-Cost}=0) \\ \quad frontier \leftarrow \text{priority queue ordered by } f, \text{ initially containing } node \\ \quad reached \leftarrow \text{lookup table} \{ problem.\text{Initial} : node \} \\ \quad \textbf{while } frontier \text{ is not empty } \textbf{do} \\ \quad\quad node \leftarrow \text{Pop}(frontier) \qquad \triangleright\ f\text{가 가장 작은 노드} \\ \quad\quad \textbf{if } problem.\text{Is-Goal}(node.\text{State}) \textbf{ then return } \text{Solution}(node) \\ \quad\quad \textbf{for each } child \in \text{Expand}(problem, node) \textbf{ do} \\ \quad\quad\quad s \leftarrow child.\text{State} \\ \quad\quad\quad \textbf{if } s \notin reached \ \textbf{or}\ child.\text{Path-Cost} < reached[s].\text{Path-Cost} \textbf{ then} \\ \quad\quad\quad\quad reached[s] \leftarrow child \\ \quad\quad\quad\quad \text{add } child \text{ to } frontier \\ \quad \textbf{return } \textit{failure} \end{array}

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

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

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

Best-First Search는 프레임워크의 관점으로도 볼 수 있는데, 평가 함수 $f(n)$ 을 달리 정의하면 다음 알고리즘들이 도출된다.

Uniform-Cost Search

$f(n) = g(n)$

시작 노드부터 $n$ 까지의 실제 누적 비용 $g(n)$ 만을 기준으로 한다. 휴리스틱을 사용하지 않으며, 간선 비용이 음수가 아닌 한 최적 해를 보장한다. 다익스트라 알고리즘의 그래프 탐색 버전에 해당한다. 자세한 내용은 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와의 관계

너비 우선 탐색(BFS)도 넓은 의미에서 $f(n) = \text{depth}(n)$ 인 Best-First Search로 볼 수 있다. 모든 간선 비용이 동일할 때는 깊이가 곧 경로 비용이므로 UCS와 동일한 결과를 낸다. 다만 BFS는 보통 FIFO 큐로 구현하므로, 우선순위 큐를 사용하는 일반적인 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 테이블로 재방문을 방지하면 유한 그래프에서 완전해지지만, 무한 상태 공간에서는 보장되지 않는다. ↩