Что такое метод доказательства «вырезать и вставить»?
Я видел ссылки на доказательства вырезания и вставки в некоторых текстах по анализу и разработке алгоритмов. Его часто упоминают в контексте динамического программирования при доказательстве оптимальной подструктуры для задачи оптимизации (см. главу 15.3 CLRS). Это также проявляется при манипуляциях с графиками.
Какова основная идея таких доказательств? Как мне использовать их, чтобы доказать правильность алгоритма или удобство конкретного подхода?
1 ответ
Термин «вырезать и вставить» иногда встречается в алгоритмах при динамическом программировании (и других вещах тоже, но именно там я впервые увидел это). Идея состоит в том, что для того, чтобы использовать динамическое программирование, проблема, которую вы пытаетесь решить, вероятно, имеет некоторую базовую избыточность. Вы используете таблицу или подобную технику, чтобы избежать многократного решения одних и тех же проблем оптимизации. Конечно, прежде чем вы начнете пытаться использовать динамическое программирование, было бы неплохо доказать, что проблема заключается в этой избыточности, иначе вы ничего не получите, используя таблицу. Это часто называют свойством «оптимальной подзадачи» (например, в CLRS).
Техника «вырезать и вставить» - это способ доказать, что проблема обладает этим свойством. В частности, вы хотите показать, что когда вы предлагаете оптимальное решение проблемы, вы обязательно используете оптимальные решения составляющих подзадач. Доказательство от противного. Предположим, вы нашли оптимальное решение проблемы, используя неоптимальные решения подзадач. Затем, если бы вы заменили («обрезали») эти неоптимальные решения подзадач на оптимальные решения подзадач («вставив» их), вы бы улучшили свое оптимальное решение. Но, поскольку ваше решение было оптимальным по предположению, у вас есть противоречие. Есть несколько других шагов, связанных с таким доказательством, но это часть «вырезать и вставить».