상향식과 하향식의 차이점은 무엇입니까?

상향식과 하향식의 차이점은 무엇입니까?

---

상향식 (동적 프로그래밍) 방법은 먼저 "작은"하위 문제를 찾고 구성하고 작은 문제의 해결책을 사용하여 큰 하위 문제를 해결한다.

하향식 (top-down)은 당신이 전에 하위 문제에 대한 해결책을 계산 한 경우 "자연으로"체크에서 문제 해결에 구성되어 있습니다.

조금 혼란 스러워요. 이 둘의 차이점은 무엇입니까?

---

rev4 : 사용자 Sammaron의 매우 설득력있는 설명은 아마도이 답변이 이전에 하향식과 상향식을 혼동한다고 언급했습니다. 원래이 답변 (rev3)과 다른 답변에서 "하단은 메모 화"( "하위 문제 가정")라고 말했지만, 그 반대 일 수 있습니다 (즉, "하향 문제"는 "하위 문제 가정"및 " 상향식 "은"하위 문제 구성 "일 수 있습니다. 이전에는 동적 프로그래밍의 하위 유형이 아닌 다른 종류의 동적 프로그래밍 인 메모에 대해 읽었습니다. 나는 구독하지 않았음에도 불구하고 그 견해를 인용했다. 나는이 답변이 문헌에서 적절한 참조를 찾을 수있을 때까지 그 용어를 무시할 수 있도록 다시 작성했다. 또한이 답변을 커뮤니티 위키로 변환했습니다. 학술 자료를 선호하십시오. 레퍼런스 목록:} {문학 : 5 }

요약

동적 프로그래밍은 중복 작업을 다시 계산하지 않도록 계산 순서를 정하는 것입니다. 주요 문제 (하위 문제 트리의 루트)와 하위 문제 (하위 트리)가 있습니다. 하위 문제는 일반적으로 반복되고 겹칩니다 .

예를 들어, 좋아하는 Fibonnaci의 예를 고려하십시오. 순진한 재귀 호출을 한 경우 이것은 하위 문제의 전체 트리입니다.

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(다른 드문 문제에서이 트리는 일부 분기에서 무한 종료되어 비 종료를 나타낼 수 있으므로 트리의 맨 아래가 무한대로 커질 수 있습니다. 또한 일부 문제에서는 전체 트리가 어떻게 보이는지 알 수 없습니다. 따라서 공개 할 하위 문제를 결정하기위한 전략 / 알고리즘이 필요할 수 있습니다.)

---

메모, 표

상호 배타적이지 않은 동적 프로그래밍에는 두 가지 주요 기술이 있습니다.

• 메모 화-이것은 laissez-faire 접근법입니다. 이미 모든 하위 문제를 계산했으며 최적의 평가 순서가 무엇인지 모릅니다. 일반적으로 루트에서 재귀 호출 (또는 반복되는 동등 항목)을 수행하고 최적의 평가 순서에 가까워 지거나 최적의 평가 순서에 도달하는 데 도움이된다는 증거를 얻습니다. 결과 를 캐시 하므로 재귀 호출이 하위 문제를 다시 계산하지 않도록 하여 중복 하위 트리가 다시 계산되지 않도록해야합니다.

  • 예 : 피보나치 수열을 계산하는 경우 fib(100)이를 fib(100)=fib(99)+fib(98)호출 fib(99)=fib(98)+fib(97)하면,, ... 등 ..., fib(2)=fib(1)+fib(0)=1+0=1. 그런 다음 마침내 해결 fib(3)=fib(2)+fib(1)되지만 fib(2)캐시했기 때문에 다시 계산할 필요가 없습니다 .
  • 이것은 트리의 맨 위에서 시작하여 잎 / 하위 트리의 하위 문제를 다시 루트로 평가합니다.

