WWW.KONFERENCIYA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Конференции, лекции

 

с/к “Эффективные алгоритмы”

Лекция 13: Подходы к решению NP-трудных задач

А. Куликов

Computer Science клуб при ПОМИ

http://logic.pdmi.ras.ru/infclub/

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 1 / 58

План лекции

Расщепление

1

Выполнимость (автоматическое доказательство)

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / 58 План лекции Расщепление 1 Выполнимость (автоматическое доказательство) Случайный порядок перебора 2 Выполнимость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / 58 План лекции Расщепление 1 Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 2 / Мотивация Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 3 / Мотивация Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0.

The “hardware” approach: возьмем в 10 раз более быстрый компьютер. Теперь мы можем решать примеры размера n0 + 4.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 3 / Мотивация Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0.

The “hardware” approach: возьмем в 10 раз более быстрый компьютер. Теперь мы можем решать примеры размера n0 + 4.

The “brainware” approach: придумаем алгоритм сложности 1.3n.

Это позволит нам решать примеры размера 2 · n0.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 3 / Мотивация Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0.

The “hardware” approach: возьмем в 10 раз более быстрый компьютер. Теперь мы можем решать примеры размера n0 + 4.

The “brainware” approach: придумаем алгоритм сложности 1.3n.

Это позволит нам решать примеры размера 2 · n0.

Другими словами, уменьшение основания экспоненты времени работы алгоритма увеличивает размер решаемых за данное время примеров в константное число раз, в то время как использование более быстрого компьютера способно увеличить размер лишь на константу.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 3 / Мотивация А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 4 / Мотивация Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 4 / Мотивация Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.

Лучшее понимание NP-трудных задач.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 4 / Мотивация Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.

Лучшее понимание NP-трудных задач.

Новые интересные комбинаторные и алгоритмические задачи.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 4 / Мотивация Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.

Лучшее понимание NP-трудных задач.

Новые интересные комбинаторные и алгоритмические задачи.

Общая теория.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 4 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 5 / Метод расщепления Основная идея Разбить входной пример задачи на несколько более простых примеров той же задачи, найти для них решения (рекурсивными вызовами) и построить по найденным решениям ответ для исходного примера.



А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 6 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 7 / Анализ алгоритмов расщепления А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 8 / Анализ алгоритмов расщепления как правило, анализ расщепляющего алгоритма состоит из длинного списка случаев А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 8 / Анализ алгоритмов расщепления как правило, анализ расщепляющего алгоритма состоит из длинного списка случаев в каждом случае показывается, что входной пример можно разбить на несколько примеров, чьи размеры на нужную константу меньше, чем размер исходного примера А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 8 / Анализ алгоритмов расщепления как правило, анализ расщепляющего алгоритма состоит из длинного списка случаев в каждом случае показывается, что входной пример можно разбить на несколько примеров, чьи размеры на нужную константу меньше, чем размер исходного примера доказательство для каждого случая представаляет собой простое комбинаторное рассуждение А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 8 / Анализ алгоритмов расщепления как правило, анализ расщепляющего алгоритма состоит из длинного списка случаев в каждом случае показывается, что входной пример можно разбить на несколько примеров, чьи размеры на нужную константу меньше, чем размер исходного примера доказательство для каждого случая представаляет собой простое комбинаторное рассуждение такой разбор случаев можно проводить автоматически А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 8 / Программа для автоматического доказательства верхних оценок для NP-трудных задач Вход А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 9 / Программа для автоматического доказательства верхних оценок для NP-трудных задач Вход NP-трудную задачу, сформулированную в терминах КНФ формул А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 9 / Программа для автоматического доказательства верхних оценок для NP-трудных задач Вход NP-трудную задачу, сформулированную в терминах КНФ формул множество правил упрощения для данной задачи А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 9 / Программа для автоматического доказательства верхних оценок для NP-трудных задач Вход NP-трудную задачу, сформулированную в терминах КНФ формул множество правил упрощения для данной задачи верхнюю оценку А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 9 / Программа для автоматического доказательства верхних оценок для NP-трудных задач Вход NP-трудную задачу, сформулированную в терминах КНФ формул множество правил упрощения для данной задачи верхнюю оценку По входным данным программа пытается найти алгоритм расщепления для данной задачи, который использует данные правила упрощения и имеет время работы, удовлетворяющее данной оценке.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 9 / Пример входа Пример входа Допсутим, программа получила задание доказать, что существует алгоритм для выполнимости, который использует правила удаления единичных клозов и чистых литералов и имеет время работы не хуже 1.619K, где K — количество клозов входной формулы.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 10 / Предобработка Предобработка А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 11 / Предобработка Предобработка программа должна доказать, что для любой упрощенной формулы можно найти (1, 2)-расщепление (то есть расщепление, которому соответствует рекуррентное неравенство А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 11 / Предобработка Предобработка программа должна доказать, что для любой упрощенной формулы можно найти (1, 2)-расщепление (то есть расщепление, которому соответствует рекуррентное неравенство каждый литерал упрощенной формулы входит в нее хотя бы один раз положительно и хотя бы один раз отрицательно (все остальные литералы являются чистыми и удаляются соответствующим правилом) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 11 / Предобработка Предобработка программа должна доказать, что для любой упрощенной формулы можно найти (1, 2)-расщепление (то есть расщепление, которому соответствует рекуррентное неравенство каждый литерал упрощенной формулы входит в нее хотя бы один раз положительно и хотя бы один раз отрицательно (все остальные литералы являются чистыми и удаляются соответствующим правилом) более того, если есть литерал, который входит в формулу хотя бы дважды, то расщепление по нему дает требуемое неравенство:





Предобработка Таким образом Программе нужно доказать, что упрощенную формулу, состоящую только из (1, 1)-литералов, всегда можно хорошо расщепить.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 12 / Автоматический разбор случаев А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 13 / Автоматический разбор случаев А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 13 / Автоматический разбор случаев А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 13 / Автоматический разбор случаев Автоматический разбор случаев А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 13 / Автоматический разбор случаев Автоматический разбор случаев Автоматический разбор случаев Автоматический разбор случаев План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 14 / Случайный порядок перебора Основная идея Если для нахождения решения достаточно знать какую-то его часть, можно попытаться ее угадать, а потом достроить решение.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 15 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 16 / Основные идеи PPSZ-подобного алгоритма Основные идеи А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 17 / Основные идеи PPSZ-подобного алгоритма Основные идеи выберем случайную перестановку переменных и будем расщеплять по переменным в соответствующем порядке А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 17 / Основные идеи PPSZ-подобного алгоритма Основные идеи выберем случайную перестановку переменных и будем расщеплять по переменным в соответствующем порядке возможно, расщеплять нужно будет не по всем переменным, посколько некоторые переменные могут получить значения в результате применения правил упрощения А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 17 / Основные идеи PPSZ-подобного алгоритма Основные идеи выберем случайную перестановку переменных и будем расщеплять по переменным в соответствующем порядке возможно, расщеплять нужно будет не по всем переменным, посколько некоторые переменные могут получить значения в результате применения правил упрощения для оценки времени работы будем считать, по скольким переменным нам расщеплять не пришлось А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 17 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} построить дерево рекурсии глубины не более 2n/3, где на каждом А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} построить дерево рекурсии глубины не более 2n/3, где на каждом сначала применяем правило удаления единичных клозов, А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} построить дерево рекурсии глубины не более 2n/3, где на каждом сначала применяем правило удаления единичных клозов, а потом выбираем первую переменную из перестановки, все еще входяющую в формулу, и расщепляемся по ней А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} построить дерево рекурсии глубины не более 2n/3, где на каждом сначала применяем правило удаления единичных клозов, а потом выбираем первую переменную из перестановки, все еще входяющую в формулу, и расщепляемся по ней если на каком-то шаге выяснилось, что формула выполнима, выдать “выполнима” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / PPSZ-подобный алгоритм Алгоритм PPSZ-SAT(F ) выбрать случайным образом перестановку из множества всех перестановок {1,..., n} построить дерево рекурсии глубины не более 2n/3, где на каждом сначала применяем правило удаления единичных клозов, а потом выбираем первую переменную из перестановки, все еще входяющую в формулу, и расщепляемся по ней если на каком-то шаге выяснилось, что формула выполнима, выдать “выполнима” в противном случае выдать “невыполнима” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 18 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 19 / Локальный поиск Основная идея Взять кандидата на решение и проверить, является ли он решением.

