🔗 관련 문서: Wikipedia - 탐색 알고리즘

탐색Search

[목차로 돌아가기]

1. 탐색의 개념

탐색(Search)은 문제의 답이 될 수 있는 것들의 집합을 상태 공간(state space)으로 간주하고, 초기 상태에서 목표 상태에 도달하기 위한 경로를 체계적으로 검색하는 과정이다. 인공지능에서 탐색은 추론, 계획 수립, 게임 플레이 등 다양한 문제 해결의 근간이 되는 기법이다.

탐색 문제는 일반적으로 다음 다섯 가지 요소로 정의된다.

• 초기 상태(Initial State):
  탐색을 시작하는 출발 상태
• 행동(Actions):
  각 상태에서 취할 수 있는 가능한 연산(동작)의 집합
• 전이 모델(Transition Model):
  특정 상태에서 행동을 취했을 때 도달하는 다음 상태를 정의하는 함수
• 목표 테스트(Goal Test):
  현재 상태가 목표 상태인지 판별하는 조건
• 경로 비용(Path Cost):
  초기 상태에서 현재 상태까지 도달하는 데 드는 누적 비용
탐색 트리 vs 상태 공간 그래프

상태 공간을 그림으로 나타낸 것이 상태 공간 그래프이며, 탐색 알고리즘이 실제로 상태들을 방문해 나가는 순서를 나뭇가지 형태로 펼친 것이 탐색 트리이다. 하나의 상태가 여러 경로로 재방문될 수 있어 탐색 트리는 상태 공간 그래프보다 노드 수가 많아질 수 있다.

[목차로 돌아가기]

2. 탐색 기법의 평가 기준

여러 탐색 알고리즘의 성능은 다음 네 가지 기준으로 비교한다.

• 완비성(Completeness):
  해가 존재할 경우 반드시 그 해를 찾아내는가에 대한 성질이다.
• 최적성(Optimality):
  찾아낸 해가 전역 최적값(global optimum), 즉 가능한 해들 중 가장 비용이 낮은 해인가에 대한 성질이다.
• 시간 복잡도(Time Complexity):
  해를 찾기까지 생성해야 하는 노드의 수(탐색에 걸리는 시간)이다.
• 공간 복잡도(Space Complexity):
  탐색 과정에서 메모리에 저장해야 하는 노드의 최대 개수이다.

탐색은 크게 맹목적 탐색(uninformed / blind search)과 목표까지의 거리에 대한 추가 정보를 활용하는 정보 기반 탐색(informed / heuristic search), 그리고 경로 전체가 아닌 현재 상태 주변만 살피는 지역 탐색(local search)으로 나눌 수 있다.

[목차로 돌아가기]

3. 맹목적 탐색(Uninformed Search)

맹목적 탐색은 목표까지 남은 거리 등 문제에 특화된 추가 정보(휴리스틱) 없이, 상태 공간의 구조만을 이용해 체계적으로 탐색하는 방법이다.

3.1 너비 우선 탐색(BFS, Breadth-First Search) [나무위키]

시작 노드로부터 얕은 깊이의 노드부터 순차적으로 모든 형제 노드를 탐색한 뒤 다음 깊이로 내려가는 방법이다. 목표 상태를 찾을 때까지 생성된 모든 노드를 큐(queue, FIFO)에 넣어 관리하므로 메모리 사용량이 크다는 단점이 있다. 그러나 각 단계에서 이동 비용이 모두 동일(균일)하다면, 얕은 깊이의 해부터 확인하므로 완비적이며 최적해(전역 최적값)를 보장한다.

3.2 깊이 우선 탐색(DFS, Depth-First Search) [나무위키]

한 방향으로 갈 수 있는 만큼 깊이 내려간 뒤, 더 이상 진행할 수 없으면 되돌아와(backtracking) 다른 경로를 탐색하는 방법이다. 스택(stack, LIFO) 구조로 관리되어 BFS에 비해 메모리 부담이 적지만, 먼저 도달한 해가 최단 경로라는 보장이 없어 최적성을 보장하지 않는다. 또한 무한히 깊은 경로나 순환이 있는 공간에서는 완비성도 보장되지 않는다.

탐색 깊이에 제한을 두는 깊이 제한 탐색(depth-limited search)을 적용하면 무한 루프는 방지할 수 있지만, 제한된 깊이 안에 해가 없으면 찾지 못하고, 설령 찾아도 최단 경로라는 보장은 여전히 없다.

3.3 균일 비용 탐색(UCS, Uniform-Cost Search)

