(→같이 보기) |
(→같이 보기) |
||
| (같은 사용자의 중간 판 8개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
==개요== | ==개요== | ||
;dynamic programming | ;[[dynamic]] [[programming]] | ||
;동적 | ;[[動的]] [[計劃]][[法]] | ||
*의사결정 최적화를 위한 [[수리적 계획법]] | ;동적 계획법, 동적 프로그래밍 | ||
*큰 문제를 하위문제들로 나누고 나중에 | * 대략 "재귀에 대한 최적화" ★ | ||
:하위문제들이 서로 독립적이지 않은 경우가 | * 의사결정 최적화를 위한 [[수리적 계획법]] | ||
*복잡한 문제를 간단한 | * [[수학적 최적화]] 방법이자 [[알고리즘 패러다임]]의 하나 | ||
*부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 | * 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 | ||
*여러 | * 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법 | ||
* | * 하위문제의 결과를 기록하여 나중에 다시 계산할 필요가 없도록 하는 것 ★ | ||
* 큰 문제를 하위문제들로 나누고 나중에 재결합한다. | |||
:하위문제들이 서로 독립적이지 않은 경우가 있다([[분할정복]]과 다른 점). | |||
* 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달한다. | |||
* 복잡한 문제를 재귀적인 방식으로 더 간단한 하위 문제로 분해하여 단순화하는 것이다. | |||
* 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. | |||
* 1950년대, Richard Bellman이 개발하였다. | |||
* 항공우주공학에서 경제학에 이르기까지 다양한 분야에서 응용되었다. | |||
* 여러 시점에 걸친 의사결정은 재귀적으로 분리할 수 있는 경우가 있다. (모든 의사결정 문제를 이런 방식으로 분리할 수 있는 것은 아니다) | |||
* 컴퓨터 과학에서는 문제를 하위 문제로 나눈 다음 하위 문제에 대한 최적의 솔루션을 재귀적으로 찾아 최적으로 해결할 수 있는 경우 해당 문제를 최적 하위 구조라고 한다. | |||
* 하위문제가 더 큰 문제 내에 재귀적으로 중첩되어 동적 계획법을 적용할 수 있는 경우, 더 큰 문제의 값과 하위 문제의 값 사이에는 관계가 있다. 이 관계를 최적화 문헌에서는 [[벨만 방정식]]이라고 한다. | |||
[[파일:Shortest_path_optimal_substructure.svg|300px]] | |||
==같이 보기== | ==같이 보기== | ||
{{z컬럼3| | |||
* [[동적]] | |||
* [[계획법]] | |||
* [[분할정복]] | |||
* [[수리계획법]] | * [[수리계획법]] | ||
* [[차원의 저주]] | * [[차원의 저주]] | ||
| 19번째 줄: | 32번째 줄: | ||
* [[그리디 알고리즘]] | * [[그리디 알고리즘]] | ||
* [[분할 정복 알고리즘]] | * [[분할 정복 알고리즘]] | ||
}} | |||
==참고== | ==참고== | ||
| 26번째 줄: | 40번째 줄: | ||
* {{네이버백과}} | * {{네이버백과}} | ||
[[분류: | [[분류: 동적 계획법]] | ||
[[분류: 動]][[분류: 的]][[분류: 計]][[분류: 劃]][[분류: 法]] | |||
2023년 11월 5일 (일) 17:20 기준 최신판
1 개요[ | ]
- dynamic programming
- 動的 計劃法
- 동적 계획법, 동적 프로그래밍
- 대략 "재귀에 대한 최적화" ★
- 의사결정 최적화를 위한 수리적 계획법
- 수학적 최적화 방법이자 알고리즘 패러다임의 하나
- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
- 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법
- 하위문제의 결과를 기록하여 나중에 다시 계산할 필요가 없도록 하는 것 ★
- 큰 문제를 하위문제들로 나누고 나중에 재결합한다.
- 하위문제들이 서로 독립적이지 않은 경우가 있다(분할정복과 다른 점).
- 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달한다.
- 복잡한 문제를 재귀적인 방식으로 더 간단한 하위 문제로 분해하여 단순화하는 것이다.
- 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
- 1950년대, Richard Bellman이 개발하였다.
- 항공우주공학에서 경제학에 이르기까지 다양한 분야에서 응용되었다.
- 여러 시점에 걸친 의사결정은 재귀적으로 분리할 수 있는 경우가 있다. (모든 의사결정 문제를 이런 방식으로 분리할 수 있는 것은 아니다)
- 컴퓨터 과학에서는 문제를 하위 문제로 나눈 다음 하위 문제에 대한 최적의 솔루션을 재귀적으로 찾아 최적으로 해결할 수 있는 경우 해당 문제를 최적 하위 구조라고 한다.
- 하위문제가 더 큰 문제 내에 재귀적으로 중첩되어 동적 계획법을 적용할 수 있는 경우, 더 큰 문제의 값과 하위 문제의 값 사이에는 관계가 있다. 이 관계를 최적화 문헌에서는 벨만 방정식이라고 한다.
2 같이 보기[ | ]
3 참고[ | ]
네이버백과 "동적 계획법"
로그인하시면 댓글을 쓸 수 있습니다.
{{ comment.name }}
{{ comment.created | snstime }}
-
{{comment.page_title}} ―{{comment.name}}