algorithm - 프로그래밍 - 최적 부분 사각형




동적 프로그래밍 및 메모:상향식 및 하향식 방식 (5)

rev4 : 사용자 Sammaron이 매우 웅변 적으로 말한 것은 아마도이 해답이 이전에 하향식과 상향식을 혼란스럽게 만들었다는 점이었습니다. 원래이 답변 (rev3)과 다른 답변은 "상향식 (bottom-up)은 메모 (memoization)"( "하위 문제 가정")이라고 말하면서 반대가 될 수 있습니다 (즉, "하향식" 상향식 "은"하위 문제 작성 "일 수 있음). 이전에는 동적 프로그래밍의 하위 유형과는 다른 종류의 동적 프로그래밍 인 메모 작성에 대해 읽었습니다. 나는 그것을 구독하지 않고도 그 견해를 인용하고있었습니다. 나는이 문헌에 대한 적절한 언급이 문헌에서 발견 될 때까지 용어에 대해 불가지론자인이 대답을 다시 썼다. 또한이 답변을 커뮤니티 위키로 변환했습니다. 학술 자료를 선호하십시오. 참고 문헌 목록 : {Web : 1 , 2 } {Literature : 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

(다른 드문 문제 중 일부는이 트리가 무한대로 끝나지 않을 수도 있기 때문에 트리의 바닥이 무한히 커질 수 있습니다. 또한 일부 문제에서는 풀 트리가 어떻게 보이는지 모를 수도 있습니다. 따라서 공개 할 하위 문제를 결정하기위한 전략 / 알고리즘이 필요할 수 있습니다.

Memoization, Tabulation

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

  • Memoization - 이것은 방탕 한 접근 방식입니다. 이미 모든 하위 문제를 계산했으며 최적의 평가 순서가 무엇인지 알 수 없다고 가정합니다. 일반적으로 루트에서 재귀 호출 (또는 반복적으로 제공되는 일부분)을 수행하고 최적의 평가 순서에 가까워 지길 바라거나 최적의 평가 순서에 도달하는 데 도움이된다는 증거를 얻습니다. 재귀 호출은 결과를 캐시 하기 때문에 하위 문제를 다시 계산하지 않으므로 중복 된 하위 트리는 다시 계산되지 않습니다.

    • 예 : 피보나치 시퀀스 fib(100) 계산하는 경우, 이것을 호출하면 fib(100)=fib(99)+fib(98) 호출하는 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) 를 다시 계산할 필요가 없습니다. 왜냐하면 우리가 캐시했기 때문입니다.
    • 이것은 트리의 맨 위에서 시작하여 잎 / 하위 트리의 하위 문제를 루트쪽으로 다시 평가합니다.
  • 도표화 - 동적 프로그래밍을 "테이블 채우기"알고리즘으로 생각할 수도 있습니다 (대개 다차원이지만이 테이블은 매우 드문 경우 *에는 유클리드가 아닌 구조를 가질 수 있습니다). 이는 메모와 비슷하지만보다 적극적이며 추가 단계가 필요합니다. 사전에 계산을 수행 할 정확한 순서를 선택해야합니다. 이것은 주문이 정적이어야 함을 의미하지는 않으며, 메모 작성보다 유연성이 훨씬 뛰어납니다.

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

(가장 일반적으로 "동적 프로그래밍"패러다임에서 프로그래머가 전체 트리를 고려한 다음 원하는 속성을 최적화 할 수있는 하위 문제를 평가하기위한 전략을 구현하는 알고리즘 작성한다고합니다. 일반적으로 시간 복잡성 공간 - 복잡성) 당신의 전략은 특정 하위 문제로 어딘가에서 시작해야하며, 아마도 그러한 평가의 결과에 따라 스스로 적응할 수 있습니다. "동적 프로그래밍"의 일반적인 의미에서 이러한 하위 문제 등을 캐시하려고 할 수 있습니다. 일반적으로 다양한 데이터 구조에서 그래프의 경우와 같이 미묘한 차이로 하위 문제를 다시 생각하는 것을 피하십시오. 매우 자주 이러한 데이터 구조가 배열이나 테이블처럼 핵심에 있습니다. 필요하지 않으면 하위 문제에 대한 솔루션을 버릴 수 있습니다 더 이상.)

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

장점과 단점

코딩의 용이성

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