각 경로의 누적 비용 $g(n)$이 가장 낮은 노드부터 우선적으로 확장하는 방법이다. 이동 비용이 모두 동일하지 않은 경우에도 완비적이며 최적해를 보장하지만, 비용이 낮은 노드를 계속 우선 처리하기 위해 우선순위 큐를 사용해야 하므로 계산·메모리 부담이 크다.

예시로 이해하는 균일 비용 탐색

시작 노드 S에서 목표 노드 G까지 아래와 같이 간선 비용이 서로 다른 그래프가 주어졌다고 하자.

간선(경로)과 이동 비용
S–A : 2  |  S–B : 1  |  S–D : 4  |  A–G : 5  |  B–C : 1  |  C–G : 3  |  D–G : 2

균일 비용 탐색은 매 단계마다 프론티어(frontier, 우선순위 큐) 중 누적 비용 $g(n)$이 가장 작은 노드를 꺼내 확장한다. 이 그래프에서 탐색이 진행되는 과정을 표로 정리하면 다음과 같다.

단계	확장 노드(pop)	$g(n)$	설명
1	S (시작)	0	이웃 A($g=2$), B($g=1$), D($g=4$)를 프론티어에 추가
2	B (최소)	1	C의 경로 발견 (S–B–C, $g=1+1=2$) → 프론티어에 추가
3	A (최소)	2	G 후보 추가 (S–A–G, $g=2+5=7$)
4	C (최소)	2	G까지 더 짧은 경로 발견 (S–B–C–G, $g=2+3=5$) → 기존 $g=7$보다 짧아 갱신
5	D (최소)	4	G 경로 재계산 (S–D–G, $g=4+2=6$) → 기존 $g=5$보다 커서 갱신 안 함
6	G (최소, 목표!)	5	목표 노드가 프론티어에서 최솟값으로 뽑혔으므로 탐색 종료

S→A→G(비용 $2+5=7$)와 S→D→G(비용 $4+2=6$)는 거쳐 가는 간선이 2개뿐이라 S→B→C→G(간선 3개)보다 언뜻 더 빠른 경로처럼 보일 수 있다. 그러나 균일 비용 탐색은 간선의 개수가 아니라 각 경로의 누적 비용 $g(n)$만을 비교하므로, 실제로는 비용 5인 S→B→C→G가 최적해로 선택된다.

핵심 포인트: "간선 수가 적다고 비용이 낮은 것은 아니다"

위 예시처럼 목표까지 거치는 간선(홉) 수가 적더라도, 각 간선의 비용이 크면 누적 비용은 오히려 커질 수 있다. 균일 비용 탐색이 비교하는 기준은 언제나 간선 수가 아닌 누적 경로 비용 $g(n)$이라는 점에 유의해야 한다.

3.4 반복적 깊이 심화 탐색(IDS, Iterative Deepening Search)

탐색 깊이 제한을 0부터 시작하여 점차 1씩 증가시키면서 깊이 우선 탐색을 반복 수행하는 방법이다. DFS의 낮은 메모리 사용량과 BFS의 완비성·최적성(균일 비용 조건에서)을 동시에 갖춘 절충안으로 평가된다.

[목차로 돌아가기]

4. 정보 기반 탐색(Informed Search)

정보 기반 탐색은 목표까지 남은 비용을 추정하는 휴리스틱 함수 $h(n)$을 활용하여 탐색 효율을 높이는 방법이다.

4.1 탐욕적 최우선 탐색(Greedy Best-First Search)

휴리스틱 함수 $h(n)$값, 즉 목표까지 남았다고 추정되는 비용이 가장 작은 노드를 우선적으로 확장하는 방법이다. 지금까지의 실제 이동 비용은 고려하지 않으므로 계산이 빠르지만, 최적해를 보장하지 못한다.

4.2 A* 알고리즘 [나무위키]

A* 알고리즘은 시작 노드로부터 실제로 소요된 비용 $g(n)$과 목표까지 남은 비용의 추정치인 휴리스틱 함수 $h(n)$을 함께 고려한 평가함수를 사용한다.