Если нет, то локально модифицировать. Если через несколько итераций решение не найдено, выбрать другого кандидата.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 20 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 21 / Хэммингово расстояние Определение А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 22 / Хэммингово расстояние Определение Хэммингово расстояние двух наборов — количество переменных, которым эти наборы присваивают разные значения.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 22 / Хэммингово расстояние Определение Хэммингово расстояние двух наборов — количество переменных, которым эти наборы присваивают разные значения.

Для набора t и числа d под Хэмминговым шаром (t, d ) (с центром в t и радуиса d ) будем понимать множество всех наборов, находящихся на расстоянии не более чем d от t.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 22 / Поиск в шаре Поиск в шаре Для формулы F в 3-КНФ поиск выполняющего набора в шаре (t, d ) может быть осуществлен за время 3d :

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 23 / Поиск в шаре Поиск в шаре Для формулы F в 3-КНФ поиск выполняющего набора в шаре (t, d ) может быть осуществлен за время 3d :

если t не выполянет F, возьмем произвольный невыполненный А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 23 / Поиск в шаре Поиск в шаре Для формулы F в 3-КНФ поиск выполняющего набора в шаре (t, d ) может быть осуществлен за время 3d :

если t не выполянет F, возьмем произвольный невыполненный рассмотрим три набора, полученных из t изменением значений А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 23 / Поиск в шаре Поиск в шаре Для формулы F в 3-КНФ поиск выполняющего набора в шаре (t, d ) может быть осуществлен за время 3d :

