상태공간 문제를 푸는 탐색 기법과 선택 기준

상태공간과 프론티어가 탐색의 출발점이다

탐색은 복잡한 문제를 상태공간으로 표현한 뒤, 그 안에서 해에 이르는 경로를 찾아가는 절차다. 그래프나 트리의 경로·전략·비용을 관리해 최적 해 또는 만족 해를 구하며, 인공지능, 경로 탐색, 게임 의사결정, 스케줄링에 적용된다.

상태공간은 상태(state), 시작 상태와 목표 상태, 연산자(action), 전이 함수, 비용 함수로 구성한다. 분기계수 b와 목표 깊이 d는 시간·공간 복잡도를 지배하며 O(b^d)로 나타낼 수 있다. 어떤 노드를 다음에 꺼낼지는 프론티어(Frontier) 선택 규칙이 정하고, 이 규칙에 따라 무정보탐색과 휴리스틱탐색으로 나뉜다. 평가함수 f(n)과 휴리스틱 h(n)은 이 선택에 사용된다.

상태 표현의 중복을 줄이고 불변식과 종료 조건을 먼저 명시해야 한다. 이어서 균등 또는 가중 비용 모델, 제약조건, 목표 판정자(Goal Test)를 정의한다. 프론티어는 BFS에서 FIFO 큐, DFS에서 LIFO 스택, Best-First와 A*에서 우선순위큐로 운영하며, 방문 집합 또는 트랜스포지션 테이블로 중복 상태를 관리한다.

A*의 f(n)=g(n)+h(n)처럼 평가함수를 설계할 때는 휴리스틱의 허용성(admissible)과 일관성(consistent)이 최적성에 영향을 준다. 스케일 정규화, 타이브레이킹, 음수 비용, 비단조 휴리스틱 예외도 처리 대상이다. 목표 도달, 프론티어 고갈, 시간·메모리 한도 초과를 중단 조건으로 두고, 힐클라임빙의 로컬 옵티마나 미니맥스의 가지폭 폭발에는 리스타트·프루닝·깊이 제한을 적용할 수 있다.

시간과 메모리 상한, 실시간 응답 요구, 증분적 재탐색(Anytime) 전략도 설계에 포함된다. 캐싱, 메모이제이션, Heuristic Learning은 운영 비용을 줄이는 수단이 된다.

프론티어를 꺼내고 확장하는 흐름

⤢✕

완전 탐색과 깊이·너비 우선 전략

모든 경우의 수를 열거하는 완전 탐색은 전체 상태공간을 체계적으로 방문하는 방식이다. 조합 폭발 가능성이 높으므로 가지치기와 중복 제거가 필요하다.

DFS는 스택/LIFO로 가장 깊은 노드를 우선 확장한다. 공간 효율은 O(bd)로 우수하지만, 비가중 그래프에서 최단 경로를 보장하지 않는다. 순환을 막기 위한 방문 집합 또는 깊이 제한이 필요하다.

BFS는 큐/FIFO로 레벨 순서대로 노드를 확장한다. 균등 가중 그래프에서는 최단 경로를 보장하지만 메모리 사용량이 O(b^d)로 크다. 대규모 그래프에서는 외부 메모리 또는 양방향 탐색을 고려할 수 있다.

반복적 깊이 증가(IDDFS, Iterative Deepening)는 DFS에 점차 커지는 깊이 한도를 적용한다. 균등 비용에서 BFS의 완전성·최단성과 DFS의 공간 효율을 결합한다. 휴리스틱을 쓰지 않으므로 엄밀하게는 무정보탐색이지만, 실무에서는 하이브리드 전략으로 병용된다.

휴리스틱과 게임 트리에서의 탐색

Best-First 탐색은 우선순위큐에서 평가함수가 가장 작은 노드를 먼저 확장한다. 탐욕적 Best-First는 f(n)=h(n)을 사용한다. 빠르게 진행될 수 있지만 최적성을 보장하지 않으며, 병목 구간에서는 휴리스틱 편향이 생길 수 있다.

힐 클라임빙(Hill-Climbing)은 이웃 가운데 h(n)이 개선되는 방향으로 이동하는 국소 탐색이다. 로컬 최적, 평탄면, 능선 문제가 발생할 수 있어 랜덤 리스타트나 시뮬레이티드 어닐링을 함께 사용할 수 있다.

미니맥스 프로시저(MiniMax Procedure)는 적대적 게임 트리에서 MAX와 MIN을 교대로 평가한다. 깊이 제한과 휴리스틱 평가함수를 병행하며, 알파-베타 프루닝은 동일 해를 보장하면서 노드 확장을 최대 제곱근 수준으로 줄인다.

A는 f(n)=g(n)+h(n)으로 탐색한다. h가 허용적이면 최적성을 보장하고, 일관적이면 재확장을 최소화한다. 메모리 소모가 클 때는 IDA와 RBFS로 공간을 줄일 수 있다.

