챕터별 상세
00:00
검색 문제의 공식화와 복습
검색 문제를 상태(State), 행동(Action), 비용(Cost), 시작 상태 및 목표 테스트로 정의하는 과정을 복습한다. 최적의 해는 시작점에서 목표점까지 도달하는 행동 시퀀스 중 총 비용의 합이 최소가 되는 경로를 찾는 것이다. 이전 시간에 다룬 Exhaustive Search와 Dynamic Programming의 한계를 짚으며 사이클이 존재하는 그래프에서의 검색 필요성을 강조했다.
06:10
Uniform Cost Search (UCS)의 원리와 구현
UCS는 시작 상태에서 현재 상태까지의 누적 비용(Past Cost)이 가장 적은 노드부터 탐색을 진행한다. 우선순위 큐(Priority Queue)를 사용하여 Frontier를 관리하며, 매 단계마다 최소 비용 노드를 꺼내 확장한다. 모든 간선의 비용이 0 이상일 때 최적의 해를 보장하며, 이는 Dijkstra 알고리즘과 수학적으로 동일한 구조를 가진다.
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보다 훨씬 적은 노드 확장으로 최적해를 찾을 수 있다.
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)은 삼각 부등식을 만족하여 탐색 과정에서 비용이 역전되지 않도록 보장한다. 그래프 검색에서는 일관성이 허용성보다 더 강력하고 필수적인 조건으로 작용한다.
56:40
완화된 문제(Relaxed Problems)를 통한 휴리스틱 설계
유효하고 강력한 휴리스틱을 설계하는 가장 체계적인 방법은 원래 문제의 제약 조건을 제거한 '완화된 문제'를 정의하는 것이다. 완화된 문제의 실제 최적 비용을 휴리스틱으로 사용하면 항상 일관성을 만족하게 된다. 예를 들어, 격자 탐색에서 벽을 통과할 수 있다고 가정하면 맨해튼 거리가 자연스러운 휴리스틱이 된다.
용어 해설
- 균일 비용 검색(Uniform Cost Search)
- — 시작 노드에서 현재 노드까지의 누적 비용이 가장 낮은 경로를 우선적으로 탐색하는 알고리즘이다. Dijkstra 알고리즘의 일반화된 형태로, 간선의 가중치가 있는 그래프에서 최단 경로를 찾는 데 사용된다. 모든 간선의 비용이 0 이상일 때 최적의 해를 보장한다.
- 휴리스틱 함수(Heuristic Function)
- — 현재 상태에서 목표 상태까지 도달하는 데 필요한 예상 비용을 추정하는 함수이다. 탐색 범위를 줄여 효율성을 높이는 데 사용되며, 실제 비용보다 크지 않게 추정하는 것이 중요하다. 좋은 휴리스틱은 탐색 성능을 비약적으로 향상시킨다.
- 일관성(Consistency)
- — 휴리스틱 함수가 삼각 부등식을 만족해야 한다는 조건이다. 즉, 현재 노드에서 다음 노드로 이동하는 실제 비용과 다음 노드의 휴리스틱 합이 현재 노드의 휴리스틱보다 크거나 같아야 함을 의미한다. 그래프 검색에서 A* 알고리즘이 최적의 해를 찾기 위한 필수 조건이다.
- 완화된 문제(Relaxed Problem)
- — 원래 문제의 제약 조건을 일부 제거하여 더 쉽게 풀 수 있도록 만든 문제이다. 완화된 문제의 최적 비용은 원래 문제의 휴리스틱 함수로 사용될 수 있다. 이를 통해 일관성을 만족하는 유효한 휴리스틱을 체계적으로 설계할 수 있다.
언급된 리소스
AI 분석 전체 내용 보기
AI 요약 · 북마크 · 개인 피드 설정 — 무료
출처 · 인용 안내
원문 발행 2026. 03. 10.수집 2026. 03. 10.출처 타입 YOUTUBE
인용 시 "요약 출처: AI Trends (aitrends.kr)"를 표기하고, 사실 확인은 원문 보기 기준으로 진행해 주세요. 자세한 기준은 운영 정책을 참고해 주세요.
