формулировка проблемы общего динамического программирования

Question

Интересно, можно ли сформулировать объективную функцию общей задачи динамического программирования, как в dynamic programming on wiki, где целевая функция представляет собой сумму элементов для действия и состояния на каждом этапе? Или это всего лишь конкретный случай и какова общая формулировка?

---

EDIT:

К «динамической задачи программирования», я имею в виду проблему, которая может быть решена с помощью метода динамического программирования. Такие проблемы имеют свойство optimal problem and optimal structure.

Но в аренду для меня иногда бывает непросто идентифицировать такие проблемы, возможно, потому, что я не привык к такого рода словесному описанию. Когда я натолкнулся на страницу WIKI для уравнения Беллмана, я чувствую, что математическая формулировка функции стоимости поможет как-то. Я подозреваю, что общая функция стоимости/коэффициента полезного действия всегда может быть представлена ​​как накопление затрат/прибыли со всех этапов? и накопление может быть аддитивным или мультипликативным или что-то еще?

Когда я опубликовал свой вопрос, я понял, что более удобно обсуждать динамическое программирование в некотором месте, более ориентированное на математическую оптимизацию. Но в Stackoverflow.com довольно много обсуждений компьютерных алгоритмов. Поэтому я тоже не счел нужным задавать свой вопрос.

Answer 1

Это не то, как я охарактеризовал бы произвольную проблему оптимизации (или алгоритм динамического программирования). В частности, фактор β ^t выглядит как ручка электротехники, которую обычно не хотели программисты. Более тонко, похоже, не всегда будет очевидно, что функция F предназначена для данной проблемы.

Но да, набор β к 1 и любая произвольная целевая функция могут быть сформулированы таким образом. Обычно целевой функцией может быть любая функция начального состояния и все предпринятые действия; При такой функции легко определить функцию, которая должна быть подключена в эту формулу F.

Я полагаю, что это полезная вещь, которую нужно делать или нет.

Answer 2

в информатике динамическое программирование обозначает построение любого алгоритма в терминах рекурсивного разбиения его на подзадачи, когда одни и те же подзадачи появляются много раз в этом рекурсивном расширении. Простой пример книги, числа Фибоначчи можно вычислить с помощью динамического программирования:

Из общего повторения F (п) = F (п-1) + F (п-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)] = ... 

Итак, мы уже видим, что фибоначчи (5) вычисляются дважды реализацией.динамического программирования парадигмы теперь «memoize» или «кэш» результаты, как это:

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)) реализацию ассоциативного массива 'store'.

Итак, с точки зрения компьютерной науки ссылка, которую вы предоставили, представляет собой проблему с исследованием/оптимизацией операций одной и той же идеи (деление проблемы на подзадачи), но эта идея была абстрагирована на практике с этим шаблоном рекурсии + memoization в область общей информатики. Надеюсь, это поможет очистить некоторые облака.

Answer 3

Folks,

Там новый веб-сайт (МОГ), которая концентрируется на исследования операций вопросы here но низкий объем трафика не может получить вам хороший ответ очень быстро.

время Soapbox:

Для тех, кто заботится дискутировать о том, что уместно для переполнения стека, отметим, что алгоритм является алгоритмом, независимо от того, кто утверждает, что его как часть своей области. Симплексный метод, метод Джикстры, ветвь и связанная лагранжева релаксация - это все алгоритмы или методы решения некоторых типов задач. Многие из них преподаются и применяются в обоих полях, поэтому граница между OR и CS довольно размыта в этой области.

Например, (как и очень сильный экземпляр), курс обучения в алгоритмах MIT включает в себя все следующие: рандомизированный конкурентный алгоритм, динамическое программирование, жадные алгоритмы, минимальные спаниевые деревья, кратчайшие пути, алгоритм Дейкстры, Bellman- Форд, линейное программирование, поиск по глубине, топологические сортировки и все парные кратчайшие пути среди других тем. В этом случае я отложу MIT.

Мне нравится переполнение стека, потому что многие программисты распознают проблему оптимизации, когда сталкиваются с ней, но часто им просто нужна небольшая помощь в решении, как сформулировать проблему или даже о том, что проблема вызывается по имени.