• 도표-동적 프로그래밍을 "표 작성"알고리즘으로 생각할 수도 있습니다 (일반적으로 다차원이지만이 '표'는 매우 드문 경우에 비 유클리드 기하학을 가질 수 있습니다). 이것은 메모 화와 비슷하지만 더욱 활성화 된 단계이며 추가 단계가 필요합니다. 계산을 수행 할 정확한 순서를 미리 선택해야합니다. 이것은 순서가 정적 인 것이 아니라 메모보다 훨씬 더 유연하다는 것을 의미하지는 않습니다.

  • 예를 들면 : 당신이 피보나치를 수행하는 경우,이 순서대로 숫자를 계산하도록 선택할 수 있습니다 : fib(2), fib(3), fib(4)... 더 쉽게 다음 사람을 계산할 수 있도록 모든 값을 캐싱. 또한 테이블을 채우는 것으로 생각할 수도 있습니다 (다른 형태의 캐싱).
  • 나는 개인적으로 '표'라는 단어를 많이 듣지 않지만 매우 괜찮은 용어입니다. 어떤 사람들은 이것을 "동적 프로그래밍"이라고 생각합니다.
  • 알고리즘을 실행하기 전에 프로그래머는 전체 트리를 고려한 다음 루트를 향한 특정 순서로 하위 문제를 평가하는 알고리즘을 작성합니다. 일반적으로 테이블을 채 웁니다.
  • * 각주 : 때때로 '테이블'은 그리드와 같은 연결성을 가진 직사각형 테이블이 아닙니다. 오히려 나무와 같은 더 복잡한 구조 또는 문제 영역에 특정한 구조 (예 :지도에서 비행 거리 내에있는 도시) 또는 격자 모양의 격자가없는 격자 다이어그램을 가질 수 있습니다. 예를 들어, user3290797 은 트리에서 최대 독립 세트 를 찾는 동적 프로그래밍 예제를 연결했습니다 . 이는 트리에서 공백을 채우는 것에 해당합니다.

그것은 "동적 프로그래밍"패러다임에서, 가장 일반적인의에서 (나는 프로그래머가 전체 트리를 고려 말할 것이다 다음원하는 모든 속성 (일반적으로 시간 복잡성 및 공간 복잡성 조합)을 최적화 할 수있는 하위 문제 평가 전략을 구현하는 알고리즘을 작성합니다. 전략은 특정 하위 문제와 함께 어딘가에서 시작해야하며 해당 평가 결과에 따라 자체적으로 적용될 수 있습니다. "동적 프로그래밍"의 일반적인 의미에서 이러한 하위 문제를 캐시하려고 시도 할 수 있으며,보다 일반적으로 다양한 데이터 구조의 그래프와 같이 미묘한 차이로 하위 문제를 다시 방문하지 않도록하십시오. 종종 이러한 데이터 구조는 배열이나 테이블과 같은 핵심 요소입니다. 더 이상 필요하지 않은 하위 문제에 대한 솔루션을 버릴 수 있습니다.)

[이전에,이 답변은 하향식 용어와 상향식 용어에 대한 진술을했다; 메모와 표라고하는 두 가지 주요 접근 방식이 있습니다 (모두는 아니지만). 대부분의 사람들이 사용하는 일반적인 용어는 여전히 "동적 프로그래밍"이며 일부 사람들은 "동적 프로그래밍"의 특정 하위 유형을 지칭하기 위해 "Memoization"이라고 말합니다. 이 답변은 커뮤니티가 학술 논문에서 적절한 참조를 찾을 때까지 하향식과 상향식 중 어느 것을 말하는지는 거부합니다. 궁극적으로 용어보다는 구별을 이해하는 것이 중요합니다.]

---

장점과 단점

코딩의 용이성

Memoization은 코딩이 매우 쉽고 (일반적으로 * 자동으로이를 수행하는 "memoizer"주석 또는 래퍼 함수를 ​​작성할 수 있음) 첫 번째 접근 방식이되어야합니다. 표의 단점은 주문을해야한다는 것입니다.

누군가가 이미 컴파일 쓴 경우, 예를 들어 ... 함수를 직접 작성, 및 / 또는 불순한 / 비 기능 프로그래밍 언어로 코딩하는 경우 * (이것은 단지 쉽게 실제로 fib기능을 반드시 자체에 대한 재귀 호출을하고, 재귀 호출이 새로운 메모 함수를 호출하는지 확인하지 않고 함수를 마술로 메모 할 수는 없습니다 (원래의 메모되지 않은 함수는 아님).

재귀

하향식과 상향식은 모두 자연스럽지 않지만 재귀 또는 반복 테이블 채우기로 구현할 수 있습니다.

실제적인 관심사

메모를 사용하면 트리가 매우 깊을 경우 (예 :) fib(10^6)지연된 각 계산을 스택에 배치해야하고 스택 중 10 ^ 6을 갖기 때문에 스택 공간이 부족합니다.

최적

하위 문제를 방문하거나 방문하려는 순서가 최적이 아닌 경우 특히 하위 문제를 계산하는 방법이 두 가지 이상인 경우 (일반적으로 캐싱이 문제를 해결할 수 있지만 이론적으로는 캐싱이 가능할 수 있습니다) 이국적인 경우는 아닙니다). Memoization은 일반적으로 시간 복잡성을 공간 복잡성에 추가합니다 (예 : Fib로 테이블을 사용하면 O (1) 공간을 사용할 수 있지만 Fib를 사용한 메모는 O (N)을 사용하는 것처럼 계산을 버릴 수있는 자유가 더 많습니다. 스택 공간).

