[KMOOC 강화학습] Week 02-1 문제해결전략과 동적계획법
해당 강의는 K-MOOC의 “강화학습의 수학적 기초와 알고리즘 이해” 수업을 수강하며 기록한 내용입니다. 강의는 링크에서 확인하실 수 있습니다.
수학적 귀납법
- 어떤 명제가 참 혹은 거짓이라고 한다.
- 첫번째 상태가 참이라고 하고
- 어떤 상태가 참이라고 할 때
- 다음 상태도 참임을 보이면서 증명하는 것
⚡ 이렇게 수학적 귀납법으로 유도할 때 결국 n번째 상태에 대한 정보를 이용하여 (n+1)번째 상태를 도출하게 된다.
☝ 이것이 재귀식(recursive equation)을 통해 문제를 해결하게 된거다!
최소 비용 경로 구하기
최소 비용 경로란?
행렬 칸의 각 숫자($C_{i,j}$)는 해당 위치 별 비용을 말한다.
해결책
$V(i,j)$ : 임의의 칸에서 (4,5)로 이동할 때의 비용
라고할 때 다음과 같이 정의할 수 있다.
$V(i,j) = min (C_{i,j}+V(i,j+1), C_{i,j}+V(i+1,j))$
마지막 칸에서 역방향으로 V 행렬을 위의 재귀식을 이용해서 채워나가서 먼저 지도를 그린 다음, 역방향으로 최소비용 방향을 기록하면 된다!
☝ 즉 동적계획법은 해당 행동의 미래의 영향을 현재 시점에서 계산한다
탐욕 알고리즘(Greedy Algorithm)
Greedy algorithm은 매 순간 미래참조 없이 현재 상황에서 최선을 선택하게 된다.
분할 정복 알고리즘(Devide and conquer algorithm)
주어진 문제를 작은 문제로 분할해서 하나씩 해결하는 방식으로 최종 큰 문제에 대한 해답은 작은 문제별 해답을 합치게 되는 것이다!
이는 exclusive하게 문제를 나누게 된다.
동적 계획법
리처드 벨먼이 1950년도에 제안한 방법론으로, 여러 단계에 걸쳐 순차적으로 의사결정을 하여 다단계(multistage) 혹은 순차적(sequential) 프로세스를 가지기에 dynamic하고 Planning 개념의 프로그래밍을 말한다.
☝ 이 방식의 특징은 이전의 의사 결정이 이후에 영향을 끼치게 된다.!
방법론
중첩된 작은 문제로 단순화하여 재귀적인 구조를 활용한다. 그런 다음 부분 문제들을 순차적으로 해결한다.
☝ 문제들이 subset 관계를 가지고 상위 문제와 하위 문제 간의 관계를 표현하여 해결하는 방식을 말한다.
댓글남기기