A* 평가함수:
$$ f(n) = g(n) + h(n) $$
• $g(n)$ : 시작 노드에서 노드 $n$까지 지금까지 발견된 최선(최소) 비용이며, 더 짧은 경로가 새로 발견되면 갱신될 수 있다.
• $h(n)$ : 노드 $n$에서 목표까지 남은 비용의 추정값(휴리스틱 함수)이다.
• 휴리스틱 함수 $h(n)$이 실제 남은 비용을 과대평가하지 않으면(허용성, admissibility) A* 알고리즘은 항상 최적해를 찾는다.
• 반대로 허용성을 갖지 않는(실제 비용을 과대평가할 수 있는) 휴리스틱을 사용한 A*는 더 빠르게 해를 찾을 수는 있지만 최적해를 보장하지 못한다.

쉬운 예시: 지도 위의 길 찾기

당신이 서울역(출발)에서 남산타워(목적지)까지 가려고 한다.

1. 갈림길 발견: 길을 가다 보니 왼쪽 길과 오른쪽 길이 나왔다.
2. 왼쪽 길 계산:
   • $g(n)$ (지금까지 걸어온 거리): 1km
   • $h(n)$ (남산타워까지 직선거리 예상): 3km
   • 결과 $f(n) = 4$km
3. 오른쪽 길 계산:
   • $g(n)$ (지금까지 걸어온 거리): 2km
   • $h(n)$ (남산타워까지 직선거리 예상): 1km
   • 결과 $f(n) = 3$km
4. 결정: 4km보다 3km가 작으므로, 알고리즘은 오른쪽 길을 선택하여 이동한다.

이렇게 매 순간 "현재까지의 노력($g$)"과 "남은 거리의 직관($h$)"을 더해 가장 효율적인 선택을 반복한다.

예시로 이해하는 A* 알고리즘

시작 노드 S에서 목표 노드 G까지 아래와 같은 그래프가 주어졌다고 하자.

간선(경로)과 실제 이동 비용
S–A : 1  |  S–B : 4  |  A–B : 2  |  A–G : 5  |  B–G : 1

휴리스틱 값 $h(n)$ (목표까지 남은 비용의 추정치, 허용적)
$h(S)=3$  |  $h(A)=2$  |  $h(B)=1$  |  $h(G)=0$

A*는 매 단계마다 Open List(아직 방문하지 않은 후보 노드들) 중 $f(n)=g(n)+h(n)$이 가장 작은 노드를 골라 확장한다. 이 그래프에서 A*가 동작하는 과정을 표로 정리하면 다음과 같다.

단계	확장 노드	$g(n)$	$h(n)$	$f(n)=g+h$	설명
1	S (시작)	0	3	3	이웃 A, B를 Open List에 추가
2	A ($f=3$, 최소)	1	2	3	B의 경로 발견 (S–A–B, $g=3$) → 기존 $g=4$보다 짧아 갱신 / G 후보 추가 ($g=6$)
3	B ($f=4$, 최소)	3	1	4	G까지의 경로 발견 (S–A–B–G, $g=4$) → 기존 $g=6$보다 짧아 갱신
4	G ($f=4$, 최소, 목표!)	4	0	4	목표 노드가 Open List에서 최솟값으로 뽑혔으므로 탐색 종료

처음에는 S → A → G 경로(비용 $1+5=6$)로도 갈 수 있었지만, A를 확장하는 과정에서 B를 거쳐 더 짧은 경로($g=3$)가 발견되어 갱신되었고, 이어서 B를 확장하면서 G까지의 경로도 더 짧게($g=4$) 갱신되었다. 결과적으로 A*는 S → A → B → G, 총 비용 4의 경로를 찾아내는데, 이는 이 그래프에서 가능한 가장 낮은 비용의 경로(최적해)와 일치한다.

이처럼 휴리스틱이 허용적(실제 비용을 과대평가하지 않음)이면, 도중에 $g(n)$이 더 나은 값으로 계속 갱신되더라도 A*가 목표 노드를 Open List에서 최솟값으로 꺼내는 순간 그 경로는 항상 전역 최적해임이 보장된다.

A* 알고리즘이 특별한 이유

• 다익스트라(Dijkstra) 알고리즘의 보완: 다익스트라는 모든 방향을 다 탐색해서 시간이 오래 걸리지만, A*는 목적지 방향으로 먼저 가보려는 성질($h(n)$)이 있어 훨씬 빠르다.
• 최적성: $h(n)$ 값을 너무 크게 잡지 않는다면(허용성을 만족한다면), 반드시 최단 경로를 찾아낸다.
요약하자면
A* 알고리즘은 "지금까지 얼마나 왔지?"($g(n)$)와 "목적지까지 대략 얼마나 남았지?"($h(n)$)라는 두 가지 정보를 조합해, 목적지까지 가장 빠르게 갈 수 있는 길을 찾아내는 스마트한 내비게이션과 같다.

