Какая интуиция дает оптимальную субструктуру?

Question

Этот вопрос связан с динамическим программированием и, в частности, с проблемой резки прутка из CLRS Pg 362.

Общее оптимальное решение включает в себя оптимальные решения для двух связанных подзадач.

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

Спасибо

Answer 1

Вы можете сравнить динамическое программирование и жадный подход.

Оптимальная подструктура означает, что оптимальное решение может быть найдено путем нахождения оптимальных решений подзадач. Если это не так, то сумма оптимального решения подзадач не дает нам оптимального глобального решения.

Например, рассмотрим алгоритм Дейкстры. Если мы знаем кратчайший путь от узла A к узлу C, мы можем использовать эту информацию, чтобы найти кратчайший путь и к другим узлам.

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