고급 최적화

또한 매우 복잡한 문제를 겪고 있다면 표를 작성하는 것 외에는 선택의 여지가 없을 수도 있습니다 (또는 메모를 원하는 곳에서 조정하는 데 더 적극적인 역할을 수행해야 함). 또한 최적화가 절대적으로 중요하고 최적화해야하는 상황에있는 경우 표를 사용하면 메모를 통해 제정신이되지 않는 최적화를 수행 할 수 있습니다. 겸손한 의견으로는 일반적인 소프트웨어 엔지니어링에서는이 두 경우 중 어느 것도 나오지 않기 때문에 (스택 공간과 같은) 무언가가 테이블을 만들 필요가 없다면 메모 ( "답을 캐시하는 기능")를 사용하는 것입니다. 기술적으로 스택 분출을 피하기 위해 1) 스택 크기 제한을 허용하는 언어로 스택 크기 제한을 늘리거나 2) 스택을 가상화하기 위해 지속적인 추가 작업을 수행 할 수 있습니다 (ick).

---

더 복잡한 예

여기에서는 일반적인 DP 문제 일뿐만 아니라 메모와 표를 흥미롭게 구분하는 특별한 관심사를 보여줍니다. 예를 들어, 한 공식이 다른 공식보다 훨씬 쉬워 지거나 기본적으로 테이블이 필요한 최적화가있을 수 있습니다.

• 편집 거리를 계산하는 알고리즘 [ 4 ], 2 차원 테이블 채우기 알고리즘의 사소한 예로서 흥미로운

---

하향식 DP와 상향식 DP는 동일한 문제를 해결하는 두 가지 방법입니다. 피보나치 수 계산에 대한 메모 화 된 (위에서 아래로) vs 동적 (아래에서 위로) 프로그래밍 솔루션을 고려하십시오.

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

개인적으로 메모가 훨씬 더 자연 스럽습니다. 재귀 함수를 사용하고 기계적인 프로세스로 캐시 할 수 있습니다 (캐시에서 먼저 조회 응답을 반환하고 가능하면 반환하십시오. 그렇지 않으면 재귀 적으로 계산 한 다음 반환하기 전에 나중에 사용할 수 있도록 캐시에 계산을 저장하십시오). 동적 프로그래밍을 위해서는 솔루션이 계산되는 순서를 인코딩해야합니다. 따라서 작은 문제가 발생하기 전에 "큰 문제"가 계산되지 않습니다.

---

동적 프로그래밍의 주요 특징은 중복되는 하위 문제가 있다는 것 입니다. 즉, 해결하려는 문제가 하위 문제로 분류 될 수 있으며 이러한 하위 문제 중 많은 부분이 하위 하위 문제를 공유합니다. 그것은 "분열과 정복"과 같지만 여러 번 같은 일을하게됩니다. 2003 년부터 이러한 문제를 가르치거나 설명 할 때 사용한 예 : 피보나치 수를 재귀 적으로 계산할 수 있습니다 .

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Use your favorite language and try running it for fib(50). It will take a very, very long time. Roughly as much time as fib(50) itself! However, a lot of unnecessary work is being done. fib(50) will call fib(49) and fib(48), but then both of those will end up calling fib(47), even though the value is the same. In fact, fib(47) will be computed three times: by a direct call from fib(49), by a direct call from fib(48), and also by a direct call from another fib(48), the one that was spawned by the computation of fib(49)... So you see, we have overlapping subproblems.

Great news: there is no need to compute the same value many times. Once you compute it once, cache the result, and the next time use the cached value! This is the essence of dynamic programming. You can call it "top-down", "memoization", or whatever else you want. This approach is very intuitive and very easy to implement. Just write a recursive solution first, test it on small tests, add memoization (caching of already computed values), and --- bingo! --- you are done.

Usually you can also write an equivalent iterative program that works from the bottom up, without recursion. In this case this would be the more natural approach: loop from 1 to 50 computing all the Fibonacci numbers as you go.

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

