동적계획법에 확률같은걸 끼얹나? (확률적인 동적계획법 문제)

일반적으로 동적계획 문제는 최적 경로 찾기나 지정된 3곳 중에 금액이나 사람 등을 몇 개 투입해야 최대 이익이 될 수 있는지 등을 계산하였습니다.

그런데 만약 다음과 같은 경로 찾기 문제를 생각해봅시다

A   --   B    --   D

    ㄴ  C   ┘     

여기서 A에서 B와 C로 갈 수 있다고 할 때 그냥 거리가 짧은 쪽을 고르면 쉽게 풀리는 문제입니다.

그런데 만약 A에서 B와 C를 확률적으로 갈 수 있다고할 때  즉, 두 길이 50%와 50%확률로 갈 수 있다고 할 때 는 어떻게 될까요?

 

가장 기본적인 생각은 기댓값이라는 아이디어입니다.

로또복권 한장을 사면 기댓값이 22원 정도... 만원내기로 동전 던지기를 할 때 기댓값은 5천원...

이렇게 실제 실현된 값은 아니지만 기댓값이라는 개념으로 위의 문제에서 확률에 따른 길의 길이를 기댓값으로 수치화 할 수 있습니다. 따라서 이 기댓값을 가지고 동적계획법 계산이 가능해집니다.

 

예를 들어보죠

여러분은 아주 잘나가는 햄버거 요리사입니다.

 

 

 그런데 어느날 아주 유명한 미식가가 찾아와 햄버거 하나를 주문합니다.

이 미식가를 만족시키면 자신의 평판이 오를것이 분명하기 때문에 최대한 열심히 만들려고합니다.

그런데 미식가가 어떤 취향인지를 몰라서 일단 햄버거를 여러개 만들 생각도 해봅니다.

과연 이 미식가를 만족시킬 수 있을까요??

 

이때 확률론적 동적계획법을 사용하면 미식가를 최대한으로 만족하고 여러분의 평판과 임금이 오를 수 있습니다!! 

 

일단 저기서 추가적인 조건이 있습니다.

  1. 일단 여러분은 한번 요리를 시작하면 무조건 3천원이 소모되며 햄버거 하나당 추가적으로 1천원이 더 소모됩니다.

  2. 한번 요리를 시작하면 5분이 소요됩니다.

  3. 임의로 만든 햄버거 하나가 미식가를 만족시킬 확률은 50%이며 모든 햄버거가 입맛에 안맞으면 1.6만원의 손해를 입습니다.

  4. 미식가는 15분동안 기다려 줄 수 있습니다.

이때 어떻게하면 최소한의 소모로 미식가를 만족시킬 수 있을까요?

 

그러면 잘 생각해봅시다. 3개를 만들었는데 미식가가 만족하는 퀄리티의 햄버거가 2개라고한다면 의미가 있을까요?

미식가는 하나의 햄버거만 주문했기 때문에 1개 이상을 만족시키는 것은 의미가 없습니다.

그러면  목표는 최소한으로 만들어서 최대한 미식가를 만족시킬 수 있는 L값을 정하는 것입니다.

 

따라서 미식가가 만족할 확률은 다음과 같이 정해집니다.

 

 

이제 햄버거에 대한 기댓값을 정의해봤으니 동적계획법에서 중요한 3가지 요소 단계, 상태, 결정변수를 정의해 봅시다.

 

먼저 단계!

여기서는 단계란 미식가가 최대 15분을 기다려줄 수 있고 요리 한번하는데 5분이 소요되므로 총 3번 요리할 동안 기다려 줄 수 있습니다. 

 

따라서 단계는 3개가 있다고 볼 수 있습니다.

 

그러면 상태와 결정변수를 분석해봅시다.

 

결정변수는 뭘까요? 여기서 변경할 수 있는 숫자는 한번에 생산하는 햄버거의 갯수뿐이죠?

 

마지막으로 상태는 특정 단계에서 만족 했는가 안했는가 입니다.

 

그래야 만족하는 루트로 갈지 만족하지 못하는 루트로 갈지 정할 수 있거든요

 

 

그러면 이제 식을 정의해봅시다

 

한 단계당 무조건 요리를 해야하고 햄버거 수에 따라 비용이 달라지므로 다음과 같이 나타낼 수 있습니다.

3+Li

 

따라서 이 문제의 동적계획법 수식은 다음과 같습니다.

 

 

따라서 이것을 다시 동적계획법에서 풀듯이 뒤에서 부터 풀면 다음과 같습니다.

 

 

 

 

어때요 그냥 동적계획법과 다를바없이 쉽지 않나요?