일반적인 동적 프로그래밍 문제의 공식화

StackOverflow https://stackoverflow.com/questions/2255627

  •  20-09-2019
  •  | 
  •  

문제

일반적인 동적 프로그래밍 문제의 객관적인 기능이 항상 위키에 대한 동적 프로그래밍, 목표 함수가 모든 단계에서 행동과 상태를위한 항목의 합계는 어디입니까? 아니면 그것은 단지 구체적인 사례이며 일반적인 공식은 무엇입니까?

편집하다:

"Dynamic Programming Problem"이라는 것은 동적 프로그래밍 기술로 해결할 수있는 문제를 의미합니다. 이러한 종류의 문제는 재산을 가지고 있습니다 최적의 문제와 최적의 구조.

그러나 나에게 임대 할 때 때때로 그러한 문제를 식별하는 것은 쉽지 않습니다. 아마도 그런 종류의 언어 적 설명에 익숙해지지 않았기 때문일 것입니다. Bellman 방정식의 위키 페이지를 발견했을 때 비용 기능의 수학적 공식화가 어떻게 든 도움이 될 것이라고 생각합니다. 전체 비용/이득 기능은 항상 모든 단계에서 비용/이득의 축적으로 표시 될 수 있다고 생각합니까? 그리고 축적은 부가가치 또는 다수 일 수 있습니까?

내 질문을 게시했을 때, 나는 수학적 최적화에 더 지향되는 어떤 곳에서 동적 프로그래밍을 논의하는 것이 더 적절하다는 것을 깨달았습니다. 그러나 stackoverflow.com에는 컴퓨터 알고리즘에 대해 많은 논의가 있습니다. 그래서 나는 여기서 내 질문을하기에는 부적절하다고 느끼지 않았습니다.

도움이 되었습니까?

해결책

그것은 임의의 최적화 문제 (또는 동적 프로그래밍 알고리즘)를 특성화하는 방법이 아닙니다. 특히, 인자 β티 프로그래머가 일반적으로 원하지 않는 전기 공학 해킹처럼 보입니다. 더 미묘하게, 그것은 항상 기능이 무엇인지 분명하지 않은 것 같습니다. 에프 주어진 문제입니다.

그러나 예, β를 1으로 설정하고 임의의 목적 기능을 설정하십시오. ~할 수 있다 그런 식으로 공식화하십시오. 일반적으로 목적 함수는 초기 상태의 함수 및 취한 모든 조치 일 수 있습니다. 이러한 함수가 주어지면 기능을 정의하기 쉽습니다. 에프 그 공식에 연결합니다.

그것이 유용한 일인지 문제에 달려 있는지 여부는 생각합니다.

다른 팁

컴퓨터 과학에서 동적 프로그래밍 이 재귀적인 확장에서 동일한 하위 문제가 여러 번 나타날 때 재귀 적으로 하위 문제로 분할하는 관점에서 알고리즘의 건물을 나타냅니다. 간단한 책 예제, Fibonacci 번호는 동적 프로그래밍을 사용하여 계산할 수 있습니다.

일반 재발 F (N) = F (N-1) + F (N-2)에서 다음 알고리즘을 구현할 수 있습니다.

int fibonacci(n):
  if (n < 2): return 1
  else: return fibonacci(n-1) + fibonacci(n-2)

이제 이것은 물론 전혀 효율적이지 않습니다. 수많은 재귀 호출을 생성하기 때문입니다.

F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ...

따라서 여기서 우리는 이미 Fibonacci (5)가 구현에 의해 두 번 계산된다는 것을 알았습니다. 그만큼 동적 프로그래밍 패러다임은 이제 다음과 같은 결과를 "메모 화"또는 "캐시"해야합니다.

integer_map store;
int memofibo(n):
  if (n < 2) : return 1
  else if (store.find_key(n)): return store.find_value(n)
  else:
    int f = memofibo(n-1) + memofibo(n-2)
    store.set(n, f)
    return f

이 구현은 N의 모든 인수 값에 대해 재귀 단계가 최대 한 번에 실행되도록 보장하므로 O (n log n) 시간 (표준 O (log n)) 구현의 NTH Fibonacci 번호를 Acciative Array 'Store의 구현을 계산합니다. '.

따라서 컴퓨터 과학 관점에서 제공 한 링크는 동일한 아이디어 (문제를 하위 문제로 나누기)의 운영 연구 / 최적화 문제 버전이지만,이 아이디어는 일반 컴퓨터 영역 에서이 재귀 + 메모 화 패턴에 대해 실제로 추상화되었습니다. 과학. 이것이 구름의 일부를 청소하는 데 도움이되기를 바랍니다.

사람들,

운영 연구 질문에 중점을 둔 새로운 (ISH) 웹 사이트가 있습니다. 여기 그러나 적은 양의 트래픽은 당신에게 좋은 답변을 매우 빨리 얻지 못할 수 있습니다.

비누 상자 시간 :

스택 오버 플로우에 적합한 것에 대해 토론하려는 사람들의 경우 알고리즘은 해당 분야의 일부로 주장하는 사람에 관계없이 알고리즘입니다. Djikstra의 방법, Branch and Bound, Lagrangian 휴식은 특정 유형의 문제를 해결하는 모든 알고리즘 또는 방법입니다. 이들 중 다수는 두 분야 모두에서 가르치고 적용되므로 OR과 CS 사이의 경계는이 영역에서 꽤 흐릿합니다.

예를 들어 MIT의 알고리즘의 학부 과정에는 다음과 같은 모든 무작위 경쟁 알고리즘, 동적 프로그래밍, 욕심 많은 알고리즘, 최소 스패닝 트리, DijkStra의 알고리즘, Bellman -Ford, 선형 프로그래밍 , 깊이 우선 검색, 토폴로지 정렬 및 다른 주제 중 가장 짧은 경로. 이 경우 MIT를 연기하겠습니다.

많은 프로그래머가 발생할 때 최적화 문제를 인식하기 때문에 스택 오버플로를 좋아하지만 종종 문제를 공식화하는 방법이나 이름으로 문제가있는 것을 결정하는 데 약간의 도움이 필요합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top