* (실제로 이것은 함수를 직접 작성하거나 불순한 / 비 기능적 프로그래밍 언어로 작성하는 경우에만 실제로 가능합니다 ... 예를 들어 누군가가 이미 미리 컴파일 된 fib 함수를 작성한 경우 필연적으로 자체 호출을 재귀 호출하고, 재귀 호출이 새로운 메모 기능을 호출하지 않고 마술처럼 메모를 할 수는 없습니다 (원래의 unmemoized 함수가 아니라).

재귀

하향식과 상향식 모두 재귀 또는 반복적 인 테이블 채우기로 구현할 수 있지만 자연이 아닐 수도 있습니다.

실질적인 관심사

memoization을 사용하면 tree가 매우 깊다면 (예 : fib(10^6) ) 스택 공간이 부족합니다. 지연 계산은 스택에 저장해야하기 때문에 10 ^ 6이됩니다.

최적 성

두 가지 방법 모두 하위 문제를 계산할 수있는 경우 (특히 캐싱을 통해 문제를 해결할 수 있지만 이론적으로는 캐싱이 문제가 될 수 있음) 하위 문제를 방문한 순서 (또는 시도하려는 순서)가 최적이 아닌 경우 몇몇 이국적인 경우에는 아닙니다). Memoization은 보통 공간 복잡성에 시간 복잡성을 추가합니다 (예 : Fib로 표를 사용하면 O (1) 공간을 사용할 수 있지만 Fib로 메모를하면 O (N)을 사용함) 스택 공간).

고급 최적화

매우 복잡한 문제를 겪고있는 경우 표를 작성하는 것 외에 다른 방법으로 선택할 수도 있습니다 (또는 최소한 메모 작성을 진행할 때 더 적극적인 역할을 수행해야합니다). 또한 최적화가 절대적으로 중요하며 최적화해야하는 상황에있는 경우 표를 사용하면 메모 작성을 통해 정상적으로 수행 할 수없는 최적화를 수행 할 수 있습니다. 겸손한 견해로, 일반적인 소프트웨어 공학에서,이 두 경우 중 어느 것도 나타나지 않습니다. 그래서 뭔가 (스택 공간과 같은) 테이블을 필요로하지 않는 한 memoization ( "답변을 캐시하는 함수")을 사용합니다 ... 기술적으로 스택 파열을 피하기 위해 1) 허용 가능한 언어로 스택 크기 제한을 늘리거나 2) 스택 (ick)을 가상화하기위한 추가 작업의 일정한 요소를 먹거나 3) 연속 통과 스타일의 프로그램을 사용할 수 있습니다. 사실상 스택을 가상화합니다. 그러나 이것의 복잡성은 확실하지 않지만, 기본적으로 N 크기의 스택에서 연기 된 호출 체인을 가져 와서 연속적으로 중첩 된 N 개의 썽크 함수로 고정시킵니다. 일부 언어에서는 테일 콜 (tail-call) 최적화가 없으면 스택 파열을 피하기 위해 물건을 트램폴린해야 할 수도 있습니다.

더 복잡한 예제

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

  • 편집 거리를 계산하는 알고리즘 [ 4 ], 2 차원 테이블 채우기 알고리즘의 중요하지 않은 예로 흥미로운

나는 memoization과 bottom-up 방법을 올바르게 사용하여 접근법을 올바르게 이해하고 있는지 잘 모르겠습니다.

Bottom up : 먼저 "더 작은"하위 문제를 살펴본 다음 더 작은 문제에 대한 해결책을 사용하여 더 큰 하위 문제를 해결합니다.

위에서 아래로 : 문제를 자연스럽게 해결하고 이전에 하위 문제에 대한 해결책을 계산했는지 확인하십시오.

나는 조금 혼란 스럽다. 누군가 그것을 설명 할 수 있습니까? 그 차이점은 무엇입니까?


간단히 말하자면 위로 가기 접근법은 반복적으로 Sub 문제를 호출하는 재귀를 사용합니다.
어디 까지나 상향식 접근법은 하나를 호출하지 않고 단일을 사용하므로 더 효율적입니다.


동적 프로그래밍은 종종 Memoization이라고 불립니다!

1.Memoization은 하향식 기술 (주어진 문제를 분해하여 시작하기 시작)이며 동적 프로그래밍은 상향식 기술입니다 (사소한 하위 문제에서부터 주어진 문제를 해결하기 시작)

2.DP는 기본 케이스에서 시작하여 솔루션을 찾고 그 방법을 위쪽으로 작동합니다. DP는 상향식으로하기 때문에 모든 하위 문제를 해결합니다.

Memoization과 달리 필요한 하위 문제 만 해결합니다.

  1. DP는 지수 함수의 brute-force 해를 다항식 시간 알고리즘으로 변환 할 수 있습니다.

  2. DP는 훨씬 더 효율적일 수 있습니다.

반대로 Memoization은 재귀 때문에 (종종 중요한) 오버 헤드를 지불해야합니다.

