какой алгоритм я должен использовать рядом, чтобы выяснить, является ли ответ динамического программирования на проблему оптимальным ответом или нет? Вы могли бы предложить несколько бумаг, чтобы помочь мне узнать это?Как определить, является ли ответ динамического программирования оптимальным или нет?
Метод динамического программирования к проблеме, как правило, получает правильный ответ - т. Е. Находит истинный ответ на минимальные затраты - но обычно не гарантируется способ решения проблемы, которая использует минимальное количество процессора или памяти.
Существует много случаев, когда мы не знаем, использует ли наш метод решения проблемы минимально возможное количество процессора. Одним из примеров является то, что динамическая программа является одним из наиболее эффективных методов, но не является наиболее эффективным возможным способом: http://en.wikipedia.org/wiki/Knapsack_problem.
Не существует алгоритма, который говорит вам, является ли данное решение динамического программирования оптимальным.
См. Halting Problem для исследования по близкому вопросу.
Мне кажется, что сам вопрос испорчен. Неправильно ли, что если проблему можно сформулировать как проблему динамического программирования, то решение динамического программирования будет оптимальным? Единственная проблема, которую я вижу, - это проблема проблемы, которая является проблемой DP, но, возможно, не может быть решена, потому что она не заканчивается (возможно, это то, что вы имели в виду с проблемой остановки). – Mathias
Если по вашему вопросу вы имеете в виду: «Как узнать, правильно ли реализовано мое динамическое программирование?» Вы можете решить эту проблему также путем обратного отслеживания, которое просто реализовать и всегда дает лучшее решение. Вы можете попробовать как обратное отслеживание, так и динамическое программирование для одних и тех же небольших входов данных, и если выходы идентичны, то вы можете сильно подозревать, что реализация динамического программирования верна. В противном случае динамическое программирование всегда дает оптимальный ответ, но не все проблемы решаются DP, и, конечно, не все DP-прогремы могут быть решены с использованием того же состояния и/или повторения.
Думаю, вам сначала нужно определить проблему и «оптимальную». –
Можете ли вы привести пример, где вы подозреваете, что динамическое программирование даст вам неоптимальный ответ? Я не совсем понимаю ваш вопрос, потому что по определению я считаю, что если ваша проблема может быть сформулирована как динамическое программирование, то динамическое программирование даст вам оптимальный ответ (если вы его можете вычислить). – Mathias