이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.
핵심 요약
Uniform Cost Search는 과거 비용을 기반으로 최적성을 보장하며, A* 검색은 휴리스틱을 통해 미래 비용을 예측함으로써 탐색 효율을 극대화한다. 일관성 있는 휴리스틱 설계가 알고리즘의 성능과 정확도를 결정하는 핵심이다.
배경
스탠포드 대학교의 대표적인 AI 강의인 CS221의 검색 알고리즘 세션이다.
대상 독자
컴퓨터 과학 전공자, AI 알고리즘의 수학적 원리를 이해하고자 하는 개발자
의미 / 영향
이 강의는 AI 에이전트의 의사결정과 경로 계획에 필수적인 검색 알고리즘의 이론적 토대를 제공한다. 실무적으로는 로봇 경로 탐색, 게임 AI, 물류 최적화 등 다양한 분야에서 탐색 비용을 최소화하는 시스템을 설계하는 데 직접적으로 활용 가능하다. 특히 휴리스틱 설계 원칙은 복잡한 현실 문제를 알고리즘이 해결 가능한 형태로 변환하는 핵심 기술이다.
챕터별 상세
00:00
검색 문제의 공식화와 복습
검색 문제를 상태(State), 행동(Action), 비용(Cost), 시작 상태 및 목표 테스트로 정의하는 과정을 복습한다. 최적의 해는 시작점에서 목표점까지 도달하는 행동 시퀀스 중 총 비용의 합이 최소가 되는 경로를 찾는 것이다. 이전 시간에 다룬 Exhaustive Search와 Dynamic Programming의 한계를 짚으며 사이클이 존재하는 그래프에서의 검색 필요성을 강조했다.
- •검색 문제는 상태 공간을 탐색하여 최소 비용 경로를 찾는 과정이다
- •Dynamic Programming은 사이클이 없는 경우에만 유효하다
- •사이클이 있는 일반적인 그래프 검색을 위해 새로운 알고리즘이 필요하다
06:10
Uniform Cost Search (UCS)의 원리와 구현
UCS는 시작 상태에서 현재 상태까지의 누적 비용(Past Cost)이 가장 적은 노드부터 탐색을 진행한다. 우선순위 큐(Priority Queue)를 사용하여 Frontier를 관리하며, 매 단계마다 최소 비용 노드를 꺼내 확장한다. 모든 간선의 비용이 0 이상일 때 최적의 해를 보장하며, 이는 Dijkstra 알고리즘과 수학적으로 동일한 구조를 가진다.
- •누적 비용(Past Cost)을 기준으로 탐색 순서를 결정한다
- •우선순위 큐를 통해 효율적으로 최소 비용 노드를 선택한다
- •모든 간선 비용이 비음수(Non-negative)일 때 최적성이 보장된다
Frontier는 탐색 대기 중인 노드들의 집합이며, Explored Set은 이미 최단 경로가 확정된 노드들의 집합이다.
python
def uniform_cost_search(problem):
frontier = PriorityQueue()
frontier.update(problem.start_state(), 0)
explored = set()
while True:
state, past_cost = frontier.remove_min()
if problem.is_end(state):
return solution
explored.add(state)
for action, cost, next_state in problem.successors(state):
if next_state not in explored:
frontier.update(next_state, past_cost + cost)우선순위 큐를 사용하여 누적 비용이 가장 적은 노드부터 탐색하는 Uniform Cost Search의 핵심 로직이다.
29:50
A* 검색: 휴리스틱을 이용한 탐색 가속화
A* 검색은 UCS의 누적 비용에 목표 상태까지의 예상 비용인 휴리스틱(Heuristic)을 더해 탐색의 방향성을 부여한다. f(s) = g(s) + h(s) 공식을 사용하며, 여기서 g(s)는 과거 비용, h(s)는 미래 추정 비용이다. 휴리스틱을 통해 목표와 상관없는 방향의 탐색을 억제함으로써 UCS보다 훨씬 적은 노드 확장으로 최적해를 찾을 수 있다.
- •휴리스틱 함수 h(s)는 목표까지의 남은 비용을 추정한다
- •A*는 UCS에 미래 예측 지능을 결합한 형태이다
- •좋은 휴리스틱은 탐색해야 할 노드 수를 획기적으로 줄인다
python
def astar_search(problem, heuristic):
# A* is UCS with modified costs
# cost'(s, a) = cost(s, a) + h(succ(s, a)) - h(s)
modified_problem = ModifiedSearchProblem(problem, heuristic)
return uniform_cost_search(modified_problem)A* 검색을 휴리스틱이 적용된 수정된 비용을 사용하는 UCS로 구현하는 방식이다.
42:00
휴리스틱의 조건: 허용성과 일관성
A* 알고리즘이 최적해를 보장하기 위해서는 휴리스틱이 특정 조건을 만족해야 한다. 허용성(Admissibility)은 휴리스틱이 실제 비용을 과대평가하지 않아야 함을 의미하며, 일관성(Consistency)은 삼각 부등식을 만족하여 탐색 과정에서 비용이 역전되지 않도록 보장한다. 그래프 검색에서는 일관성이 허용성보다 더 강력하고 필수적인 조건으로 작용한다.
- •허용성은 h(s)가 실제 최단 거리보다 작거나 같아야 함을 뜻한다
- •일관성은 모든 간선에 대해 h(s) <= cost(s, a) + h(s')를 만족해야 한다
- •일관성이 깨지면 이미 탐색한 노드를 다시 탐색해야 하는 비효율이 발생한다
56:40
완화된 문제(Relaxed Problems)를 통한 휴리스틱 설계
유효하고 강력한 휴리스틱을 설계하는 가장 체계적인 방법은 원래 문제의 제약 조건을 제거한 '완화된 문제'를 정의하는 것이다. 완화된 문제의 실제 최적 비용을 휴리스틱으로 사용하면 항상 일관성을 만족하게 된다. 예를 들어, 격자 탐색에서 벽을 통과할 수 있다고 가정하면 맨해튼 거리가 자연스러운 휴리스틱이 된다.
- •제약 조건을 제거하여 문제를 단순화한다
- •단순화된 문제의 최적 비용은 원래 문제의 하한선(Lower Bound)이 된다
- •완화된 문제의 비용을 사용하면 수학적으로 일관성이 보장된다
실무 Takeaway
- 복잡한 경로 탐색 시 UCS를 기본으로 사용하되, 도메인 지식이 있다면 A*를 적용하여 성능을 최적화해야 한다
- A*의 휴리스틱 설계 시 반드시 일관성(Consistency) 조건을 체크하여 최적해가 보장되는지 확인해야 한다
- 새로운 문제에 대한 휴리스틱이 떠오르지 않는다면 문제의 제약 조건을 하나씩 제거해보며 완화된 문제를 구성해본다
- 우선순위 큐의 효율적인 관리가 대규모 상태 공간 검색의 실제 구현 성능을 좌우한다
언급된 리소스
AI 분석 전체 내용 보기
AI 요약 · 북마크 · 개인 피드 설정 — 무료
출처 · 인용 안내
원문 발행 2026. 03. 10.수집 2026. 03. 10.출처 타입 YOUTUBE
인용 시 "요약 출처: AI Trends (aitrends.kr)"를 표기하고, 사실 확인은 원문 보기 기준으로 진행해 주세요. 자세한 기준은 운영 정책을 참고해 주세요.