Алгоритмы для NP-трудных задач

Общая информация
ЛекторА. С. Куликов
Семестрвесна 2013
Дата начала01.03.2013
Количество пар6
Язык курсарусский
Вопросы к экзамену
Видеоhttp://video.yandex.ru/users/uralcsclub/collection/20/
Анонсы
Объявление для печати
Встреча ВКонтактеhttp://vk.com/event50208526
Аннотация

В мини-курсе будет дан обзор идей и методов, использующихся при построении и анализе алгоритмов для NP-трудных задач. Несмотря на то что эффективных алгоритмов для таких задач до сих пор неизвестно, NP-трудные задачи часто возникают на практике. Мы рассмотрим приближённые алгоритмы (позволяющие эффективно находить решение, которое гарантированно не сильно хуже оптимального), точные алгоритмы с доказуемыми верхними оценками (которые более интересны с теоретической точки зрения) и эвристики (алгоритмы, хорошо работающие на практике, но не имеющие теоретических гарантий на время работы и ошибку приближения).

Курс начнётся с демонстрации всех трёх типов алгоритмов для классической NP-трудной задачи — задачи коммивояжёра, которая формулируется следующим образом: даны $ n $ городов и попарные расстояния между ними, необходимо найти кратчайший маршрут, проходящий по всем городам ровно по одному разу. Практические применения данной задачи включают в себя разработку микросхем, планирование, сборку генома. Трудность данной задачи объясняется тем, что с ростом количества городов количество потенциальных маршрутов растёт очень быстро. Например, даже для пятнадцати городов количество таких маршрутов равно 43 589 145 600. Если считать, что компьютер может перебрать миллиард маршрутов в секунду, то искать решение для задачи с сотней городов ему придётся больше триллиона лет. В то же время в задачах, возникающих на практике, количество городов обычно составляет десятки тысяч. К счастью, всё же есть методы, позволяющие решать такие примеры на практике. Например, в 2004 году был найден оптимальный цикл по 24 978 городам Швеции, а в 2006 был вычислен оптимальный маршрут лазера при построении интегральной схемы через 85 900 точек.

Задаче коммивояжёра посвящено огромное количество статей и исследований, как практических, так и теоретических. На сайте http://www.tsp.gatech.edu/index.html можно найти множество ссылок (статьи, книги, датасеты, программы, игры, соревнования и даже фильм).

Для данной задачи мы узнаем:

  • методы, с помощью которых задачу коммивояжёра решают на практике, — метод ветвей и границ и метод локального поиска;
  • почему в общем случае для данной задачи приближённые алгоритмы вряд ли существуют;
  • $ 1.5 $-приближённый алгоритмы для задачи коммивояжёра в метрическом пространстве (когда длины рёбер графа удовлетворяют неравенству треугольника);
  • $ 2/3 $-приближённый алгоритм для случая, когда найти необходимо не минимальный, а максимальный путь коммивояжёра;
  • классический алгоритм, основанный на методе динамического программирования, со временем работы $ O^*(2^n) $;
  • алгоритм, основанный на формуле включений-исключений, со временем работы $ O^*(2^n) $ и псевдополиномиальной памятью;
  • алгоритм со временем работы $ O^*(4^nn^{\log n}) $ и полиномиальной памятью, основанный на методе перебора с возвратом;
  • недавний алгоритм, улучшающий верхнюю оценку $ O^*(2^n) $, основанный на матрицах Татта и быстрой проверке на равенство нуля многочлена;
  • применения к другим NP-трудным задачам.
После этого будет продемонстрировано ещё несколько элегантных идей решения NP-трудных задач.

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

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. NP-полные задачи
(01.03.2013 - 17:50 - 19:00)

Задачи поиска, NP-полные задачи, сведения.
2. Алгоритмы для задачи коммивояжёра
(01.03.2013 - 19:10 - 21:00)

Эвристики: метод локального поиска и метод ветвей и границ. Приближённые алгоритмы: $ 1.5 $-приближённый алгоритм для задачи коммивояжёра в метрическом пространстве, неприближаемость общего случая, $ 1/2 $-приближение для максимизационного варианта.
3. Алгоритмы для задачи коммивояжёра (продолжение)
(02.03.2013 - 17:50 - 19:30)

Точные алгоритмы: динамическое программирование; формула включений-исключений; матрица Татта и перманент.
4. Алгоритмы для задачи выполнимости
(02.03.2013 - 19:40 - 21:00)

Формулировка и важность задачи. Простые подклассы: 2-SAT, Horn SAT. Примеры сведений: гамильтонов цикл, максимальный разрез, вершинное покрытие.
5. Алгоритмы для задачи выполнимости (продолжение)
(03.03.2013 - 17:50 - 21:00)

Алгоритмы расщепления. Локальный поиск. Точный алгоритм для задачи максимальной 2-выполнимости, основанный на быстром умножении матриц. Приближённый алгоритм для задачи максимальной 2-выполнимости, основанный на полуопределённом программировании.
Ваша оценка: Пусто Средняя: 5 (3 голосов)
Share |