2.1 문제해결전략과 동적계획법 : 강화학습의 수학적 기초와 알고리즘의 이해

강화학습의 수학적 기초와 알고리즘의 이해 강의를 듣고, 정리한 글 임을 밝힙니다.

 

수학적 귀납법(Mathematical induction)

$p_1, p_2, p_3, \dots$ 라는 참 또는 거짓인 명제가 있다고 하자

1. $p_1$이 참이고,
2. 모든 $n \ge 1$ 에 대해 $p_n$이 참일 때 $p_{n+1}$도 참이라면,
3. $p_1, p_2, \dots$ 모두 참이다

 

문제

동적계획법(DP)으로 풀기

$$ V(i,j) = min \begin{cases} C_{ij} + V(i,j +1) \\ C_{ij} + V(i + 1, j) \end{cases} $$

 

동적 계획법으로 찾은 최소경로 답

탐욕 알고리즘(Greedy Algorithm)

매 순간 최선의 선택

 

 

분할 정복 알고리즘(Divide-and-conquer Algorithm)

• 문제를 하나 이상의 작은 문제로 분할
• 작은 문제들을 각각 정복 if 정복이 어렵다면, 다시 더 작은 문제들로 분할
• 필요하다면, 작은 문제들에 대한 해답을 통합하여 원래 문제의 해답을 구함

 

동적 계획법(DP)

→ 다단계(multistage) 혹은 순차적(sequential)의사결정 프로세스

• 주어진 문제를 중첩되는 작은 문제들(overlapping subproblems)로 단순화
• 재귀적인 구조식 정의 → 상위 부분문제와 하위 부분문제 간의 관계 도출
• 하위 부분문제를 해결한 결과를 활용 → 상위 부분 문제를 재귀식을 통해 해결

• 최적 부분 구조 (optimal substructure)
  • 최적화의 원리 (principle of optimality)
    • 한 문제에 대한 해가 최적이라면, 그 문제를 이루는 모든 부분문제들에 해당하는 부분해가 부분문제의 최적해 이다.
    • 어떤 문제의 최적해가 그 문제를 분할한 부분문제에 대한 최적해를 항상 포함한다.

 

< 분할 정복과 동적 계획법의 차이 >