기법	성능(시간)	확장성(메모리)	일관성(최적성/재현성)	안정성(리스크)	운영 편의
DFS	빠름(깊은 해 유리), 최악 O(b^d)	높음(O(bd))	낮음(최단 보장 X)	무한 루프/막다른 길 위험	구현 용이
BFS	보통~느림(O(b^d))	낮음(메모리 부담 큼)	높음(균등 비용 최단 보장)	메모리 폭주 위험	쉬움
Greedy Best-First	빠름	중간	낮음(최적성 X)	휴리스틱 편향	보통
A*	보통~느림	낮음~중간(큰 메모리)	높음(h 허용/일관 시)	메모리 고갈	보통
Hill-Climbing	매우 빠름	매우 높음	낮음(로컬 옵티마)	정체/진동	매우 쉬움
MiniMax(+αβ)	느림(b^d)	낮음(트리 폭 큼)	높음(완전 탐색 시)	시간 초과	복잡
IDDFS	보통(중복 확장)	높음	높음(균등 비용)	반복 비용	쉬움

여기서 일관성은 결과의 최적성 보장과 반복 실행 시 재현성 관점이다.

입력과 출력까지 포함해 탐색을 설계한다

DFS와 BFS는 그래프 또는 트리, 시작·목표 상태, 선택적으로 깊이 제한을 입력으로 받는다. 큐나 스택 프론티어, 방문 집합, 목표 테스트를 처리하며 경로 또는 실패와 방문 통계를 출력한다.

A*에는 g(n) 비용, 허용적·일관적 휴리스틱 h(n), 우선순위큐가 필요하다. f(n)=g+h가 최소인 노드를 꺼내고, 중복 상태에서는 더 낮은 g로 갱신한다. 일관성이 깨졌다면 재확장을 허용하며, 최적 경로·비용과 확장 노드 수를 출력한다.

MiniMax(+αβ)는 게임 상태, 평가함수, 깊이 한도를 입력으로 사용한다. MAX/MIN을 교대로 확장하고 α≥β에서 가지치기하며 무승부와 터미널 상태를 처리한다. 결과는 최적 수와 기대 유틸리티다.

Hill-Climbing은 초기 해, 이웃 생성자, 평가함수로 시작한다. 가장 크게 개선되는 이웃으로 이동하고 정체 시 랜덤 리스타트 또는 온도 스케줄(어닐링)을 사용한다. 지역 또는 전역 최적의 근사 해가 출력된다.

A* 격자 경로 탐색 코드

전제조건: Python 3.10+, 표준 라이브러리만 사용.

from heapq import heappush, heappop

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    def h(p):  # Manhattan
        return abs(p[0]-goal[0]) + abs(p[1]-goal[1])

    def neighbors(r, c):
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                yield (nr, nc)

    openq, g, parent = [], {start: 0}, {start: None}
    heappush(openq, (h(start), 0, start))  # (f, tie, node)
    closed = set()

    while openq:
        _, _, cur = heappop(openq)
        if cur in closed:
            continue
        closed.add(cur)
        if cur == goal:
            path = []
            while cur:
                path.append(cur)
                cur = parent[cur]
            return list(reversed(path))

        for nb in neighbors(*cur):
            tentative = g[cur] + 1
            if tentative < g.get(nb, float('inf')):
                g[nb] = tentative
                parent[nb] = cur
                f = tentative + h(nb)
                heappush(openq, (f, tentative, nb))
    return None

# 예시 실행
grid = [
    [0,0,0,1,0],
    [1,1,0,1,0],
    [0,0,0,0,0],
    [0,1,1,1,0],
    [0,0,0,0,0],
]
print(astar(grid, (0,0), (4,4)))

경로·의사결정·운영 문제에 적용하는 방식

물류와 로보틱스에서는 창고 피킹·AGV 경로 최적화에 A*·D*·JPS를 적용한다. 동적 장애물 환경에서는 재계획(Anytime A*)과 휴리스틱 갱신을 사용한다.

게임 AI에서는 RTS/NPC 네비게이션에 계층형 그래프(HPA*)를, 턴제 보드 게임에는 미니맥스+알파베타+이터레이티브 딥닝 조합을 적용한다.

네트워크·시스템 운영에서는 BFS로 장애 전파 경로를 역추적하고 영향 범위를 추정할 수 있다. 변경 영향 분석에는 그래프 도달성 탐색과 우선순위 기반 큐잉을 사용한다.

스케줄링과 플래닝에서는 제약 충족 문제에 Best-First와 도메인 휴리스틱(CSP: MRV/LCV)을 적용한다. 힐클라임빙과 메타휴리스틱은 근사 해 탐색과 빠른 수렴에 사용된다.

휴리스틱 품질과 자원 제약이 만드는 차이

허용 휴리스틱을 사용하는 A*는 확장 노드 수가 30~90% 감소한 사례가 보고됐다. 알파베타는 무작위 순서와 비교해 최선 정렬 시 확장 노드 수를 제곱근 수준으로 줄인다.

휴리스틱 품질에 비례해 경로 탐색 응답시간을 50% 이상 단축할 수 있다. IDDFS와 IDA* 같은 메모리 압축 전략은 메모리 사용량을 수배 절감한다. 일관된 휴리스틱은 최적성과 재현성을 확보하고, 실패·한도 초과 조건을 명시하면 운영 예측 가능성이 높아진다.

균등 비용에서 최단성이 필요하면 BFS 또는 IDDFS를, 대규모 최적 경로에는 A*를, 적대적 의사결정에는 미니맥스(+αβ)를 선택할 수 있다. 메모리와 시간 제약, 휴리스틱 품질, 운영 복잡도 사이의 트레이드오프가 선택 기준이다.