[CS300 #262] 탐색 — 상태 공간과 휴리스틱

컴퓨터공학 300 주제 시리즈의 262번째 글이다. 전체 지도는 여기.

한 줄 요약

문제를 “상태”와 “상태를 바꾸는 행동”의 그래프로 바꾸면 풀이는 목표 상태까지의 경로 찾기가 되고, 좋은 휴리스틱은 그 탐색에서 열어 봐야 할 노드 수를 크게 줄인다.

왜 필요한가

학습이 AI 의 전부처럼 보이지만, 길찾기·퍼즐·일정 배치·게임처럼 규칙이 명확한 문제는 지금도 탐색이 주력이다. 내비게이션이 경로를 내놓는 것, 컴파일러가 명령어 순서를 고르는 것, LLM 이 여러 후보 답을 펼쳐 보고 고르는 것까지 뼈대는 같다.

탐색의 문제는 하나다. 상태가 너무 많다. 8-퍼즐만 해도 도달 가능한 배치가 9!/2 = 181,440 개다. 모든 상태를 다 보지 않고 답을 찾으려면 “어느 쪽이 목표에 가까워 보이는가”를 추정하는 지식, 즉 휴리스틱이 필요하다.

핵심 개념

문제를 상태 공간으로 정의하기

탐색 문제는 다섯 가지로 정의한다.

요소	뜻	미로 예
초기 상태	출발점	S 의 좌표
행동	상태에서 할 수 있는 일	상하좌우 이동
전이 모델	행동 후 상태	좌표 변화(벽이면 불가)
목표 판정	끝났는지	G 에 도착했는가
경로 비용	행동의 비용 합	한 칸 = 1

이 정의만 하면 문제의 의미는 사라지고 그래프 탐색만 남는다. 같은 알고리즘이 미로에도, 퍼즐에도, 일정표에도 쓰인다.

무정보 탐색

목표가 어디 있는지 모르고 체계적으로 펼친다.

• 너비 우선(BFS): 가까운 것부터. 비용이 모두 같으면 최단 경로를 보장한다. 메모리를 많이 쓴다.
• 깊이 우선(DFS): 한 갈래를 끝까지. 메모리는 적지만 최단을 보장하지 않고 무한 공간에서 빠져나오지 못할 수 있다.
• 균일 비용(UCS, 다익스트라): 지금까지 비용 g(n) 이 가장 작은 것부터. 비용이 서로 다를 때의 최단 경로.

정보 탐색과 A*

A* 는 노드를 다음 값이 작은 순서로 꺼낸다.

f(n) = g(n) + h(n)
       │       └ 여기서 목표까지 남은 비용의 추정치 (휴리스틱)
       └ 출발점에서 여기까지 실제 비용

h 가 항상 0 이면 균일 비용 탐색과 같다. h 가 좋을수록 목표 쪽으로 곧장 파고든다.

A* 가 최적 해를 보장하려면 휴리스틱이 조건을 지켜야 한다.

• 허용성(admissible): h(n) 이 실제 남은 비용을 절대 넘지 않는다. 낙관적이어야 한다.
• 일관성(consistent): 이웃 n’ 에 대해 h(n) ≤ c(n, n’) + h(n’). 삼각 부등식. 일관성이 있으면 허용성도 따라온다.

격자에서 상하좌우만 움직이면 맨해튼 거리

Δx

+

Δy

는 벽을 무시한 거리이므로 실제 거리보다 클 수 없다. 허용적이다. 대각선 이동이 허용되는 격자에서는 맨해튼 거리가 과대평가가 되어 허용성이 깨진다. 휴리스틱은 문제의 행동 정의와 짝을 이뤄야 한다.

휴리스틱을 만드는 법 — 완화 문제

좋은 휴리스틱은 대개 제약을 푼 쉬운 문제의 정확한 답이다. 미로에서 벽을 없애면 맨해튼 거리가 정답이 된다. 8-퍼즐에서 “타일이 다른 타일을 뚫고 지나갈 수 있다”고 완화하면 각 타일의 맨해튼 거리 합이 된다. 제약을 덜 풀수록 h 가 커지고(실제에 가까워지고) 탐색이 줄지만, h 계산 자체가 비싸진다.

복잡도 감각

분기 계수 b, 해의 깊이 d 이면 BFS 는 O(b^d) 노드를 본다. 휴리스틱은 지수를 없애지 못하지만 실질적인 분기 계수를 줄인다. 그래서 같은 문제에서 열어 보는 노드 수로 휴리스틱의 질을 비교한다.

직접 해 보기

벽이 하나 있는 격자에서 BFS, h=0 인 A*, 맨해튼 A* 를 비교한다. 우선순위 큐는 표준 라이브러리 heapq 를 쓴다.

import heapq
from collections import deque
GRID = ["S...........",
        "............",
        "......#.....",
        "......#.....",
        "......#.....",
        "......#....G"]
H, W = len(GRID), len(GRID[0])
def find(ch):
    for r in range(H):
        for c in range(W):
            if GRID[r][c] == ch: return (r, c)
S, G = find("S"), find("G")
def nbrs(p):
    r, c = p
    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
        nr, nc = r+dr, c+dc
        if 0 <= nr < H and 0 <= nc < W and GRID[nr][nc] != "#":
            yield (nr, nc)
def bfs():
    q, seen, expanded = deque([(S, 0)]), {S}, 0
    while q:
        p, d = q.popleft(); expanded += 1
        if p == G: return d, expanded
        for n in nbrs(p):
            if n not in seen: seen.add(n); q.append((n, d+1))
def astar(h):
    pq, g, expanded = [(h(S), h(S), 0, S)], {S: 0}, 0
    while pq:
        f, _, d, p = heapq.heappop(pq)   # f 가 같으면 h 가 작은 쪽 먼저
        if d > g[p]: continue
        expanded += 1
        if p == G: return d, expanded
        for n in nbrs(p):
            if d+1 < g.get(n, 1e9):
                g[n] = d+1; heapq.heappush(pq, (d+1+h(n), h(n), d+1, n))
manhattan = lambda p: abs(p[0]-G[0]) + abs(p[1]-G[1])
print("BFS      (경로길이, 확장노드):", bfs())
print("A* h=0   (경로길이, 확장노드):", astar(lambda p: 0))
print("A* 맨해튼 (경로길이, 확장노드):", astar(manhattan))

실행 결과:

BFS      (경로길이, 확장노드): (16, 68)
A* h=0   (경로길이, 확장노드): (16, 68)
A* 맨해튼 (경로길이, 확장노드): (16, 17)

세 방법 모두 길이 16 인 최단 경로를 찾는다(최적성). 차이는 확장한 노드 수다. h=0 인 A* 는 BFS 와 똑같이 사방으로 퍼지고, 맨해튼 휴리스틱을 쓰면 거의 경로 위의 칸만 열어 본다.

코드의 한 줄을 눈여겨볼 만하다. 큐에 (f, h, g, 좌표) 를 넣었다. f 가 같은 후보가 많을 때 h 가 작은(목표에 가까운) 쪽을 먼저 꺼내도록 한 동점 처리다. 이 한 줄이 없으면 이 격자에서는 맨해튼 A* 도 68개를 다 연다. 열린 격자에서는 f 값이 같은 칸이 많기 때문이다. 이론 성능과 실제 성능 사이에는 이런 구현 세부가 끼어 있다.

현업에서는

• 지도·물류: 도로망 길찾기는 A* 와 그 변형, 그리고 미리 계산한 지표를 휴리스틱으로 쓰는 기법이 기본이다.
• 게임 AI: NPC 이동은 격자나 내비게이션 메시 위의 A* 가 표준이다.
• 스케줄링: 쿠버네티스 스케줄러는 후보 노드를 걸러 내고(필터) 점수를 매겨(스코어) 고른다. 전수 탐색이 아니라 규칙 기반 점수로 근사하는 휴리스틱 탐색에 가깝다.
• LLM 디코딩: 빔 서치는 매 단계 상위 k 개 후보만 남기는 탐색이다. 완전 탐색을 포기하고 너비를 제한한다.

확인 문제

1. 상태 공간 탐색 문제를 정의하는 다섯 요소를 들어라.
2. A* 에서 h(n)=0 이면 어떤 알고리즘과 같아지는가?
3. 대각선 이동(비용 1)이 허용되는 격자에서 맨해튼 거리는 허용적인가?
4. 8-퍼즐에서 “제자리에 있지 않은 타일 수”와 “맨해튼 거리 합” 중 어느 쪽이 더 좋은 휴리스틱인가?
5. 예제에서 맨해튼 A* 의 확장 노드가 줄어든 이유와, 동점 처리를 빼면 무슨 일이 생기는지 설명하라.

풀이

1. 초기 상태, 행동, 전이 모델, 목표 판정, 경로 비용.
2. 균일 비용 탐색(다익스트라). 비용이 모두 같으면 BFS 와 같은 순서로 넓게 퍼진다.

3. 아니다. 대각선 한 번(비용 1)으로 가는 거리를 맨해튼은 2 로 세므로 과대평가한다. 이때는 체비쇼프 거리 max(

   Δx

   ,

   Δy

   ) 가 허용적이다.

4. 맨해튼 거리 합. 둘 다 허용적이고, 모든 상태에서 맨해튼 합이 더 크거나 같다(지배한다). 따라서 확장 노드가 같거나 적다.
5. 목표 쪽 칸의 f 가 작아 우선 꺼내지기 때문이다. 동점 처리가 없으면 f 가 같은 칸들을 g 가 작은 순서로 꺼내 넓게 퍼지고, 이 격자에서는 BFS 와 같은 68개를 연다.

더 읽을거리 (References)

• P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4(2), 1968. (A* 원 논문, 서지 정보)
• S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., 3장 “Solving Problems by Searching”. 책 사이트
• Python 공식 문서, heapq — Heap queue algorithm