[목차로 돌아가기]

5. 지역 탐색(Local Search)

지역 탐색은 지금까지의 경로를 기억하지 않고, 현재 상태 주변(이웃)만을 살피며 상태를 개선해 나가는 방법이다. 메모리 사용이 적어 큰 문제에 적합하지만, 탐색 트리 전체를 보지 못하므로 전역 최적값을 보장하지 못하는 경우가 많다.

5.1 언덕 오르기(Hill Climbing) [위키]

현재 상태의 이웃 상태들 중 가장 개선되는 방향으로만 이동하는 탐욕적(greedy) 지역 탐색 기법이다. 구현이 간단하고 계산이 빠르지만, 주변 이웃보다는 낫지만 전체적으로는 최선이 아닌 지역 최적값(local optimum)에 빠지면 그 지점에서 더 이상 나아가지 못하는 한계가 있다. 따라서 전역 최적값을 보장하지 않는다.

5.2 담금질 기법(Simulated Annealing)

언덕 오르기의 지역 최적값 문제를 완화하기 위해, 일정 확률로 더 나쁜 상태로도 이동을 허용하는 기법이다. 금속을 서서히 냉각시키며 안정적인 결정 구조를 얻는 담금질(annealing) 과정에서 착안했으며, 탐색이 진행될수록(온도가 낮아질수록) 나쁜 상태로의 이동 확률을 점차 줄여나간다.

[목차로 돌아가기]

6. 탐색 기법 비교

주요 탐색 기법의 완비성·최적성을 정리하면 다음과 같다. (단, 완비성·최적성은 상태 공간이 유한하고 이동 비용이 0보다 큰 일반적인 조건을 기준으로 한다)

탐색 기법	완비성	최적성	비고
BFS	O	O (비용 균일 시)	메모리 부담 큼
DFS	△ (무한공간 X)	X	메모리 부담 적음
UCS	O	O	비용 비균일에도 최적
IDS	O	O (비용 균일 시)	DFS의 메모리 + BFS의 완비성
탐욕적 최우선 탐색	X	X	$h(n)$만 고려
A* (허용적 휴리스틱)	O	O	$f(n)=g(n)+h(n)$
언덕 오르기	X	X	지역 최적값에 빠질 수 있음

[목차로 돌아가기]

7. 기출문제로 확인하기

Q. 트리 탐색의 결과로 전역 최적값이 보장되는 기법은?
• ① 너비 우선 탐색(breadth-first search) ✅ 정답
• ② 허용성(admissibility)을 갖지 않는 A* 알고리즘
• ③ 언덕 오르기 방법(hill climbing method)
• ④ 탐색 깊이 제한이 있는 깊이 우선 탐색(depth-first search)

해설
너비 우선 탐색은 얕은 깊이부터 모든 경로를 체계적으로 탐색하므로(이동 비용이 균일할 때) 가장 먼저 찾아낸 해가 곧 최단 경로, 즉 전역 최적해가 된다. 언덕 오르기는 이웃 상태만 보고 이동하므로 지역 최적값에 빠질 수 있고, 허용성이 없는 휴리스틱을 사용한 A*는 실제 남은 비용을 과소·과대평가할 수 있어 최적해를 보장하지 못하며, 깊이 제한이 있는 DFS는 제한된 범위 안에서 먼저 찾은 해가 최단 경로라는 보장이 없다.
Q. 다음 그래프에서 모든 간선 비용이 0 이상일 때, 균일 비용 탐색(uniform-cost search)이 찾는 최소 비용 경로와 비용은?
(S–A:2, A–G:5, S–B:1, B–C:1, C–G:3, S–D:4, D–G:2)
• ① S→B→C→G, 비용 5 ✅ 정답
• ② S→A→G, 비용 7
• ③ S→D→G, 비용 6
• ④ 노드 수가 가장 적은 S→D→G, 비용 2

해설
균일 비용 탐색은 현재까지의 누적 경로비용 $g(n)$이 가장 작은 노드를 우선 확장한다. 각 완성 경로의 비용은 $S \to A \to G = 2+5=7$, $S \to B \to C \to G = 1+1+3=5$, $S \to D \to G = 4+2=6$이다. 따라서 최소 비용 경로는 S→B→C→G이며 비용은 5이다. 간선 수가 아니라 누적 비용을 비교해야 하므로, 간선이 2개뿐인 S→D→G나 S→A→G가 얼핏 더 유리해 보여도 실제로는 더 비싸다.