Что такое вырезка и вставка?

Question

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

Эта лекция отмечает Correctness of MST из MIT 6.046J/18.410J весной 2015 года использование «вырезать и -пастевая техника для доказательства gr eedy-выбор недвижимость

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

Более аутентичное объяснение «вырезать и вставить» было введено в КСПСЕ (третий Edtion) Глава 15.3 Элемента динамического программирования на странице 379

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

Answer 4

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

P ложным, то есть! P истинно.

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

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