Оптимальная подструктура
Я пытаюсь получить более полное представление об использовании оптимального свойства субструктуры в динамическом программировании, но я не понял, почему мы должны доказать, что любое оптимальное решение проблемы содержит в себе оптимальные решения подзадач.,
Разве не достаточно показать, что какое-то оптимальное решение проблемы обладает этим свойством, а затем использовать это, чтобы доказать, что, поскольку решение, построенное с помощью нашего рекурсивного алгоритма, по крайней мере так же хорошо, как и оптимальное решение, само оно будет оптимальным? Другими словами, я не могу определить, где в аргументе правильности нашего алгоритма нам нужно, чтобы все оптимальные решения содержали оптимальные решения подзадач.
Чтобы уточнить:
Определение оптимальной подструктуры в CLRS гласит, что "проблема демонстрирует оптимальную подструктуру, если какое-либо оптимальное решение проблемы содержит в себе оптимальные решения подзадач".
Почему бы не сказать, что "проблема имеет оптимальную подструктуру, если какое-то оптимальное решение проблемы содержит в себе оптимальные решения подзадач"?
2 ответа
Меня это немного беспокоило в моих исследованиях алгоритмов аппроксимации, в которых участвуют динамические программы, которые находят примерно оптимальные решения. Я считаю, что правильное представление о правильности динамических программ - это сокращение (в смысле теории сложности) от проблемы к подзадаче. Это сокращение часто применяется рекурсивно и с запоминанием, но это детали прямо сейчас.
Пусть A- проблема, а B- подзадача. Есть только одна подзадача, потому что мы можем объединить несколько независимых подзадач в одну с помощью обобщенного декартова произведения. Редукция состоит из двух функций: f от A-экземпляра до B-экземпляра и h от B-решения до A-решения. Необходимое нам свойство корректности состоит в том, что для каждой функции g от каждого B-экземпляра до соответствующего оптимального B-решения (оракула) состав h. г. f - функция от каждого A-экземпляра до соответствующего оптимального A-решения. (Если h нужен доступ к A-экземпляру, то расширьте B так, чтобы его экземпляры содержали A-экземпляр, который необходимо дословно скопировать в соответствующее B-решение.)
Чтобы понять, для конкретного A-экземпляра и оптимального A-решения не требуется существование оракула g такого, что конвейер h. г. f производит это решение из данного экземпляра. (Другими словами, h не обязательно должен быть сюръективным.) С другой стороны, h должен иметь возможность обрабатывать каждое возможное оптимальное B-решение из g для B-экземпляра, построенного f.
Одна общая стратегия для обеспечения того, чтобы h был правильным, состоит в том, чтобы найти функцию "субструктуры" k от A-решений до B-решений и способ "склеить" субструктуру, то есть доказательство того, что, учитывая A-решение x и a B-решение y не хуже k(x), существует A-решение x'не хуже x такое, что k(x') = y. Тогда h может оптимизировать все по инверсному изображению при k своего ввода. Необязательно, чтобы сплайсинг применялся ко всем решениям x, только к одному оптимальному.
В динамическом программировании мы разделяем проблему на более мелкие подзадачи, выполняем некоторые манипуляции и даем ответ для более широкого ответа - очень похоже на рекурсивный подход (и не случайно).
Теперь, когда мы пришли к формальному доказательству правильности такого алгоритма, это делается по индукции. Мы докажем, что наше "базовое предложение" является правильным (обычно очень простым), и затем мы предполагаем, что любая задача, меньшая, чем текущая, - также оптимальна. Затем мы используем эту гипотезу, чтобы доказать правильность нашей большой проблемы.
Если бы мы не знали, что все решения являются оптимальными - мы не смогли бы доказать, что с помощью одного дополнительного шага мы смогли бы изменить оптимальное решение для более мелкой проблемы на оптимальное решение для более крупной проблемы - просто не было бы достаточно информации для доказать это утверждение.
Если бы мы знали, что некоторые из подзадач являются оптимальным решением - этого было бы недостаточно, чтобы гарантировать, что использование этой подзадачи, для которой у нас есть оптимальное решение - Indeeds, - это то, что нам нужно, чтобы получить оптимальное решение более крупной проблемы.
Посмотрите на рюкзак, например, и давайте посмотрим на его шаг DP:
f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))
Если бы мы знали, что только один из них является оптимальным - мы не смогли бы доказать, что алгоритм корректен, потому что нам, возможно, понадобился "другой" случай, когда у нас нет оптимального решения.
Если мы выбрали f(x,i-1) в max() - это мог быть неправильный выбор. Обеспечивая оптимальное решение всех подзадач, мы обеспечиваем, чтобы этого не произошло.