In any interesting scenario the bottom-up solution is usually more difficult to understand. However, once you do understand it, usually you'd get a much clearer big picture of how the algorithm works. In practice, when solving nontrivial problems, I recommend first writing the top-down approach and testing it on small examples. Then write the bottom-up solution and compare the two to make sure you are getting the same thing. Ideally, compare the two solutions automatically. Write a small routine that would generate lots of tests, ideally -- all small tests up to certain size --- and validate that both solutions give the same result. After that use the bottom-up solution in production, but keep the top-bottom code, commented out. This will make it easier for other developers to understand what it is that you are doing: bottom-up code can be quite incomprehensible, even you wrote it and even if you know exactly what you are doing.

In many applications the bottom-up approach is slightly faster because of the overhead of recursive calls. Stack overflow can also be an issue in certain problems, and note that this can very much depend on the input data. In some cases you may not be able to write a test causing a stack overflow if you don't understand dynamic programming well enough, but some day this may still happen.

Now, there are problems where the top-down approach is the only feasible solution because the problem space is so big that it is not possible to solve all subproblems. However, the "caching" still works in reasonable time because your input only needs a fraction of the subproblems to be solved --- but it is too tricky to explicitly define, which subproblems you need to solve, and hence to write a bottom-up solution. On the other hand, there are situations when you know you will need to solve all subproblems. In this case go on and use bottom-up.

I would personally use top-bottom for Paragraph optimization a.k.a the Word wrap optimization problem (look up the Knuth-Plass line-breaking algorithms; at least TeX uses it, and some software by Adobe Systems uses a similar approach). I would use bottom-up for the Fast Fourier Transform.

---

Lets take fibonacci series as an example

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

Another way to put it,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

In case of first five fibonacci number

Bottom(first) number :1
Top (fifth) number: 5 

Now lets take a look of recursive Fibonacci series algorithm as an example

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Now if we execute this program with following commands

rcursive(5);

if we closely look into the algorithm, in-order to generate fifth number it requires 3rd and 4th numbers. So my recursion actually start from top(5) and then goes all the way to bottom/lower numbers. This approach is actually top-down approach.

To avoid doing same calculation multiple times we use Dynamic Programming techniques. We store previously computed value and reuse it. This technique is called memoization. There are more to Dynamic programming other then memoization which is not needed to discuss current problem.

Top-Down

Lets rewrite our original algorithm and add memoized techniques.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

And we execute this method like following

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

This solution is still top-down as algorithm start from top value and go to bottom each step to get our top value.

Bottom-Up

But, question is, can we start from bottom, like from first fibonacci number then walk our way to up. Lets rewrite it using this techniques,

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

Now if we look into this algorithm it actually start from lower values then go to top. If i need 5th fibonacci number i am actually calculating 1st, then second then third all the way to up 5th number. This techniques actually called bottom-up techniques.

Last two, algorithms full-fill dynamic programming requirements. But one is top-down and another one is bottom-up. Both algorithm has similar space and time complexity.

---

Dynamic Programming is often called Memoization!

1.Memoization is the top-down technique(start solving the given problem by breaking it down) and dynamic programming is a bottom-up technique(start solving from the trivial sub-problem, up towards the given problem)

2.DP finds the solution by starting from the base case(s) and works its way upwards. DP solves all the sub-problems, because it does it bottom-up

Unlike Memoization, which solves only the needed sub-problems

1. DP has the potential to transform exponential-time brute-force solutions into polynomial-time algorithms.

2. DP may be much more efficient because its iterative

On the contrary, Memoization must pay for the (often significant) overhead due to recursion.

To be more simple, Memoization uses the top-down approach to solve the problem i.e. it begin with core(main) problem then breaks it into sub-problems and solve these sub-problems similarly. In this approach same sub-problem can occur multiple times and consume more CPU cycle, hence increase the time complexity. Whereas in Dynamic programming same sub-problem will not be solved multiple times but the prior result will be used to optimize the solution.

---

Simply saying top down approach uses recursion for calling Sub problems again and again
where as bottom up approach use the single without calling any one and hence it is more efficient.

---

Following is the DP based solution for Edit Distance problem which is top down. I hope it will also help in understanding the world of Dynamic Programming:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

You can think of its recursive implementation at your home. It's quite good and challenging if you haven't solved something like this before.

참고URL : https://stackoverflow.com/questions/6164629/what-is-the-difference-between-bottom-up-and-top-down