동적 프로그래밍이란 무엇입니까?

컴퓨터 과학 분야를 언급 할 때 동적 프로그래밍은 문제를 더 작은 문제로 세분화하여 복잡한 문제를 해결하기위한 유사한 컴퓨터 알고리즘 그룹을 설명합니다. 1950 년대에 Richard Bellman이 처음으로 만든 동적 프로그래밍은 하위 문제가 겹치거나 하위 구조가 최적 인 문제를 해결합니다. 동적 프로그래밍의 작동 방식을 이해하려면이 두 용어의 개념을 이해하는 것이 가장 좋습니다.

겹치는 하위 문제는 더 작은 방정식 세트로 분류 될 때 더 작은 방정식의 일부를 두 번 이상 재사용하여 답에 도달하는 복잡한 방정식을 설명합니다. 예를 들어, 일련의 숫자를 사용하여 가능한 모든 결과를 계산하도록 지시 된 수학적 방정식은 한 번만 다른 결과를 계산하는 동안 동일한 결과를 여러 번 계산할 수 있습니다. 동적 프로그래밍은 결과를 처음 계산 한 후에는 결과를 저장하고 나중에 다시 계산하는 대신 답을 방정식에 연결해야한다는이 문제를 알려줍니다. 길고 복잡한 프로세스와 방정식을 다룰 때 시간을 절약하고 훨씬 적은 단계로 더 빠른 솔루션을 만들 수 있습니다.

최적의 하위 구조는 모든 하위 문제에 대한 최상의 답변을 찾은 다음 최상의 전체 답변을 만들어 솔루션을 만듭니다. 복잡한 문제를 더 작은 문제로 나눈 후 컴퓨터는 수학 시스템을 사용하여 각 문제에 가장 적합한 답을 결정합니다. 작은 답변에서 원래 문제에 대한 답변을 계산합니다. 이 프로세스에는 결함이 있습니다. 수학적으로 가장 잘 작동하는 솔루션을 제공하지만 문제의 유형과 실제 환경과의 관계에 따라 실제 생활에서 최상의 솔루션 일 수도 있고 아닐 수도 있습니다.

이러한 작업 중 동적 프로그래밍 알고리즘은 솔루션의 최단 경로를 찾습니다. 이를 위해 두 가지 접근 방법 중 하나가 필요할 수 있습니다. 하향식 접근법은 방정식을 더 작은 방정식으로 나누고 필요한 경우 이러한 방정식에 대한 답을 재사용합니다. 상향식 접근 방식은 방정식을 세분화 한 후 가장 작은 수학적 값을 풀려고 시도한 다음 가장 큰 수학적 값을 계산합니다. 두 방법 모두 시간을 절약 할 수 있지만 동적 프로그래밍은 원래 문제가 더 작은 방정식으로 분해되어 어떤 시점에서 방정식을 풀기 위해 재사용되는 경우에만 작동합니다.