Что такое техника «вырезать и вставить»?

Question

Я видел ссылки на вырезать и вставить доказательства в определенных текстах по анализу алгоритмов и разработке. Это часто упоминается в контексте динамического программирования при доказательстве оптимальной подструктуры для задачи оптимизации (см. Главу 15.3 CLRS). Это также проявляется в манипуляциях с графиками.

Какова основная идея таких доказательств? Как мне использовать их, чтобы доказать правильность алгоритма или удобство конкретного подхода?

Answer 1

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

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

Answer 2

Доказательство от противного

P предполагается ложным, то есть! P истинно.

Показано, что! P подразумевает два взаимно противоречивых утверждения, Q и! Q.

Поскольку Q и! Q не могут быть оба истинными, предположение, что P ложно, должно быть неверным, а P должно быть истиной.

Answer 3

Вырезание и вставка - это способ, используемый при проверке концепций теории графов. Идея такова: предположим, у вас есть решение задачи A, вы хотите сказать, что некоторые ребра / узел должны быть доступны в решении.Вы будете предполагать, что у вас есть решение без заданного ребра / узла, вы попытаетесь восстановить решение, обрезав ребро / узел и вставив указанный ребро / узел, и скажете, что преимущество нового решения, по крайней мере, такое же, как и в предыдущем решении.

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

Answer 4

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

Жадность Корректность

Эта лекция отмечает Корректность MST из класса алгоритма старшекурсника MIT 2005 демонстрирует метод «вырезать и вставить», чтобы доказать как оптимальную структуру, так и свойство жадного выбора.

Эта лекция отмечает Корректность MST из MIT 6.046J / 18.410J, весна 2015 г., используйте технику «вырезать и вставить», чтобы доказать свойство жадного выбора

Корректность динамического программирования

Более достоверное объяснениедля «вырезать и вставить» было введено в CLRS (3-е издание) Глава 15.3 Элемент динамического программирования на стр. 379

"4. Вы показываете, что решения подзадач, используемых в рамках оптимального решения проблемысами должны быть оптимальными, используя технику «вырезать и вставить». Вы делаете это, предполагая, что каждый изПодзадача решения не является оптимальной и, следовательно, выводит противоречие.В частности, «вырезая» неоптимальное решение подзадачи и «вставляя» в оптимальное, вы показываете, что вы можете получить лучшее решение исходной проблемы, что противоречит вашему предположению, что у вас уже есть оптимальное решение.Если существует более одной подзадачи, они, как правило, настолько похожи, что аргумент «вырезать и вставить» для одного можно изменить для других без особых усилий. "