동적 프로그래밍의 대답이 최적의 대답인지 아닌지 확인하는 방법은 무엇입니까?

-1

동적 프로그래밍의 문제에 대한 대답이 최적의 대답인지 아닌지 알아보기 위해 어떤 종류의 알고리즘을 사용해야합니까? 내가 알아낼 수있는 몇 가지 서류를 제안 해 주시겠습니까?동적 프로그래밍의 대답이 최적의 대답인지 아닌지 확인하는 방법은 무엇입니까?

출처

2012-01-28 ePezhman

먼저 문제를 정의하고 "최적"이라고 정의해야한다고 생각합니다. –

다이내믹 프로그래밍이 최적이 아닌 답변을 줄 수 있다고 생각하는 예를들 수 있습니까? 나는 당신의 문제가 동적 프로그래밍 언어로 기술 될 수 있다면, 동적 프로그래밍은 당신에게 최적의 대답을 줄 것이라고 믿는다. (당신이 계산할 수 있다면). – Mathias

문제에 대한 동적 프로그래밍 접근법은 일반적으로 정확한 대답을 얻습니다. 즉, 진정한 최소 비용 응답을 찾으십시오. 그러나 최소 CPU 또는 메모리 양을 사용하는 문제를 해결하는 방법으로는 일반적으로 보장되지 않습니다.

우리가 문제를 해결하는 방법이 가능한 최소 CPU 사용량을 사용하는지 알 수없는 경우가 많습니다. 동적 프로그램이 알려진보다 효율적인 방법 중 하나이지만 가능한 가장 효율적인 방법으로 입증되지 않은 한 가지 예가 http://en.wikipedia.org/wiki/Knapsack_problem입니다.

출처

2012-01-28 05:26:54 mcdowella

주어진 동적 프로그래밍 솔루션이 최적인지 여부를 알려주는 알고리즘은 없습니다.

밀접한 관련 질문에 대한 연구는 Halting Problem을 참조하십시오.

출처

2012-01-28 00:37:18

질문 자체에는 결함이있는 것 같습니다. 문제가 동적 프로그래밍 문제로 언급 될 수 있다면 동적 프로그래밍의 솔루션이 최적이 될 것이라는 점은 맞습니까? 내가 볼 수있는 유일한 문제는 DP 문제 인 문제의 경우이지만 문제가 종료되지 않았기 때문에 해결되지 않을 수 있습니다 (Halting Problem의 의미 일 수 있습니다). – Mathias

"동적 프로그래밍이 올바르게 구현되었는지 어떻게 알 수 있습니까?" 또한 구현하기 쉽고 항상 최상의 솔루션을 제공하는 백 트래킹을 통해 문제를 해결할 수 있습니다. 동일한 작은 데이터 입력에 대해 역 추적과 동적 프로그래밍을 모두 시도 할 수 있으며 출력이 동일한 경우 동적 프로그래밍 구현이 올바른지 의심 할 수 있습니다. 그렇지 않으면 동적 프로그래밍이 항상 최적의 답을 제공하지만 모든 문제가 DP에 의해 해결되는 것은 아니며 물론 모든 DP 프로그래밍이 동일한 상태 및/또는 재현을 사용하여 해결 될 수있는 것은 아닙니다.

출처

2012-01-28 08:16:37

동적 프로그래밍의 대답이 최적의 대답인지 아닌지 확인하는 방법은 무엇입니까?

답변

관련 문제