если t не выполянет F, возьмем произвольный невыполненный рассмотрим три набора, полученных из t изменением значений хотя бы один из них будет ближе к выполняющему набору А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 23 / 3 -Алгоритм Алгоритм Simple-3-SAT(F ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 24 / 3 -Алгоритм Алгоритм Simple-3-SAT(F ) проверить, есть ли выполняющий набор в шарах (0n, n/2), А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 24 / 3 -Алгоритм Алгоритм Simple-3-SAT(F ) проверить, есть ли выполняющий набор в шарах (0n, n/2), Лемма число переменных формулы F.

3 -Алгоритм Алгоритм Simple-3-SAT(F ) проверить, есть ли выполняющий набор в шарах (0n, n/2), Лемма число переменных формулы F.

Доказательство Понятно, что если выполняющий набор есть, то он содержится в одном из рассмотренных двух шаров.

План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 25 / Обобщение для k-SAT Обобщение для k-SAT А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 26 / Обобщение для k-SAT Обобщение для k-SAT покрыть множество всех наборов шарами равного радиуса (покрывающий код, covering code) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 26 / Обобщение для k-SAT Обобщение для k-SAT покрыть множество всех наборов шарами равного радиуса (покрывающий код, covering code) проверить каждый шар А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 26 / Обобщение для k-SAT Обобщение для k-SAT покрыть множество всех наборов шарами равного радиуса (покрывающий код, covering code) проверить каждый шар время работы алгоритма: (2 2/(k + 1))n А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 26 / Обобщение для k-SAT Обобщение для k-SAT покрыть множество всех наборов шарами равного радиуса (покрывающий код, covering code) проверить каждый шар время работы алгоритма: (2 2/(k + 1))n Открытый вопрос Придумать алгоритм, работающий быстрее.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 26 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 27 / Динамическое программирование Основная идея Последовательно находить и запоминать решения для подпримеров исходного примера.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 28 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 29 / Задача о коммивояжере Алгоритм Dynamic-TSP(G ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 30 / Задача о коммивояжере Алгоритм Dynamic-TSP(G ) для каждого непустого подмножества S {2,..., n} и для каждой вершины i S через Opt[S, i] будем обозначать длину кратчайшего маршрута. начнинающегося в вершине 1, проходящему через все вершины S {i} и заканчивающегося в А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 30 / Задача о коммивояжере Алгоритм Dynamic-TSP(G ) для каждого непустого подмножества S {2,..., n} и для каждой вершины i S через Opt[S, i] будем обозначать длину кратчайшего маршрута. начнинающегося в вершине 1, проходящему через все вершины S {i} и заканчивающегося в последовательно заполнить матрицу:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 30 / Задача о коммивояжере Алгоритм Dynamic-TSP(G ) для каждого непустого подмножества S {2,..., n} и для каждой вершины i S через Opt[S, i] будем обозначать длину кратчайшего маршрута. начнинающегося в вершине 1, проходящему через все вершины S {i} и заканчивающегося в последовательно заполнить матрицу:

вернуть оптимальную стоимость маршрута:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 30 / Открытые вопросы Лемма Сложность алгоритма Dynamic-TSP по времени и по памяти есть poly(n)2n.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 31 / Открытые вопросы Лемма Сложность алгоритма Dynamic-TSP по времени и по памяти есть poly(n)2n.

Факт Данный теоретический алгоритм был представлен в 1962-м году и до сих пор является лучшим из известных.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 31 / Открытые вопросы Лемма Сложность алгоритма Dynamic-TSP по времени и по памяти есть poly(n)2n.

Факт Данный теоретический алгоритм был представлен в 1962-м году и до сих пор является лучшим из известных.

Открытые вопросы А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 31 / Открытые вопросы Лемма Сложность алгоритма Dynamic-TSP по времени и по памяти есть poly(n)2n.

Факт Данный теоретический алгоритм был представлен в 1962-м году и до сих пор является лучшим из известных.

Открытые вопросы Придумать алгоритм, работающий за время 1.99n.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 31 / Открытые вопросы Лемма Сложность алгоритма Dynamic-TSP по времени и по памяти есть poly(n)2n.

Факт Данный теоретический алгоритм был представлен в 1962-м году и до сих пор является лучшим из известных.

Открытые вопросы Придумать алгоритм, работающий за время 1.99n.

Придумать алгоритм, работающий за время 2n, но полиномиальный по памяти.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 31 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 32 / Сведение к простой задаче Основная идея По входному примеру трудной задачи построить пример экспонециального размера для простой задачи и воспользоваться эффективным алгоритмом для этой задачи.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 33 / Табличная сумма Определение Задача о табличной k-сумме (table-k-SUM problem) заключается в проверке, можно ли из каждой строчки входной матрицы размера k m выбрать по числу так, чтобы их сумма равнялась входному результату S.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 34 / Табличная сумма Определение Задача о табличной k-сумме (table-k-SUM problem) заключается в проверке, можно ли из каждой строчки входной матрицы размера k m выбрать по числу так, чтобы их сумма равнялась входному результату S.

Перебор На полный перебор тратится время mk.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 34 / Табличная сумма Определение Задача о табличной k-сумме (table-k-SUM problem) заключается в проверке, можно ли из каждой строчки входной матрицы размера k m выбрать по числу так, чтобы их сумма равнялась входному результату S.

Перебор На полный перебор тратится время mk.

Улучшение для табличной 2-суммы Отсортируем первую строчку, после чего для каждого числа x второй строчки проверим бинарным поиском, нет ли в первой строчке числа S x. Все это займет O(m log m) времени.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 34 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) построить матрицу B[2, mk/2 ] следующим образом:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) построить матрицу B[2, mk/2 ] следующим образом:

в первую строчку записываем все возможные суммы элементов из первых k/2 строчек матрицы A (ровно по одному из каждой А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) построить матрицу B[2, mk/2 ] следующим образом:

в первую строчку записываем все возможные суммы элементов из первых k/2 строчек матрицы A (ровно по одному из каждой А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) построить матрицу B[2, mk/2 ] следующим образом:

в первую строчку записываем все возможные суммы элементов из первых k/2 строчек матрицы A (ровно по одному из каждой запускаем алгоритм для табличной 2-суммы на полученной А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / Улучшение для табличной k-суммы Алгоритм Table-k-SUM-Alg(A[k, m], S) построить матрицу B[2, mk/2 ] следующим образом:

в первую строчку записываем все возможные суммы элементов из первых k/2 строчек матрицы A (ровно по одному из каждой запускаем алгоритм для табличной 2-суммы на полученной Лемма Алгоритм Table-k-SUM-Alg имеет O(mk/2 log m) сложность по времени и O(mk/2 ) сложность по памяти.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 35 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 36 / Сумма подмножества Определение Задача о сумме подмножества (subset-sum problem) заключается в проверке того, можно ли из заданного набора из n чисел выбрать несколько так, чтобы их сумма равнялась заданному числу B.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 37 / Сумма подмножества Определение Задача о сумме подмножества (subset-sum problem) заключается в проверке того, можно ли из заданного набора из n чисел выбрать несколько так, чтобы их сумма равнялась заданному числу B.

Алгоритм Subset-Sum-Alg({bi }1in, B) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 37 / Сумма подмножества Определение Задача о сумме подмножества (subset-sum problem) заключается в проверке того, можно ли из заданного набора из n чисел выбрать несколько так, чтобы их сумма равнялась заданному числу B.

Алгоритм Subset-Sum-Alg({bi }1in, B) разбить входные числа на две части: b1,..., bn/2 и А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 37 / Сумма подмножества Определение Задача о сумме подмножества (subset-sum problem) заключается в проверке того, можно ли из заданного набора из n чисел выбрать несколько так, чтобы их сумма равнялась заданному числу B.

Алгоритм Subset-Sum-Alg({bi }1in, B) разбить входные числа на две части: b1,..., bn/2 и построить таблицу из двух строчек, в первую из которых записать все возможные суммы чисел из первой части, во вторую — из А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 37 / Сумма подмножества Определение Задача о сумме подмножества (subset-sum problem) заключается в проверке того, можно ли из заданного набора из n чисел выбрать несколько так, чтобы их сумма равнялась заданному числу B.

Алгоритм Subset-Sum-Alg({bi }1in, B) разбить входные числа на две части: b1,..., bn/2 и построить таблицу из двух строчек, в первую из которых записать все возможные суммы чисел из первой части, во вторую — из запустить для полученной матрицы алгоритм для табличной А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 37 / Анализ алгоритма Лемма Алгоритм Subset-Sum-Alg имеет сложность 2n/2 по времени и по памяти.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 38 / Анализ алгоритма Лемма Алгоритм Subset-Sum-Alg имеет сложность 2n/2 по времени и по памяти.

Открытые вопросы А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 38 / Анализ алгоритма Лемма Алгоритм Subset-Sum-Alg имеет сложность 2n/2 по времени и по памяти.

Открытые вопросы Придумать алгоритм, работающий быстрее.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 38 / Анализ алгоритма Лемма Алгоритм Subset-Sum-Alg имеет сложность 2n/2 по времени и по памяти.

Открытые вопросы Придумать алгоритм, работающий быстрее.

Придумать алгоритм, работающий за время 1.99n, но использующий лишь полиномиальную память.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 38 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

Алгоритм Matrix-Clique(G ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

Алгоритм Matrix-Clique(G ) построить матрицу смежности A графа G А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

Алгоритм Matrix-Clique(G ) построить матрицу смежности A графа G А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

Алгоритм Matrix-Clique(G ) построить матрицу смежности A графа G вернуть “да”, если на диагонали построенной матрицы есть хотя А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / 3-клика Определение Задача о 3-клике (3-clique problem) заключается в проверке наличия 3-клики (то есть полного подграфа на трех вершинах) во входном графе.

Алгоритм Matrix-Clique(G ) построить матрицу смежности A графа G вернуть “да”, если на диагонали построенной матрицы есть хотя вернуть “нет” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 39 / Анализ алгоритма Лемма Алгоритм выдает правильный ответ за время O(nw ), где w 2.376 — экспонента перемножения матриц (matrix multiplication exponent).

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 40 / Анализ алгоритма Лемма Алгоритм выдает правильный ответ за время O(nw ), где w 2.376 — экспонента перемножения матриц (matrix multiplication exponent).

Доказательство А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 40 / Анализ алгоритма Лемма Алгоритм выдает правильный ответ за время O(nw ), где w 2.376 — экспонента перемножения матриц (matrix multiplication exponent).

Доказательство важное свойство матрицы смежности: Ak [i, j] есть количество путей длины k из вершины i в вершину j в графе G (легко доказать по индукции) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 40 / Анализ алгоритма Лемма Алгоритм выдает правильный ответ за время O(nw ), где w 2.376 — экспонента перемножения матриц (matrix multiplication exponent).

Доказательство важное свойство матрицы смежности: Ak [i, j] есть количество путей длины k из вершины i в вершину j в графе G (легко доказать по индукции) 3-клика — это путь длины 3 из вершину в саму себя А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 40 / Анализ алгоритма Лемма Алгоритм выдает правильный ответ за время O(nw ), где w 2.376 — экспонента перемножения матриц (matrix multiplication exponent).

Доказательство важное свойство матрицы смежности: Ak [i, j] есть количество путей длины k из вершины i в вершину j в графе G (легко доказать по индукции) 3-клика — это путь длины 3 из вершину в саму себя для вычисления A3 требуется два умножения матриц А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 40 / Открытые вопросы Открытые вопросы А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 41 / Открытые вопросы Открытые вопросы Придумать более быстрый алгоритм для 3-клики.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 41 / Открытые вопросы Открытые вопросы Придумать более быстрый алгоритм для 3-клики.

Является ли 3-клика такой же сложной, как и умножение булевых А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 41 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 42 / Основные идеи Основные идеи сведения задачи о максимальном разрезе к задаче 3-клики Дан граф G на n вершинах.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 43 / Основные идеи Основные идеи сведения задачи о максимальном разрезе к задаче 3-клики Дан граф G на n вершинах.

Построим трехдольный граф H на 3 · 2n/3 вершинах со следующим свойством: исходный граф G имеет разрез веса w тогда и только тогда, когда H содержит 3-клику веса w.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 43 / Основные идеи Основные идеи сведения задачи о максимальном разрезе к задаче 3-клики Дан граф G на n вершинах.

Построим трехдольный граф H на 3 · 2n/3 вершинах со следующим свойством: исходный граф G имеет разрез веса w тогда и только тогда, когда H содержит 3-клику веса w.

Используем быстрое умножение матриц для поиска 3-клики.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 43 / Основные идеи Основные идеи сведения задачи о максимальном разрезе к задаче 3-клики Дан граф G на n вершинах.

Построим трехдольный граф H на 3 · 2n/3 вершинах со следующим свойством: исходный граф G имеет разрез веса w тогда и только тогда, когда H содержит 3-клику веса w.

Используем быстрое умножение матриц для поиска 3-клики.

Сложность: 2wn/3 1.732n.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 43 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Вспомогательный граф А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 44 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) оставить только ребра веса wij между долями Ti и Tj А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) оставить только ребра веса wij между долями Ti и Tj проверить, есть ли в модифицированном графе H 3-клика А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) оставить только ребра веса wij между долями Ti и Tj проверить, есть ли в модифицированном графе H 3-клика А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Алгоритм Алгоритм Matrix-MAX-CUT(G ) разбить множество вершин V на три равные части V1, V2, V построить вспомогательный трехдольный граф H: в i-я доля Ti содержит все возможные непустые подмножества Vi ; вес ребра (для остальных пар долей — аналогично) оставить только ребра веса wij между долями Ti и Tj проверить, есть ли в модифицированном графе H 3-клика вернуть максимальную найденную стоимость разреза А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 45 / Открытые вопросы Открытые вопросы А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 46 / Открытые вопросы Открытые вопросы Придумать алгоритм быстрее.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 46 / Открытые вопросы Открытые вопросы Придумать алгоритм быстрее.

