동적계획법! 그렇게 다이나믹하지 않아요

운용과학(OR)에서 여러 모형들의 기원은 그렇게 뚜렷하지 않습니다. 선형계획법이나 정수계획법 수송문제 등등...

그런데 이 동적계획법은 창조자가 잘 알려져있습니다 바로 리처드 벨만이라는 사람으로 동적계획법이 다이나믹 프로그래밍이 된것도 이 사람이 다이나믹이라는 말이 멋있어서 붙였기 때문이라는 설이 있습니다.

따라서 다이나믹이라는 뜻도 동적이라는 뜻도 이 계획법과는 상관이 없는 뜻입니다.....

 

여하튼 이번 포스트에서는 동적계획법이 무엇이며 어떻게 쓰이는지 알아봅시다.

 

동적계획법은 최적의 해를 찾기 위해 이전에 구한 답을 이용하여 문제를 푸는 기술 혹은 방법을 말합니다.

 

이렇게 써두면 직관적으로 이해가 안갑니다

 

재미있는 예를 들어보죠

 

옛날 어느 중동의 나라에 한 청년이 살고 있었습니다. 청년은 골동품을 모으는 취미가 있었는데 어느날 골동품 시장에서 신비한 램프를 샀습니다. 그리고 램프를 보관하기 위해서 닦는 순간 램프의 요정이 나타난것입니다!

 

 

램프의 요정은 램프의 봉인을 풀어준 대가로 보물을 준다고 합니다.  요정은 세계에서 가장 진귀하다는 보물 1위부터 100위까지를 가지고 있는데 전부는 줄 수 없고 자신이랑 게임을 해서 한개만 받을 수 있다고 합니다.

게임은 요정이 보물 100개를 30초마다 하나씩 보여주는데 자신이 원하는 보물에서 멈춰! 라고 말하면 그 보물을 준다고 합니다. 다만 이미 지나간 보물은 받을 수 없고 당연히 앞으로 나올 보물 또한 받을 수 없습니다.

청년은 보물을 보자마자 요정이 지금까지 보여준 보물들의 상대적인 순위를 제대로 파악할 수 있다고 할 때 과연 보물을 몇번째 보여줄 때 쯤 멈추는게 현명할까요?? 

 

이 문제는 동적계획법 문제입니다. 최적의 해는 언제쯤 멈춰야 최대의 가치가 되는지 그리고 보물의 상대적인 순위를 파악할 수 있으므로 이전 구한 답을 이용해서 문제를 풀게 됩니다. 동적계획법의 정의에 딱 맞는 문제입니다.

참고로 위 문제의 정답은 약 33번째 쯤에 보물을 받는게 가장 가치가 높습니다.

 

이렇게 복잡한 문제도 풀 수 있는 동적계획법! 그런데 아직까지는 좀 아리송합니다. 특히 지금까지 선형계획법으로 잘 풀어왔는데 동적계획법이 무슨 소용이냐!라는 말이 있을 수 있습니다. 그래서 어떤 문제를 동적 계획법으로 풀 수 있는지 알아봅시다.

 

먼저 중요한 개념은 최적성의 원칙(principle of optimality)가 없으면 동적계획법으로 풀 수 없습니다!

그러면 최적성의 원칙이 무엇인지 알아야겠죠?

 

예를 들어 봅시다

 

여러분은 의사입니다. 근대 이웃마을에 위급한 환자가 있다고 연락이 와 급하게 가야합니다. 

이웃마을까지 가는데 다음과 같은 루트가 있다고 할 때 어떤 루트로 가야할까요?

 

이런 최단경로를 찾는 문제는 대표적인 동적계획법 문제입니다.

그런데 모든 최단경로 문제가 동적계획법으로 풀 수 있을까요?

만약 위 루트에서 A루트로 가면 길이 너무 험해서 포인트에서 환자까지 가는데 1시간이 걸립니다.

편한 길인 B루트로 가면 포인트에서 환자까지 가는데 30분이 걸립니다.

이렇게 같은 지점을 가는데 그 지점에서 다음 지점으로 이동할 때 걸리는 시간이 이전 루트에 영향을 받습니다.

이렇게 되면 최적성의 원칙이 깨졌다고 합니다.

그러면 이렇게 최적성의 원칙이 깨지면 왜 동적계획법으로 풀 수 없을까요?

핵심은 이전 답을 재활용한다는 것에 있습니다.

 

만약 이전 루트에 따라서 포인트에서 환자까지 가는 길에 영향을 준다면 의사 위치에서 포인트까지 가는 길이 짧은 루트는 아무 상관이 없습니다.

짧은 루트로 갔는데 오히려 포인트에서 환자까지 가는데 시간이 다른 루트에서 온 것보다 더 걸릴 수도 있는 것이지요

기본적으로 최단경로를 찾는 문제는 A 지점에서 (정확히는 단계 안의 노드 입니다만 단계라는 용어는 나중에 다시 설명하겠습니다.)  B 지점까지의 최단경로를 알면 A지점에서 C지점으로 가는데는 B에서 C로 가는 최단 경로만 구하면됩니다.

그렇게 되면 앞서 미리 구한 A에서 B까지 가는 최단 경로 답을 이용하여 그냥 더하면 되죠 

 

min(AB) + min(BC) = min(AC) 

 

하지만 최적성의 원칙이 깨지면 위와 수식의 방식을 쓸 수 없습니다.

AB로 가는 최단 경로가 BC의 최단 경로에 영향을 주기 때문에 AC의 최단 경로라는 것을 보장하지 못하거든요

 

