Heuristic Search (휴리스틱 탐색 / 정보 탐색)
무차별 전수조사(Blind Search)의 지수적 폭발을 극복하기 위해 도메인 지식(평가 함수)을 나침반 삼아 가장 유망한 경로를 질주하는 지능형 탐색 기술. A* 알고리즘과 게임 트리 가지치기에서 시작하여, 오늘날 Tree-of-Thoughts 및 OpenAI o1, DeepSeek-R1의 추론 시간 탐색(Inference-Time Search Scaling)으로 진화한 AI의 영원한 핵심 동력입니다.
💡 "휴리스틱 탐색은 그래프로 표현된 문제에 대한 도메인 정보(Heuristic Information)를 이용하여 목표까지의 탐색 작업을 극적으로 가속하는 방식이다"
📑 핵심 목차 안내
1. 휴리스틱 탐색의 개념과 맹목적 탐색(Blind Search)의 한계
깊이우선 탐색이나 너비우선 탐색 등의 Blind Search (무정보 탐색 / 맹목적 탐색) 방법은 목표(Goal)까지의 경로를 찾는 상당히 소모적인(exhaustive) 방법입니다. 즉, 이론적으로는 문제에 대한 해를 제공하지만 너무 많은 노드를 확장시키므로 실용적인 복잡도에서는 계산이 불가능해집니다.
수많은 현실 문제에 있어 탐색 작업을 축소시키기 위해, 항상 옳은 최적해를 보장하지는 못하지만 대부분의 경우에 잘 들어맞는 경험에 의한 규칙(Rules of Thumb) 을 이용하는 경우가 많습니다. 이렇게 그래프로써 표현된 문제에 대한 특별한 정보를 이용하여 탐색 (Search) 작업을 빠르게 진행시키는 방식을 휴리스틱 탐색 (Heuristic Search Method) 이라 하며, 이때 사용된 도메인 정보를 Heuristic Information 이라 부릅니다.
🔗 Heuristic Search 의 역사 살펴보기 →
● Blind (또는 Uninformed) Search
도메인 지식 없이 기계적으로 노드를 확장하는 무정보 탐색:
● Heuristic (또는 Informed, Best-First) Search
경험적 평가 함수를 가이드 삼아 유망한 경로를 질주하는 정보 탐색:
2. 평가 함수(Evaluation Function)의 원리와 기준
휴리스틱 (Heuristic) 은 새로이 생성된 후계 노드들을 휴리스틱 정보에 따라 정해지는 기준에 의해 순서를 정하거나 재조정하는 것입니다. 이렇게 함으로써 탐색 엔진은 목표에 가장 가까운 바람직한 부분을 우선적으로 확장시켜 나가게 됩니다.
📏 평가 함수 (Evaluation Function) 의 목적과 설계 착상
노드의 바람직한 정도를 정량적으로 평가하기 위한 척도를 평가함수 (evaluation function) 이라 합니다. 평가 함수의 궁극적인 목적은 확장시킬 노드들에게 순위를 매김으로써 어떤 것이 목표 노드까지의 최상의 경로에 있음직한가를 결정하는 것입니다.
- 확률적 착상: 어떤 노드가 최상의 경로 상에 존재할 확률을 통계적으로 추정.
- 기하학적 거리 및 차이: 현재 노드와 목표 노드 간의 유클리드 거리, 맨해튼 거리(Manhattan Distance), 차이(Difference) 계산.
- 게임 및 퍼즐 특성: 게임 (Game) 이나 퍼즐에서 판의 국면 가치, 말의 점수, 제자리에서 벗어난 타일 수 등 목표 도달 가능성과 관계된 핵심 특성에 근거.
3. 전통 인공지능의 대표적 휴리스틱 탐색 알고리즘과 실제 활용 예
전통 심볼릭 AI에서 발전한 5대 휴리스틱 탐색 알고리즘은 계산 비용과 최적성 보장 사이의 다양한 트레이드오프를 보여줍니다:
⛰️ 1. 언덕오르기 (Hill Climbing)
현재 상태에서 평가 함수 값이 가장 높은 이웃 상태로만 즉각 이동하는 탐욕적(Greedy) 기법.
⚠️ 한계: 지역 최적해(Local Optima)나 고원(Plateau)에 갇히기 쉬움.
활용 예: 초기 기계학습의 파라미터 최적화, 단순 회로 배치.
🎯 2. 최상우선 탐색 (Best-First)
오픈 리스트(Open List)에 보관된 모든 후보 노드 중 휴리스틱 값 h(n)이 가장 뛰어난 노드를 우선 확장.
특징: 언덕오르기보다 넓은 시야를 가지나 최단 경로 보장은 못함.
활용 예: 초기 자연어 구문 분석 트리 탐색, 웹 크롤러 스케줄링.
⭐ 3. A* 알고리즘 (A* Search)
f(n) = g(n) + h(n)
출발지부터의 실제 누적 비용 g(n)과 목표까지의 추정 비용 h(n)을 합산. h(n)이 실제보다 과대평가하지 않는 허용성(Admissibility)을 갖추면 수학적으로 최적 경로를 100% 보장.
활용 예: 자동차 GPS 내비게이션 최단 경로, 스타크래프트/RPG 유닛 길찾기.
🔁 4. 반복적 깊이증가 A* (IDA*)
A* 알고리즘의 최대 약점인 메모리 폭발(모든 노드를 큐에 저장)을 깊이 우선 탐색(DFS)의 선형 메모리 사용과 결합하여 극복.
특징: 메모리 절약 + 최적성 유지.
활용 예: 15-퍼즐, 24-퍼즐, 루빅스 큐브(Rubik's Cube)의 최적 해법 탐색.
🌿 5. 분기한정법 (Branch & Bound)
문제를 부분 문제로 쪼개고(Branch), 휴리스틱으로 계산한 하한값(Bound)이 이미 발견한 최적해보다 나쁘면 하위 트리를 즉각 잘라내는 가지치기 기법.
활용 예: 외판원 순회 문제(TSP), 0-1 배낭 문제(Knapsack Problem), 정수 계획법.
♟️ 6. 알파베타 가지치기 (Alpha-Beta)
체스, 바둑 등 적대적 게임 트리에서 상대방이 절대로 허용하지 않을 불리한 분기를 사전에 잘라내는 게임 전용 휴리스틱 탐색.
활용 예: IBM Deep Blue 체스 챔피언 프로그램, 오델로 AI.
4. [인포그래픽 1] 전통 휴리스틱 탐색 알고리즘 특성 비교 지도
| 알고리즘 | 평가 함수 공식 | 최적성 (Optimality) | 메모리 복잡도 | 주요 실제 활용 분야 |
|---|---|---|---|---|
| 언덕오르기 (Hill Climbing) | f(n) = h(n) | 보장 불가 (Local Optima) | O(1) (상수) | 단순 파라미터 튜닝, 국소 탐색 |
| 최상우선 탐색 (Best-First) | f(n) = h(n) | 보장 불가 (탐욕적) | O(bm) (지수) | 초기 AI 파서, 경로 가이드 |
| A* 알고리즘 | f(n) = g(n) + h(n) | 100% 보장 (h(n) 허용 시) | O(bd) (지수 / 메모리 취약) | GPS 내비게이션, 게임 길찾기 |
| 반복적 깊이증가 A* (IDA*) | f(n) 임계값 기반 DFS | 100% 보장 | O(d) (선형 / 극저용량) | 루빅스 큐브, 15/24-퍼즐 최적해 |
| 분기한정법 (Branch & Bound) | 하한선(Lower Bound) | 100% 보장 | O(bd) (가지치기 축소) | 외판원 문제(TSP), 배낭 문제 |
5. 최신 AI 와 거대 언어 모델(LLM)에서 Heuristic Search 의 진화와 의미
"좌에서 우로 뱉는 단순 확률 생성을 넘어, 생각의 공간(Thought Space)을 체스처럼 탐색하는 인지적 탐색 혁명"
🌌 1. 탐색 공간의 대전환: 정형 그래프에서 '언어적 사고 공간(Thought Space)'으로
전통 AI에서 탐색의 노드는 2D 미로의 좌표나 체스 말의 위치처럼 사전에 엄밀히 정의된 이산 상태였습니다. 그러나 최신 LLM에서의 휴리스틱 탐색은 자연어로 쓰여진 논리적 추론 단계(Reasoning Steps) 자체를 상태 노드로 삼는 거대한 언어 공간으로 확장되었습니다.
과거의 탐욕적 생성(Greedy Autoregressive Decoding)은 첫 단추를 잘못 끼우면 끝까지 엉뚱한 답을 쏟아내는 치명적 결함이 있었습니다. 현대 LLM은 복잡한 질문을 받았을 때 사고의 중간 단계들을 여러 갈래의 트리로 전개하며 최적의 논리 경로를 탐색합니다.
🧠 2. 평가 함수의 진화: 수동 휴리스틱 h(n)에서 '프로세스 보상 모델(PRM)'로
전통 AI에서 휴리스틱 함수 h(n)은 인간 엔지니어가 수학적으로 설계한 맨해튼 거리나 체스 기물 가치였습니다.
반면 최신 LLM 시스템에서는 학습된 신경망 검증기인 프로세스 보상 모델 (PRM, Process Reward Model) 이
h(n)의 역할을 완벽히 대체합니다:
- Outcome Reward Model (ORM)의 한계: 최종 정답만 맞추면 중간 논리가 틀려도 보상을 주어 환각을 방치하는 문제.
- Process Reward Model (PRM)의 혁신: "스텝 바이 스텝"의 각 단계마다 "이 추론 단계가 수학적·논리적으로 참인가?"를 0.0~1.0의 실수로 실시간 채점하는 현대판 휴리스틱 평가 함수.
🌳 3. Tree-of-Thoughts(ToT)와 MCTS 기반 추론 시간 컴퓨팅
OpenAI o1, DeepSeek-R1과 같은 최첨단 추론 모델의 핵심은 바로 알파고(AlphaGo)가 사용했던 몬테카를로 트리 탐색(MCTS)과 A*의 가지치기 원리를 자연어 사고 사슬(CoT)에 결합한 것입니다:
- 대안 경로 시뮬레이션: 한 단계의 추론에서 3~5가지 가능한 다음 사고를 생성(Branching).
- 휴리스틱 가지치기 (Pruning): PRM 평가 점수가 낮은 오답 경로는 즉각 포기.
- 백트래킹 (Backtracking): 전개 도중 모순에 부딪히면 이전 분기점으로 되돌아가 새로운 해결책을 탐색.
👑 4. '쓰디쓴 교훈(The Bitter Lesson)'과 휴리스틱 탐색의 왕좌 복귀
인공지능의 거두 리처드 서튼(Richard Sutton)은 2019년 기념비적 에세이 《The Bitter Lesson》 에서 "인간의 도메인 지식을 정교하게 코딩하는 것보다, 막대한 컴퓨팅 파워를 활용한 '학습(Learning)'과 '탐색(Search)'이 결국 항상 승리한다"고 갈파했습니다.
사전학습 데이터 고갈과 GPU 클러스터 비용 폭증으로 기존 스케일링 법칙이 둔화되는 시점에서, "추론 시간(Test-time)에 모델이 얼마나 깊고 정교하게 사고 공간을 휴리스틱 탐색하는가"가 수학 올림피아드(AIME), 복잡한 코딩, 과학적 가설 발견의 성능을 비약적으로 끌어올리는 새로운 구원투수로 등극했습니다.
6. [인포그래픽 2] 전통 휴리스틱 탐색 vs 최신 LLM 추론 시간 탐색 비교
| 비교 항목 | 전통 휴리스틱 탐색 (Classical Heuristic Search) | 최신 LLM 추론 시간 탐색 (ToT / o1 / R1) |
|---|---|---|
| 탐색 공간 (State Space) | 수학적으로 정의된 격자 좌표, 지도 도로망, 퍼즐 상태 | 자연어로 서술된 다단계 논리적 사고 공간(Thought Steps) |
| 노드 생성 (Expansion) | 사전 정의된 연산자(Operator: 상/하/좌/우 이동) | LLM 자기회귀 생성을 통한 다양한 대안 가설 및 추론 단계 생성 |
| 평가 함수 h(n) | 인간이 수작업으로 공식화한 맨해튼 거리, 직선 거리 | 학습된 프로세스 보상 모델(PRM) 및 가치 신경망 채점 점수 |
| 백트래킹 & 가지치기 | 오픈/클로즈 리스트 기반의 A* 및 분기한정 가지치기 | MCTS 롤아웃 기반 자가 비판(Self-Critique) 및 오답 경로 폐기 |
| 컴퓨팅 자원 투입 시점 | 경로 탐색 쿼리 실행 시간 (수 밀리초~수 초) | 추론 시간(Test-time Compute) 확장 — 수 초~수 분간 사고 전개 |
| 대표적 구현 | A* GPS 길찾기, 딥블루 체스, 15-퍼즐 풀이 | OpenAI o1, DeepSeek-R1, Tree-of-Thoughts (ToT) |
7. 전문가 추천 영상: A* 최적 탐색부터 LLM Tree-of-Thoughts까지
MIT 인공지능 명강의와 최신 Tree-of-Thoughts 논문 분석 영상을 통해 휴리스틱 탐색의 고전과 현대적 부활을 영상으로 확인하세요.
[MIT 6.034] 최적 탐색, 분기한정법과 A* 알고리즘
패트릭 윈스턴(Patrick Winston) 교수의 휴리스틱 허용성(Admissibility)과 A* 최단 경로 보장 원리 명강의.
[논문 해설] Tree of Thoughts: LLM의 신중한 문제 해결
Yannic Kilcher — 단순 CoT를 넘어 사고 공간을 트리로 탐색하고 자가 평가·역추적하는 최신 휴리스틱 탐색 프레임워크.