Придумать алгоритм, работающий за время 1.99n, но полиномиальный по памяти.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 46 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 47 / Умный перебор Основная идея Используя свойства конкретной задачи, перебирать кандидатов на решения эффективно.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 48 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 49 / 3-раскрашиваемость Определение Задача 3-раскрашиваемости (3-coloring problem) заключается в проверке, можно ли раскрасить данный граф правильным образом в три цвета (смежные вершины не покрашены в один цвет).

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 50 / 3-раскрашиваемость Определение Задача 3-раскрашиваемости (3-coloring problem) заключается в проверке, можно ли раскрасить данный граф правильным образом в три цвета (смежные вершины не покрашены в один цвет).

Полный перебор Всего кандидатов на решение — 3n.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 50 / Умный перебор Алгоритм Simple-Clever-Enum(G ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 51 / Умный перебор Алгоритм Simple-Clever-Enum(G ) НУО, граф связен А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 51 / Умный перебор Алгоритм Simple-Clever-Enum(G ) НУО, граф связен зафиксировать цвет 1 для какой-нибудь вершины А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 51 / Умный перебор Алгоритм Simple-Clever-Enum(G ) НУО, граф связен зафиксировать цвет 1 для какой-нибудь вершины последовательно выбирать вершины, у которых есть хотя бы один уже покрашенный сосед и рассматривать два варианта ее А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 51 / Умный перебор Алгоритм Simple-Clever-Enum(G ) НУО, граф связен зафиксировать цвет 1 для какой-нибудь вершины последовательно выбирать вершины, у которых есть хотя бы один уже покрашенный сосед и рассматривать два варианта ее Лемма Алгоритм Simple-Clever-Enum имеет время работы 2n.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 51 / Еще один умный перебор Алгоритм Clever-Enum(G ) А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Еще один умный перебор Алгоритм Clever-Enum(G ) для каждого S {1,..., n} размера не более n/ А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Еще один умный перебор Алгоритм Clever-Enum(G ) для каждого S {1,..., n} размера не более n/ А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Еще один умный перебор Алгоритм Clever-Enum(G ) для каждого S {1,..., n} размера не более n/ покрасить оставшиеся вершины в цвета 2 и А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Еще один умный перебор Алгоритм Clever-Enum(G ) для каждого S {1,..., n} размера не более n/ покрасить оставшиеся вершины в цвета 2 и если покраска правильная, выдать “да” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Еще один умный перебор Алгоритм Clever-Enum(G ) для каждого S {1,..., n} размера не более n/ покрасить оставшиеся вершины в цвета 2 и если покраска правильная, выдать “да” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 52 / Анализ алгоритма Лемма Алгоритм Clever-Enum корректно выдает решение за время 1.89n.

Доказательство А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 53 / Анализ алгоритма Лемма Алгоритм Clever-Enum корректно выдает решение за время 1.89n.

Доказательство в любой раскраске один из цветов встречается не более n/3 раз А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 53 / Анализ алгоритма Лемма Алгоритм Clever-Enum корректно выдает решение за время 1.89n.

Доказательство в любой раскраске один из цветов встречается не более n/3 раз будем считать, что это всегда первый цвет А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 53 / Анализ алгоритма Лемма Алгоритм Clever-Enum корректно выдает решение за время 1.89n.

Доказательство в любой раскраске один из цветов встречается не более n/3 раз будем считать, что это всегда первый цвет 2-раскрашиваемость решается за линейное время А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 53 / Анализ алгоритма Лемма Алгоритм Clever-Enum корректно выдает решение за время 1.89n.

Доказательство в любой раскраске один из цветов встречается не более n/3 раз будем считать, что это всегда первый цвет 2-раскрашиваемость решается за линейное время ( n ) H(1/3)n 1.89n, где H — бинарная энтропия:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 53 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 54 / Случайное сведение к простой задаче Основная идея Используя случайные биты, так изменить входной пример задачи, чтобы для поиска решения понадобилось полиномиальное время.

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 55 / План лекции Расщепление Выполнимость (автоматическое доказательство) Случайный порядок перебора Выполнимость Локальный поиск 3-выполнимость k-выполнимость Динамическое программирование Задача о коммивояжере Сведение к простой задаче Сумма подмножества Максимальный разрез Умный перебор 3-раскрашиваемость Случайное сведение к простой задаче 3-раскрашиваемость А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 56 / 3-раскрашиваемость Алгоритм А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / 3-раскрашиваемость Алгоритм повторить c · 1.5n раз:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / 3-раскрашиваемость Алгоритм повторить c · 1.5n раз:

для каждой вершины выбрать случайным образом один из трех цветов, в который данная вершина не покрашена А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / 3-раскрашиваемость Алгоритм повторить c · 1.5n раз:

для каждой вершины выбрать случайным образом один из трех цветов, в который данная вершина не покрашена записать формулу в 2-КНФ, которая выполнима тогда и только тогда, когда граф можно раскрасить с заданными ограничениями:

А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / 3-раскрашиваемость Алгоритм повторить c · 1.5n раз:

для каждой вершины выбрать случайным образом один из трех цветов, в который данная вершина не покрашена записать формулу в 2-КНФ, которая выполнима тогда и только тогда, когда граф можно раскрасить с заданными ограничениями:

если полученная формула выполнима, выдать ответ “да” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / 3-раскрашиваемость Алгоритм повторить c · 1.5n раз:

для каждой вершины выбрать случайным образом один из трех цветов, в который данная вершина не покрашена записать формулу в 2-КНФ, которая выполнима тогда и только тогда, когда граф можно раскрасить с заданными ограничениями:

если полученная формула выполнима, выдать ответ “да” выдать ответ “нет” А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 57 / А. Куликов (CS клуб при ПОМИ) 13. Подходы к NP-трудным задачам 58 /

Похожие работы:

«НАНОМЕТР № 3 (55) март 2011 www.fnm.msu.ru www.nanometer.ru Информационный бюллетень ФНМ Олимпиада началась! 21 марта стартовал очный этап V Всероссийского интеллектуального форума - олимпиады по нанотехнологиям. В его программу входят испытания по математике, химии, физике и биологии для школьников, творческие конкурсы и экспериментальный тур для молодых ученых. Подробный отчет об олимпиаде читайте в следующем номере “Нанометра“. Открытие олимпиады: участников приветствует член-корреспондент...»

«В. Ю. БЕЛОНОГОВА ИТАЛЬЯНСКИЕ ВСТРЕЧИ ГОГОЛЯ С ЭМИГРАНТОМ М. ГОРЬКИМ Все мы вышли из гоголевской “Шинели”. Эта сентенция, приписываемая Ф. М. Достоевскому, как известно, зафиксировала историко-литературную традицию, согласно которой именно Гоголь считался главой и зачинателем реалистического метода в русской литературе. Вслед за революционно-демократической критикой середины ХIХ века реалистическая, социально детерминированная литература зачастую и обозначалась как гоголевское направление - в...»

«Федеральное государственное образовательное учреждение высшего профессионального образования Чувашский государственный университет имени И.Н. Ульянова Батыревский филиал Кафедра экономических дисциплин КОНСПЕКТ ЛЕКЦИЙ по дисциплине Комплексный экономический анализ Составитель: кандидат сельскохозяйственных наук, доцент Баданов Геннадий Павлович Батырево - 2009 СОДЕРЖАНИЕ 1. Основы экономического анализа. Понятие об анализе хозяйственной деятельности. История становления и развития 1.2. Роль АХД...»

«28.11.2011 19:15 Город 21:30 Создание совершенства 08:30 Голубой дракончик 19:45 Вятка Today 22:30 Гостиный двор 09:00 Зачем и почему 20:00 Прогород 23:00 Твори, выдумывай, пробуй 09:30 Искатели во времени 2x2 20:30 Миф 23:30 Теория невероятности 10:00 Исследовательский 22:50 Город экспресс 06:00 Химэн 23:20 Вятка Today Animal Planet Channel 10:30 Наука у тебя дома 06:30 Вольтрон 23:35 Прогород 10:45 Наука у тебя дома 06:55 Оазис 06:00 Обезьянья жизнь 11:00 Однажды возникла. A-One 06:25 Самое...»

«КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ Филиал КФУ в г. Чистополе А.А. ЗАМАЙДИНОВ БЕЗОПАСНОСТЬ ЖИЗНЕДЕЯТЕЛЬНОСТИ Конспект лекций Казань-2013 Замайдинов А.А. Безопасность жизнедеятельности: Краткий конспект лекций / А.А. Замайдинов; Каз.федер.ун-т. – Казань, 2013. –96 с. В предлагаемых лекциях системно изложены основные положения развивающейся научной и учебной дисциплины, именуемой безопасностью жизнедеятельности (БЖД). Рассматриваются теоретические основы БЖД, принципы обеспечения безопасности,...»

«Рецензенты: Кафедра истории народного хозяйства и экономических учений Экономического факультета МГУ им. М.В.Ломоносова. Заведующий кафедрой ИНХ и ЭУ Экономического факультета МГУ им. М.В.Ломоносова, д.э.н, проф. Худокормов А.Г. Профессор кафедры истории ИППК МГУ им. М.В.Ломоносова, д.и.н., Змеев В.А. А.А. Крамар Практикум по отечественной истории. Пособие для студентов экономических ВУЗов. — М.:, 2012. Цель настоящего пособия — помощь студентам в организации работы и успешном освоении курса...»

«МАТЕРИАЛЫ ДЛЯ ЛЕКЦИОННЫХ И ПРАКТИЧЕСКИХ ЗАНЯТИЙ ПО ДИСЦИПЛИНЕ РУССКИЙ ЯЗЫК И КУЛЬТУРА РЕЧИ 1. Стиль речи Написанное или высказанное произведение слова для правильного и незатрудненного его понимания должно обладать рядом качеств, которые ожидают от него читатель или слушатель. В научной филологической традиции 19-20 вв. раздел языкознания, который занимается правильностью, выразительностью и другими позитивными качествами речи, называют стилистикой или культурой речи. Уже в древности и в Новое...»

«ЛЕКЦИЯ 1 НАУЧНАЯ ЗАДАЧА ИЗУЧЕНИЯ МЕСТНОЙ ИСТОРИИ. ИСТОРИЧЕСКИЙ ПРОЦЕСС. ИСТОРИЯ КУЛЬТУРЫ ИЛИ ЦИВИЛИЗАЦИИ. ИСТОРИЧЕСКАЯ СОЦИОЛОГИЯ. ДВЕ ТОЧКИ ЗРЕНИЯ В ИСТОРИЧЕСКОМ ИЗУЧЕНИИ - КУЛЬТУРНО-ИСТОРИЧЕСКАЯ И СОЦИОЛОГИЧЕСКАЯ. МЕТОДОЛОГИЧЕСКОЕ УДОБСТВО И ДИДАКТИЧЕСКАЯ ЦЕЛЕСООБРАЗНОСТЬ ВТОРОЙ ИЗ НИХ В ИЗУЧЕНИИ МЕСТНОЙ ИСТОРИИ. СХЕМА СОЦИАЛЬНО-ИСТОРИЧЕСКОГО ПРОЦЕССА. ЗНАЧЕНИЕ МЕСТНЫХ И ВРЕМЕННЫХ СОЧЕТАНИЙ ОБЩЕСТВЕННЫХ ЭЛЕМЕНТОВ В ИСТОРИЧЕСКОМ ИЗУЧЕНИИ. МЕТОДОЛОГИЧЕСКИЕ УДОБСТВА ИЗУЧЕНИЯ РУССКОЙ ИСТОРИИ С...»

«План занятий Дисциплина ФИЗИКА (ЧАСТЬ 1) ФИЗИЧЕСКИЕ ОСНОВЫ МЕХАНИКИ Литература. №№ Авторы Наименование, издательство, год издания. Основная литература: Савельев И.В. Курс физики: Учеб.:Т.1.-М.: Наука. Гл. ред. 1 физ-мат. лит.2000. Дополнительная литература. Тихомиров Ю.В. Лаб. работы с элементами компьютерного моделирования (1й и 2й сем.). М.: МГТУ ГА. 2000. Новиков С.М Сборник заданий по общей физике. – 3 М.ОНИКС. Мир и образование. 2006.-510 с. Темы и лекции. Блок 1. Тема 1. Кинематика...»

«Некоммерческая организация Ассоциация московских вузов Федеральное государственное образовательное учреждение высшего профессионального образования Московский государственный агроинженерный университет имени В.П. Горячкина Научно-информационный материал Оценка технического состояния дизелей с топливной системой Common Rail Москва 2011 1 СОДЕРЖАНИЕ КУРСА ЛЕКЦИЙ Стр. Лекция 1. Обоснование необходимости разработки новых методов диагностирования ТА дизелей с 3 топливной системой Common Rail.......»

«ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2009 Философия. Социология. Политология №2(6) АРХИВ От переводчика Кристина Шюес изучала философию, политологию и литературу в университетах Гамбурга и Филадельфии, защитила докторскую диссертацию по философии (Ph.D.) в Университете Темпла (Филадельфия, США). В настоящее время К. Шюес работает в должности профессора философии в Институте образования и социальных наук Университета г. Вехта (Германия) и читает лекции в университетах г. Вилланова...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Черногоров Е.П. ТЕОРЕТИЧЕСКАЯ МЕХАНИКА. ПРИНЦИП ДАЛАМБЕРА Курс лекций ЧЕЛЯБИНСК 2010 1. ПРИНЦИП ДАЛАМБЕРА ДЛЯ МАТЕРИАЛЬНОЙ ТОЧКИ Рассмотрим движение материальной точки массой m в пространстве инерциальной системы отсчета Oxyz (рис. 1.1). Пусть точка движется под действием активных сил, равнодействующая которых F. На точку наложены связи, N – равнодействующая сил реакций этих связей. Дифференциальное...»

«Авессалом Подводный Серия Психология и астрология Часть 1 ПСИХОЛОГИЯ ДЛЯ АСТРОЛОГОВ Аквамарин 2010 ББК Ю9 88 П44 П44 Авессалом Подводный Психология для астрологов, Москва, Аквамарин, 2010 – 408 с. Серия Психология и астрология Часть 1. Психология для астрологов Часть 2. Эволюция личности Часть 3. Астрология для психологов Часть 4. Архетипы психики Часть 1 посвящена обсуждению понятий и сюжетов, с которыми в первую очередь сталкивается начинающий психолог-практик, не имея адекватного языка для...»

«1 ЛЕКЦИЯ №22 СОВРЕМЕННАЯ ФИЗИКА АТОМОВ И МОЛЕКУЛ Атом водорода в квантовой механике Решение задачи об энергетических уровнях электрона для атома водорода (а также водородоподобных систем: иона гелия Не+, двукратно ионизованного лития Li++ и др.) сводится к задаче о движении электрона в кулоновском поле ядра. Потенциальная энергия взаимодействия электрона с ядром, обладающим зарядом Ze (для атома водорода Z = 1), Ze 2 U(r ) =, (22.1) 4 o r где r — расстояние между электроном и ядром. Графически...»

«Начало Название Ядро Литература Безопасность Определение ОС Примеры Компоненты ОС Лекция 1. Введение Операционные системы 10 сентября 2012 г. Лекция 1 1 / 31 Начало Название Ядро Литература Безопасность Определение ОС Примеры Компоненты ОС Список литературы Обзор Д. В. Иртегов. Введение в операционные системы. БХВ-Петербург, СПб., 2-е edition, 2008. В. Столлингс. Операционные системы: Пер. с англ. Вильямс, М., 4-е edition, 2004. Э. Таненбаум. Современные операционные системы: Пер. с англ....»

«1866 4 апреля. Уже мало-помалу стал проясняться горизонт Казанского университета, – вспоминал попечитель Шестаков, – как вдруг разразилась гроза нежданная, негаданная: гнусный убийца дерзнул поднять руку на помазанника божия. Вопрос, кто убийца, сильно занимал все умы. Какова поднялась тревога в Казанском университете, когда получено было известие, что имя посягавшего на жизнь Царя – Димитрий Каракозов, имя, которое стояло в списке студентов Казанского университета на 1863/4 акад. год! Я сам...»

«РАСПИСАНИЕ Учебных занятий 1 курса геологического факультета на ВЕСЕННИЙ семестр 2012-2013 учебного года Время 101(10) 102 (17) 119(14) 103(13) 111(5) 104(21) 105(13) 112(15) 126(11) 106(16) 107(22) 108(12) 109(20) 110(21) день Время день Ч/н Ч/н Ч/Н с 18.02. практикум ФИЗИКА Минералогия МИНЕРАЛОГИЯ С Ч/Н с 11.02. ОБЩАЯ физфак 339, 4 часа Общая геология КРИСТАЛЛОХИМИЯ с основ.кристал. ОСН. КРИСТАЛ. практикум ГЕОЛОГИЯ 9:00- 9:00доп.гл.) Урусов В.С., Еремин Н.Н. Ряховская С.К. Ч/Н с 11.02. лекция...»

