상태 공간 탐색으로 최적 해를 설계하는 방법

문제를 상태와 전이로 바꾸는 방식

상태 공간 탐색은 문제 해결 과정을 상태들의 공간으로 표현한 뒤, 그 안을 체계적으로 탐색해 해 또는 최적 해를 찾는 방법론이다. 경로 탐색, 스케줄링, 퍼즐, 게임 AI처럼 서로 다른 문제도 같은 프레임워크로 다룰 수 있다.

탐색 문제는 상태 집합 S, 연산자 또는 행동 집합 A, 전이 함수 T(s, a) → s', 시작 상태 s0, 목표 상태 집합 G, 비용 함수 c(s, a, s')로 정의한다. 해는 시작 상태에서 목표 상태까지 이어지는 경로이며, 연산자를 적용한 순서다. 이 경로의 비용 합이 최소일 때 최적 해가 된다.

탐색 과정은 보통 트리로 표현하지만, 실제 문제 공간은 그래프다. 같은 상태에 여러 경로로 도달할 수 있고 순환도 생길 수 있다. 따라서 방문 집합인 Closed set으로 중복 상태를 제거하고 순환을 막아야 한다.

시작점·목표·제약이 탐색 범위를 결정한다

초기 상태는 탐색이 출발하는 지점이다. 네비게이션이라면 기동 시점의 현재 위치가 여기에 해당하며, 입력 제약과 가용 자원을 확인하는 기준이 된다.

목표 상태는 탐색을 멈추는 조건이다. 목적지 도달처럼 단일 목표일 수도 있고, 여러 제약을 모두 만족하는 다중 목표일 수도 있다. 목표 테스트 함수로 일반화할 수도 있다.

세계는 상태, 행동, 제약을 포함하는 문제 도메인 전체를 뜻한다. 완전 관찰인지 부분 관찰인지, 결정적인지 비결정적인지에 따라 적합한 탐색 전략도 달라진다.

상태공간그래프는 가능한 모든 상태와 전이를 그래프로 나타낸 것이다. 분기계수 b, 목표 깊이 d 같은 구조적 지표가 탐색 복잡도를 좌우한다.

연산자는 적용 조건과 효과를 가진 상태 전이 규칙이다. 비용은 누적 비용을 최소화하기 위한 목적 함수이며, 음수 비용을 허용하는지에 따라 선택할 수 있는 알고리즘이 제한된다. 휴리스틱은 목표까지 남은 비용을 추정하는 함수 h(n)이고, 허용성과 일관성 여부가 최적성 보장에 영향을 준다.

Open과 Closed를 순환시키는 탐색 과정

탐색의 입력은 (S, A, T, s0, G, c, h)다. Open 리스트에서 노드를 선택하고, 목표인지 검사한 뒤, 확장으로 자식 노드를 만든다. 이후 비용을 갱신하고 중복 상태를 처리한다. 결과는 해 경로 또는 실패 신호다.

Open 리스트가 고갈되면 실패를 반환한다. 순환이나 중복을 제대로 탐지하지 못하면 상태 수가 폭발적으로 늘어난다. 음수 비용이 존재하면 Dijkstra, Uniform-Cost, A*의 최적성 보장이 무너질 수 있다.

⤢✕

BFS는 FIFO 큐를 사용한다. 깊이가 증가하는 순서로 탐색하며, 균일 비용에서는 완전성과 최적성을 보장한다.

DFS는 스택을 사용해 공간 효율이 좋지만 완전성과 최적성을 보장하지 않는다.

UCS는 g(n)이 가장 작은 노드를 우선 선택하며, 비음수 비용에서 최적성을 보장한다.

Greedy Best-First는 h(n)이 가장 작은 노드를 먼저 확장한다. 빠르게 탐색할 수 있지만 최적성은 보장하지 않는다.

A*는 f(n)=g(n)+h(n)이 최소인 노드를 선택한다. 휴리스틱이 허용적이고 일관적이면 완전성과 최적성을 함께 만족한다.

알고리즘을 고를 때 보는 조건

알고리즘	완전성	최적성	시간 복잡도(대략)	공간 복잡도(대략)	확장성	운영 편의
BFS	있음	균일 비용일 때 있음	O(b^d)	O(b^d)	낮음	높음
DFS	경우에 따라	아님	O(b^m), m=최대깊이	O(b·m)	중간	높음
Uniform-Cost	있음(비음수 비용)	있음	상태·비용 분포 의존, 최악 시 지수	지수	중간	중간
Greedy Best-First	경우에 따라	아님	h 품질 의존, 평균 빠름	O(b^d)	중간	중간
A*	허용/일관 h에서 있음	있음	O(b^{d}) 대비 축소, h 품질 의존	O(b^d)	중간	중간

일관된 휴리스틱을 사용하면 A의 Closed 집합을 단순하게 처리할 수 있고 재확인(reopen)이 필요하지 않다. IDA처럼 깊이를 반복적으로 늘리는 기법은 공간 복잡도를 O(bd) 수준으로 낮출 수 있지만 재탐색 오버헤드가 생긴다.

경로·배치·게임에서의 모델링

경로 탐색과 네비게이션에서는 도로 그래프, 출발지 s0, 목적지 집합 G, 거리 또는 시간으로 표현한 간선 가중치를 입력으로 둔다. A*에 유클리드 또는 맨해튼 휴리스틱을 결합하고, 교차로 비용과 통행 제한을 반영해 최소 비용 경로, ETA, 대체 경로 옵션을 출력한다.

스케줄링과 리소스 할당에서는 작업 집합, 자원 제약, 비용과 우선순위를 입력으로 사용한다. 상태는 부분 스케줄, 연산자는 작업 할당, 휴리스틱은 잔여 작업 하한(lower bound)이 된다. 탐색 결과는 마감을 지키면서 비용을 최소화하고 충돌이 없는 배치다.

퍼즐과 게임 AI도 같은 방식으로 표현할 수 있다. 8-퍼즐에서는 타일 배치가 상태이고 빈칸 이동이 연산자이며, 맨해튼 거리나 제자리 수를 h로 쓴다. River Crossing(늑대·염소·배추)에서는 개체들의 강 좌우 배치가 상태, 보트 이동이 연산자, 유기체 충돌 금지가 제약이다. 결과는 제약을 위반하지 않는 연산자 시퀀스와 최소 이동 횟수 경로다.

휴리스틱이 상태 폭발을 줄이는 방식

효과적인 휴리스틱은 유효 분기계수 b*를 낮춰 상태 폭발을 제어한다. b=4, d=10일 때 BFS의 노드 확장은 ≈ 4^10=1,048,576이다. 휴리스틱 개선으로 b*=2.5를 달성하면 ≈ 2.5^10=9,765로 약 100배 이상 축소된다.

A*와 일관 휴리스틱을 함께 적용하면 최적 해를 보장하고 재현성도 확보할 수 있다. 문제를 상태, 연산자, 제약, 비용으로 분해하면 테스트와 디버깅도 쉬워진다. 중복 제거, 사이클 차단, 에러 처리를 표준화하면 실행을 예측 가능하게 운영할 수 있으며, 휴리스틱·비용·제약을 교체해 다른 도메인으로 옮기기도 수월하다.

실무에서는 A*를 기본으로 두고 도메인 특화 휴리스틱, 중복 처리, 제약 검증을 결합하는 구성이 적합하다. 초기 모델은 단순한 비용과 제약으로 시작한 뒤, 병목이 드러나는 구간에서 휴리스틱을 정교화하고 우선순위 큐와 해시 기반 방문 집합을 적용한다.