그러면 이제 어떤 문제가 동적계획법으로 풀 수 있는지를 알았으니 특정 문제를 동적계획법으로 나타내는 방법을 알아봅시다.

문제를 정의하기 위해서 동적계획법만의 세 가지 중요 변수가 있습니다.  

 

단계(Stage) : i 

: 동적 계획법의 단계를 나타냅니다.

 

상태(state)  : s

: 특정 단계에서 선택할 수 있는 노드를 말합니다

 

결정변수(control) : x 

: 특정 단계에서 다음 단계로 가는 최적의 상태를 선택하는 것을 말합니다.

 

 

이것을 수식으로 나타내면 다음과 같습니다.

 

이렇게 개념만 보면 머리가 아프니 정리할겸 예제를 봅시다.

 

삼송(三松)이라는 기업은 여러개의 자회사들을 두고 있는 초거대 기업이있다고 합시다.

 

이 기업에서 분석하길 자회사 3곳(삼송전자, 삼송자동차, 삼송중공업)에 경영비상이 걸려 특별경영개선팀을 파견하려고 합니다.

 

특별경영개선팀은 총 5개의 그룹이 있으며 각 회사마다 파견되는 개선팀에 따라 이득이 다음과 같다고 할 때 어떻게 경영개선팀을 보내는게 최대한 이득을 볼 수 있을까요?

 

팀의 수	삼송전자	삼송자동차	삼송중공업
1	20	30	40
2	70	70	90
3		100

 (단위 : 억원)

 

여기서 전자와 중공업은 최대 팀을 2개 자동차는 3개를 보낸다는 정책이 있습니다.

 

 

일단 이문제는 목표가 명확합니다. 최대한 돈을 벌자!

그리고 자원은 특별경영개선팀 5그룹이 있습니다.

 

동적계획법 풀이 1단계는 단계, 상태, 결정 변수를 정하는 것입니다.

먼저 이 문제에서 결정 변수를 정의해보면 [특정 그룹에 얼마나 많은 개선팀을 파견할 것인가??]가 됩니다.

 

그리고 단계를 나눠보면 

 

삼송전자-> 삼송자동차 -> 삼송중공업

이렇게 3단계로 나뉠 수 있습니다.

각 단계에서 변화하는 요소는 과연 무엇일까요?

이게 동적계획법의 킵 포인트로 바로 개선팀의 남는 개수가 변화합니다.

정확히는 자원이 변화할 수도 있는 가능성을 따지는 겁니다.

 

다시 각 단계에 상태를 부여해봅시다.

 S1              S2                 S3

삼송전자-> 삼송자동차 -> 삼송중공업

 

각 상태에서의 팀의 개수는 다음과 같습니다.

S1 = 5

S2 = 5-X2 = S1 - X2 

S3 = 5-X2-X3 = S2 - X3

 

그 다음으로 해야할 것은 각 단계에 관해서 재귀적 관계를 정립하는 것입니다.

 

요런 관계

 

 

저 위 수식은 동적계획법에서 매우 중요하므로 동적계획법을 요령껏 잘 쓸려면 외워둡시다

 

이제 저 수식으로 문제를 푸는데 푸는 방법이 다소 특이(?)합니다. 

 

출처 https://www.freetech4teachers.com/2018/06/a-quick-and-easy-way-to-create.html

 

이런 미로 찾기 아시나요??

 

미로 찾기는 출구에서 이리저리 복잡하게 헤매면서 푸는 재미가 있죠

 

근대 이 미로찾기를 쉽고 간단하게 풀 수 있는 방법이 있습니다.

 

바로 출구부터 시작하는 것이지요

그러면 놀랍게 입구에서 시작하는 것보다 더 빠르게 풀 수 있답니다.

 

그 이유는 미로찾기 알고리즘에 있습니다. 

 

 

 

(시간 나시면 한번 보시는걸 추천합니다 동적계획법으로 미로찾는 알고리즘입니다)

 

즉 출발 지점에서 부터 진행하지 않고 출구지점에서 부터 진행하자!! 이게 동적 알고리즘의 핵심입니다.

 

그러면 다시 삼송 기업의 회생(?) 팀 파견 문제로 돌아가봅시다

 

아까 본 재귀 수식에 i=3일 때를 넣습니다. 즉 마지막 단계에서 수식은 시작합니다.

 

그러면 4단계가 없으므로 자동적으로 3단계까지 누적이득과 3단계에서의 이득은 같게 됩니다

 

좀 더 식을 전개하면

 

 

이렇게 쓸 수 있습니다.

그러면 각 식마다 키포인트가 되는건 

 

이것을 구하는게 됩니다.

 

그러면 저 수식이 없는 단계는 몇단계였죠?? 그렇습니다 마지막 단계인 3단계가 없죠

 

그러면 3단계부터 상태에 따른 이득을 표로 나타내면 다음과 같습니다.

 

 

 

 

 

1단계에서 S1=5라고 위에서 언급했으므로 상태가 5일때만 계산해주면 됩니다

 

따라서 파견은

삼송전자, 삼송자동차, 삼송중공업 순서로

0개, 3개, 2개팀을 파견하던지

2개, 2개, 1개팀을 파견하는 것이 최적파견이 됩니다.

 

동적계획법은 문제에 따라서 약간의 변형이 필요할 수 있습니다 

 

다른 포스트에서 유명한 문제인 배낭 문제를 동적계획법으로 풀어보고 비교하면서 알아보면 동적계획법 풀이에 대한  좋은 시각을 가질 수 있습니다.