«Государственное образовательное учреждение высшего профессионального образования Федеральное агентство по здравоохранению и социальному развитию Московская медицинская академия им. И.М. Сеченова Фармацевтический факультет Кафедра биотехнологии Катлинский А.В., Сазыкин Ю.О., Орехов С.Н., Чакалева И.И. КУРС ЛЕКЦИЙ ПО БИОТЕХНОЛОГИИ Москва 2005 СОДЕРЖАНИЕ. Современная биотехнология в создании и производстве Лекция 1. лекарственных средств.. 1 Лекция 2 Антибиотики... 9 Слагаемые биотехнологического...»

«Северный государственный медицинский университет В. А. КУДРЯВЦЕВ ДЕТСКАЯ ХИРУРГИЯ в лекциях Учебник для медицинских вузов Издание 2-е, переработанное Архангельск 2007 УДК 617-089(075) ББК 54.5я73+57.3я73 К 88 Рецензент: профессор, доктор медицинских наук В. П. Быков Печатается по решению редакционно-издательского совета Северного государственного медицинского университета Кудрявцев В. А. К Детская хирургия в лекциях: Учебник для медицинских вузов: Изд. 2-е, перераб. — Архангельск: Издательский...»

«Лекция 1.4 1.4 Метрические пространства Введение в нелинейный функциональный анализ Ю. Э. Линке Институт динамики систем и теории управления СО РАН, г. Иркутск email: linke@icc.ru 17 марта 2011 г. Ю. Э. Линке (Институт динамики систем и теории управления СО РАН, г. Иркутск email: марта 2011 г. Лекция 1.4 1.4 Метрические пространства 17 linke@icc.ru) 1 / 81 План лекции Введение 1 Определение 2 Примеры 3 G и F множества 4 Компактность и полнота 5 Метризуемость декартовых произведений Гильбертов...»









 
2014 www.konferenciya.seluk.ru - «Бесплатная электронная библиотека - Конференции, лекции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.