처음에

정적 최적화로 문제를 해결했지만 처리하는 데이터 크기가 커지면 계산이 불가능 해지기 때문에 동적 계획법을 도입하고 싶다. 그러기 위한 공부가 있다면. MATLAB에서 할 것입니다.

동적 계획법에 대해

동적 계획법에 대해서는, 다른 사이트나 Qiita, 서적등에서 공부해, 뭐 생각은 어쩐지 알았지만, 실장하려고 생각하면 꽤 어렵다고 느꼈다. 그 때문에, 예제를 풀면서 습득하려고 하는 것.

피보나치 수열 구현

이번에는 가장 간단한 곳에서 피보나치 수열을 구현하려고합니다.

피보나치 수열 복습

고등학교 수학 B? 근처에서 공부한 피보나치 수열.
(0),1,1,2,3,5,8,13,21,34,...
라는 녀석.
점화식으로 쓰면,

F_0=0\\
F_1=1\\
F_{n+2}=F_n+F_{n+1}(n\geq0)\\

된다. 1개 전과 2개 전의 합.

솔직하게 구현

피보나치 수열의 점화식에 따라 솔직하게 실장하면 다음과 같다.

fibonacci_1.m

function fib = fibonacci_1(n)
if n <= 1
    fib = n;
else
    fib = fibonacci_1(n-2)+fibonacci_1(n-1);
end
end

일단 구현이 가능했습니다.
후술하지만 입력 n이 커지면 계산 시간이 폭발합니다.

동적 계획법으로 해결

하향식(메모화)

위의 솔직한 방법에서는 n 번째를 계산하기 위해 n-1 번째와 n-2 번째를 계산해야합니다. n-3과 n-4를 계산하여 ...과 같은 상태가되므로 계산량이 $ 2 ^ n $ 인 계산이 필요합니다.
따라서 하향식 기술은 메모를 사용하여 계산량을 줄입니다. 메모화란, 결과를 유지해 두는 것으로, 재계산을 막는 수법이다. 여기서,
MATLAB에는 메모화를 위한 함수 (공식 문서)가 있습니다.
이 함수를 사용하면서 구현한 것이 이하.

fibonacci_2.m

function fib = fibonacci_2(n)
memoizedFcn = memoize(@fibonacci_2);
if n <= 1
    fib = n;
else
    fib = memoizedFcn(n-2)+memoizedFcn(n-1);
end
end

구그가 받으면 다른 언어로 피보나치 수열의 구현 예가 많이 나오지만,이 memoize 함수를 사용하면 그것에 비해 스마트하게 할 수 있는 느낌이 든다. 글쎄, 그들은 명확성을 위해 메모 기능을 사용하지 않고 구현했을 것입니다.

상향식

첫 번째 방법에서는 계산하려는 n 번째 수치에서 n이 작은 쪽으로 계산하기 위해 계산량이 많아집니다.
반대로 상향식 기술은 첫 번째부터 순서대로 n 번째까지 계산하여 추가 계산을 피합니다. 손 계산 하려고 하면 , 자연 과 이 방법 을 취할 것이기 때문에 , 비교적 당연한 것 같은 느낌 도 하지만 .
구현은 간단하고 루프를 사용하여 첫 번째부터 순서대로 n 번째까지 계산한다는 것.

fibonacci_3.m

function fib = fibonacci_3(n)
if n <= 2
    fib = 1;
else
    fib1=1;
    fib2=1;
    for i=1:n-2
        fib3=fib1+fib2;
        fib1=fib2;
        fib2=fib3;
    end
    fib=fib3;
end
end

성능 비교

동적 계획법에 의해 얼마나 계산 시간을 단축할 수 있었는지를 비교해 보자.

n=40;

tic
fibonacci_1(n);
elapsed_time_1 = toc

clearAllMemoizedCaches
tic
fibonacci_2(n);
elapsed_time_2 = toc

tic
fibonacci_3(n);
elapsed_time_3 = toc

n=40으로 했을 때의 결과가 이하.


첫 번째 방법에 비해 각각 500분의 1, 2600분의 1 이하로 크게 단축되었다.

〆

위키에도 피보나치 수열의 예는 썼습니다. 여기를 참고로 쓰고 있습니다.
글쎄, MATLAB에서 구현하면 허락하고 클레멘스 ...
이번은, 톱다운과 상향식의 수법의 느낌이 잡은 느낌.
다음에 이어지는 ...지도.