[강화학습] 문제해결전략

탐욕 알고리즘(Greedy algorithm)

매 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행해 최종적인 최적해에 도달하는 기법

 

 

---

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

주어진 문제 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법

 

문제를 하나 이상의 작은 문제로 분할(divide)

작은 문제들을 각각 정복(conquer)

필요하다면, 작은 문제데 대한 해답을 통합(combine)하여 원래 문제의 해답을 구함

---

동적계획법(Dynamic programming)

주어진 문제를 중첩되는 작은 문제들로 단순화한 후, 재귀적인 구조를 활용하여 전체 문제를 해결

 

전체 문제를 일련의 중첩되는 부분문제로 정의

재귀적인 구조식을 정의 (상위 부분문제와 하위 부분문제 간의 관계 도출)

하위 부분문제의 결과를 활용해 상위 부분문제를 재귀식으로 해결'

 

=> 순차적으로 의사결정하여 문제 해결 !

 

---

분할정복 알고리즘과 동적계획법의 차이

분할정복 알고리즘은 큰 문제를 잘게 쪼개는 방법이기 때문에 부분 문제 간의 연관성이 없다.

동적계획법은 상위 문제가 하위문제를 내포하고 있어 하위문제부터 해결해가면서 상위문제를 해결하는 방법이다.

 

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

 

 

 

[참고]

http://www.kmooc.kr/courses/course-v1:KoreaUnivK+ku_ai_002+2020_A44/about