최적화 문제
정의
최적화 문제란 주어진 조건 하에서 목표를 최대화하거나 최소화하는 해를 찾는 문제를 말한다.
구성요소
- 목표함수: 최적화하려는 대상으로 이를 최대화하거나 최소화한다.
- 제약조건: 최적화 과정에서 반드시 지켜야할 조건이다. 예를 들어 자원의 제한 등이다.
- 변수: 최적화 대상이 되는 요소로 주로 생산량, 경로, 작업 스케줄 등이다.
예시
일상생활에서 지도를 따라 최단경로 찾기가 있다. 시작점에서 도착점까지의 이동거리, 시간, 비용 등을 최소화하려하기 때문이다. 금융에서는 포트폴리오 최적화, 가격 책정 최적화가 있고 운송 등에서 버스 배차시간 최적화 등이 있다.
해결방법론
최적화 문제의 특징에 따라 적용할 수 있는 방법들이 나뉜다. 최적화문제가 최적부분구조를 갖고 있는 경우에 분할정복 기법을 적용할 수 있다. 하지만 분할정복기법을 적용하는 도중에 중복되는 계산이 발생하거나 하위 문제들 간에 의존성이 존재하는 경우에 동적계획법을 적용한다.
다이나믹 프로그래밍
정의
분할정복 시 발생하는 중복의 비효율을 제거하기 위한 알고리즘 설계기법이다. 계산 결과를 기억하는 방식으로 중복의 비효율을 제거한다.
판단기준
최적화 문제를 대상으로 최적부분구조를 가져야한다. 하위문제의 중복이 필수는 아니나 동적계획법이 사실상 적용되는 요건이다.
- 최적화 문제
- 최적부분구조
- 하위문제의 중복
적용방법
탑다운 방식과 버텀업 방식이 있다. 탑다운 방식은 재귀호출을 활용하고 바텀업방식은 반복문을 주로 활용한다. 탑다운 방식에서 계산결과를 기억하는 방식을 메모이제이션, 버텀업 방식에서는 타뷸레이션이라고 한다. 프로그래밍 특성상 버텀업 방식이 성능상 좋다.
정리
- 최적화 문제란 주어진 조건 하에서 목표를 최대화하거나 최소화하는 해를 찾는 문제다.
- 최적화 문제가 최적부분구조를 갖는 경우에 분할정복기법을 적용한다.
- 분할정복기법 적용시 하위 문제 간에 중복이 발생할 경우 또는 하위 문제 간에 의존성이 있는 경우에 동적계획법을 적용한다.
- 즉, 최적화 문제에 동적계획법을 적용하려면 ① 최적화문제가 최적부분구조 이어야하고 ② 하위문제 간에 중복이 발생하거나 의존성이 존재해야한다.
- 동적계획법의 구현전략으로 탑다운 방식과 버텀업 방식이 있다