보다 간단하게하기 위해 Memoization은 문제를 해결하기 위해 하향식 접근법을 사용합니다. 즉, 핵심 (주) 문제로 시작하여 하위 문제로 분해하고 마찬가지로 이러한 하위 문제를 해결합니다. 이 접근법에서는 동일한 하위 문제가 여러 번 발생할 수 있으며 더 많은 CPU 사이클을 소비하므로 시간 복잡성이 증가합니다. 동적 프로그래밍에서 동일한 하위 문제는 여러 번 해결되지 않지만 이전 결과는 솔루션을 최적화하는 데 사용됩니다.


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

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

좋아하는 언어를 사용하여 fib(50) 를 실행 해보십시오. 매우 오랜 시간이 걸릴 것입니다. 대략 fib(50) 만큼 시간이 걸립니다! 그러나 많은 불필요한 작업이 진행되고 있습니다. fib(50)fib(49)fib(48) 를 호출하지만 그 값이 같더라도 둘 다 fib(47) 호출하게됩니다. 실제로 fib(47)fib(49) 의 직접 호출, fib(48) 의 직접 호출, 다른 fib(48) 의 직접 호출에 의해 세 번 계산됩니다. fib(49) 의 계산에 의해 산란됩니다 ... 그래서 우리는 중복되는 부분 문제 가 있음을 알 수 있습니다.

좋은 소식 : 동일한 값을 여러 번 계산할 필요가 없습니다. 한 번 계산하면 결과를 캐시하고 다음에 캐시 된 값을 사용하십시오! 이것은 동적 프로그래밍의 핵심입니다. "하향식", "메모 작성"또는 원하는 모든 것을 호출 할 수 있습니다. 이 방법은 매우 직관적이며 구현하기가 쉽습니다. 재귀 적 솔루션을 먼저 작성하고, 작은 테스트에서 테스트하고, 메모 (캐시 된 값을 캐싱)를 추가하고, - 빙고! --- 끝났어.

대개 재귀없이 아래에서 위로 작동하는 상응하는 반복 프로그램을 작성할 수도 있습니다. 이 경우보다 자연스러운 접근 방법이 될 것입니다 : 1에서 50까지 피보나치 수를 계산하여 반복하십시오.

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

흥미로운 시나리오에서 상향식 솔루션은 일반적으로 이해하기가 더 어렵습니다. 그러나 일단 알고리즘을 이해하면 일반적으로 알고리즘 작동 방식에 대한 훨씬 더 명확한 그림을 얻을 수 있습니다. 실제로 중요한 문제를 해결할 때는 먼저 하향식 접근 방식을 작성하고 작은 예제로 테스트하는 것이 좋습니다. 그런 다음 상향식 솔루션을 작성하고 두 가지를 비교하여 동일한 것을 얻고 있는지 확인하십시오. 이상적으로 두 솔루션을 자동으로 비교하십시오. 테스트를 많이 생성 할 수있는 작은 루틴을 작성하십시오. 이상적으로는 모든 작은 테스트가 특정 크기까지 가능합니다. 두 솔루션 모두 동일한 결과를 제공하는지 확인하십시오. 그 다음에 생산에서 상향식 솔루션을 사용하지만 맨 아래 코드는 그대로 두십시오. 이렇게하면 다른 개발자가 자신이 무엇을하고 있는지 쉽게 이해할 수 있습니다. 상향식 코드는 이해하기 어려울 수 있습니다. 작성한 경우에도 정확히 무엇을하고 있는지 알 수 있습니다.

많은 애플리케이션에서 재귀 호출의 오버 헤드로 인해 상향식 접근법이 약간 더 빠릅니다. 스택 오버플로는 특정 문제에서 문제가 될 수 있으며 입력 데이터에 크게 의존 할 수 있습니다. 경우에 따라 동적 프로그래밍을 충분히 이해하지 못하면 스택 오버플로를 일으키는 테스트를 작성할 수 없지만 언젠가는 여전히 발생할 수 있습니다.

문제 공간이 너무 커서 모든 하위 문제를 해결할 수 없기 때문에 하향식 접근이 유일한 실현 가능한 솔루션 인 문제가 있습니다. 그러나 "캐싱"은 여전히 ​​합리적인 시간에 효과가 있습니다. 입력 한 부분 문제 만 해결해야하기 때문입니다. 그러나 명시 적으로 정의하고 하위 문제를 해결해야하므로 하위 항목을 작성하기가 너무 까다 롭습니다. 최대 솔루션입니다. 반면에 모든 하위 문제를 해결해야 할 상황이 있습니다. 이 경우 계속해서 상향식으로 사용하십시오.

개인적으로 단락 최적화 ( 워드 랩 최적화 알고리즘을 찾아보십시오. 적어도 TeX이이를 사용하고 Adobe Systems의 일부 소프트웨어는 유사한 접근법을 사용합니다)라고하는 단락 최적화를 위해 개인적으로 맨 아래 바닥을 사용합니다. 나는 고속 푸리에 변환을 위해서 상향식을 사용할 것이다.


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

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)

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





memoization