Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

Жадная правильность

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

В этой лекции отмечается Корректность MST от MIT 6.046J/18.410J spring 2015 использует технологию "вырезания и вставки" для доказать свойство жадного выбора

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

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

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