Как узнать, является ли ответ динамического программирования оптимальным или нет?

Question

Какой тип алгоритма мне следует использовать, чтобы узнать, является ли динамическое программирование ответом на проблему оптимальным или нет? Не могли бы вы предложить какие-то документы, чтобы помочь мне узнать это?

Answer 1

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

Во многих случаях мы не знаем, использует ли наш метод решения проблемы минимально возможное количество процессоров. Одним из примеров, когда динамическая программа является одним из наиболее эффективных методов, известных, но не доказано, что он является наиболее эффективным из возможных, является http://en.wikipedia.org/wiki/Knapsack_problem.

Answer 2

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

См. Проблема остановки для исследования тесно связанного вопроса.

Answer 3

Если под своим вопросом вы имеете в виду: «Как мне определить, правильно ли реализовано мое Динамическое программирование?» Вы можете решить эту проблему также путем возврата, который прост в реализации и всегда дает наилучшее решение. Вы можете попробовать откат и динамическое программирование для одних и тех же небольших входных данных, и если выходные данные идентичны, вы можете сильно подозревать, что реализация динамического программирования является правильной. В противном случае динамическое программирование всегда дает оптимальный ответ, но не все проблемы могут быть решены с помощью DP, и, конечно, не все программы DP могут быть решены с использованием одного и того же состояния и / или повторяемости.