> [!abstract] 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에 기반한 의사코드다[^aima-best-first]. ``` 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$를 넘겨주느냐에 따라 완전히 다른 알고리즘이 된다. ## 평가 함수에 따른 알고리즘 분류 ![[bestFirstSearchFramework.svg]] 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$)는 무시하고 "목표에 가까워 보이는" 노드를 우선 확장한다. 빠르게 해를 찾을 수 있지만, 최적 해를 보장하지 못한다[^greedy-nonoptimal]. 장애물 뒤에 숨은 목표를 찾을 때 긴 우회로를 택하는 경우가 대표적이다. ### 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의 완전성[^completeness]과 최적성은 평가 함수 $f$에 의존한다. 프레임워크 자체는 완전하지도, 최적이지도 않다 — $f$가 어떤 성질을 만족하느냐에 따라 이 보장이 결정된다. | 알고리즘 | 완전성 | 최적성 | 시간 복잡도 | 공간 복잡도 | |----------|--------|--------|-------------|-------------| | UCS | $O$ (비용 > 0) | $O$ (비용 ≥ 0) | $O(b^{1+\lfloor C^*/\epsilon \rfloor})$ | $O(b^{1+\lfloor C^*/\epsilon \rfloor})$ | | Greedy | $X$[^greedy-incomplete] | $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. [^aima-best-first]: Russell and Norvig (2021), Figure 3.7. AIMA 4판에서는 이 프레임워크를 모든 정보 탐색(*informed search*) 알고리즘과 일부 무정보 탐색(*uninformed search*) 알고리즘의 공통 골격으로 제시한다. [^greedy-nonoptimal]: Greedy Best-First Search가 비최적인 이유 — $g(n)$을 무시하므로 지금까지 경유한 비용을 고려하지 않는다. 목표에 가까워 "보이지만" 실제로는 먼 돌아가는 경로를 선택할 수 있다. [^greedy-incomplete]: Greedy Best-First Search는 그래프에 사이클이 있으면 무한 루프에 빠질 수 있다. `reached` 테이블로 재방문을 방지하면 유한 그래프에서 완전해지지만, 무한 상태 공간에서는 보장되지 않는다. [^completeness]: 완전성(*completeness*) — 해가 존재할 때 알고리즘이 반드시 해를 찾는 성질. 최적성(*optimality*)은 찾은 해가 최적 해임을 보장하는 성질이다.