Оптимальная подструктура

Question

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

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

Чтобы уточнить:

Определение оптимальной подструктуры в CLRS гласит, что «задача демонстрирует оптимальную подструктуру, если любой оптимальное решение проблемы содержит в себе оптимальные решения подзадач».

Почему бы не сказать, что «проблема имеет оптимальную подструктуру, если некоторый оптимальное решение проблемы содержит в себе оптимальные решения подзадач»?

Answer 1

Меня немного беспокоится с этим в моих исследованиях по алгоритмам аппроксимации, что включает в себя динамические программы, которые находят примерно оптимальные решения. Правильный способ подумать о правильности динамических программ, я полагаю, является как уменьшение (в смысле теории сложности) от проблемы в подпроблему. Это уменьшение часто применяется рекурсивно и с воспоминанием, но сейчас это детали.

Пусть a Будьте проблемой, а B - подпортема. Существует только одна подпроблема, потому что мы можем объединить несколько независимых подпороблений в один через обобщенный декарточный продукт. Уменьшение состоит из двух функций: F, из A-экземпляра к B-экземпляру, а H, из B-раствора B-раствора. Свойство правильности, которое нам нужно, это то, что для каждой функции g от каждого B-экземпляра к соответствующему оптимальному B-решению B (Oracle), композиция H. грамм . f - функция из каждого A-экземпляра к соответствующему оптимальному анализу. (Если H нуждается в доступе к A-экземпляру, затем расширяет B, чтобы его экземпляры содержали A-экземпляр, который должен быть скопирован дословно в соответствующем B-решении.)

Чтобы сделать вашу точку зрения, для конкретного A-экземпляра и оптимального A-решения, не нужно существовать Oracle G, так что трубопровод H. грамм . F производит это решение из данного экземпляра. (Другими словами, H, не нужно сюръективно.) С другой стороны, H должен иметь возможность обрабатывать все возможное оптимальное использование B-решение из G для B-экземпляра, сконструированного на F.

Одна общая стратегия для обеспечения правильности H, заключается в том, чтобы найти функцию «субструктуры» K из A-решений для B-решений и способа «сращивания» субструктуры, то есть доказательство того, что, учитывая A-решение. x и B-раствор y не хуже K (x), существует a-решение x "не хуже x такой, что k (x ')= y. Затем H может оптимизировать все в обратном образе под k его ввода. Не нужно, чтобы сплайс применяться ко всем решениям x, только один оптимальный.

Answer 2

В динамическом программировании мы разбиваем проблему на более мелкие подзадачи, выполняем некоторые манипуляции и даем ответ на более крупный ответ - очень похоже на рекурсивный подход (и не случайно).

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

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

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

---

Взгляните, к примеру, на рюкзак, и давайте посмотрим на его шаг DP:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

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

Если бы мы выбрали f(x,i-1) в max() - Возможно, это был неправильный выбор.Обеспечивая оптимальное решение всех подзадач, мы гарантируем, что этого не произойдет.