벨만 방정식 · 제5회
벨만 방정식의 진짜 힘은 동적계획법(DP)이에요. 거대한 문제를 작은 부분문제로 쪼개고, 답을 저장해 재사용하죠. ‘무식하게 다 세기’를 천문학적으로 빠르게 만드는 마법입니다.
왼쪽 위에서 오른쪽 아래로, 오른쪽·아래로만 가며 각 칸 통행료를 내요. 최소 비용 경로는? 모든 경로를 다 세면 격자가 커질수록 폭발해요.
비결 — 각 칸까지의 최소 비용을 한 번만 계산해 저장. 그 칸 비용 + (위·왼쪽 중 더 싼 쪽)이면 끝!
각 칸의 작은 수=통행료. DP 계산을 누르면 각 칸의 큰 수=거기까지 최소비용이 채워지고, 최소비용 경로가 파랗게 빛나요.
핵심은 각 칸 최소비용 = 통행료 + min(위, 왼쪽). 겹치는 부분문제를 한 번만 풀어 재사용해요(메모이제이션). 이게 벨만의 최적성 원리의 실전이에요.
V(칸) = 통행료 + min( V(위), V(왼쪽) )
‘최적 경로의 부분도 최적’ — 이 원리로 작은 답을 쌓아 큰 답을 만들어요. 지수적 계산을 다항시간으로 줄이죠. 최단경로·서열정합(DNA)·편집거리·배낭문제·음성인식이 전부 DP예요.
벨만 5부작 완주! — 가치반복부터 동적계획법까지, 최적 결정의 수학을 훑었어요. 궁금한 건 방의 Q&A 봇에! → 제6회 · 연속시간 최적제어(HJB)
『수요를 따라가는 수학 · 벨만 방정식』 제5회. 동적계획법 최소비용 경로 시뮬레이터 + 자동채점. · 벨만방정식방으로