Совершенный алгоритм. Алгоритмы для NP-трудных задач

Предисловие
О чем эти книги
Навыки, которые вы приобретете
В чем особенность этой книги
Для кого эта книга?
Дополнительные ресурсы
Благодарности
От издательства
Глава 19. Что такое NP-трудность?
19.1. Задача о минимальном остовном дереве и задача коммивояжера: алгоритмическая загадка
19.1.1. Задача о минимальном остовном дереве
19.1.2. Задача коммивояжера
19.1.3. Безуспешные попытки решить задачу коммивояжера
19.1.4. Решения к тестовым заданиям 19.1–19.2
19.2. Возможные уровни профессиональной компетенции
19.3. «Легкие» и «трудные» задачи
19.3.1. Полиномиально-временные алгоритмы
19.3.2. Полиномиальное время против экспоненциального
19.3.3. Легкорешаемые задачи
19.3.4. Относительная труднорешаемость
19.3.5. Трудные задачи
19.3.6. Предположение, что P ≠ NP
19.3.7. Предварительное определение NP-трудности
19.3.8. Рандомизированные и квантовые алгоритмы
19.3.9. Тонкости
19.4. Алгоритмические стратегии для NP-трудных задач
19.4.1. Универсальный, правильный, быстрый (выбрать два)
19.4.2. Компромисс в отношении универсальности
19.4.3. Компромисс в отношении правильности
19.4.4. Компромисс в отношении скорости
19.4.5. Ключевые выводы
19.5. Доказательство NP-трудности: простой рецепт
19.5.1. Редукции
19.5.2. Использование упрощений для разработки быстрых алгоритмов
19.5.3. Использование упрощений для распространения NP-трудности
19.5.4. NP-трудность бесцикловых кратчайших путей
19.5.5. Решение к тестовому заданию 19.3
19.6. Ошибки новичков и допустимые неточности
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 20. Компромисс в отношении правильности: эффективные неточные алгоритмы
20.1. Минимизация производственной продолжительности
20.1.1. Определение задачи
20.1.2. Жадные алгоритмы
20.1.3. Алгоритм Грэма
20.1.4. Время работы
20.1.5. Приближенная правильность
20.1.6. Доказательство теоремы 20.1
20.1.7. Сначала самое длительное время обработки
20.1.8. Доказательство теоремы 20.4
20.1.9. Решения к тестовым заданиям 20.1–20.3
20.2. Максимальный охват
20.2.1. Определение задачи
20.2.2. Дальнейшие применения
20.2.3. Жадный алгоритм
20.2.4. Плохие примеры для GreedyCoverage
20.2.5. Приближенная правильность
20.2.6. Ключевая лемма
20.2.7. Доказательство теоремы 20.7
20.2.8. Решения к тестовым заданиям 20.4–20.5
*20.3. Максимизация влияния
20.3.1. Каскады в социальных сетях
20.3.2. Пример
20.3.3. Задача о максимизации влияния
20.3.4. Жадный алгоритм
20.3.5. Приближенная правильность
20.3.6. Влияние есть взвешенная сумма функций охвата
20.3.7. Доказательство теоремы 20.9
20.3.8. Решение к тестовому заданию 20.6
20.4. Эвристический алгоритм двукратной замены для задачи коммивояжера
20.4.1. Решение задачи коммивояжера
20.4.2. Улучшение тура двукратной заменой
20.4.3. Алгоритм двукратной замены 2-OPT
20.4.4. Время работы
20.4.5. Качество решения
20.4.6. Решения к тестовым заданиям 20.7–20.8
20.5. Принципы локального поиска
20.5.1. Метаграф допустимых решений
20.5.2. Парадигма проектирования алгоритма локального поиска
20.5.3. Три модельных решения
20.5.4. Два решения по проектированию алгоритма
20.5.5. Время выполнения и качество решения
20.5.6. Избегание плохих локальных оптимумов
20.5.7. Когда использовать локальный поиск?
20.5.8. Решения к тестовым заданиям 20.9–20.10
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 21. Компромисс в отношении скорости: точные неэффективные алгоритмы
21.1. Алгоритм Беллмана — Хелда — Карпа для задачи коммивояжера
21.1.1. Базовый уровень: исчерпывающий поиск
21.1.2. Динамическое программирование
21.1.3. Оптимальная подструктура
21.1.4. Рекуррентное уравнение
21.1.5. Подзадачи
21.1.6. Алгоритм Беллмана — Хелда — Карпа
21.1.7. Решение к тестовому заданию 21.1
*21.2. Поиск длинных путей посредством цветового кодирования
21.2.1. Актуальность
21.2.2. Определение задачи
21.2.3. Первая атака на подзадачи
21.2.4. Цветовое кодирование
21.2.5. Вычисление самого дешевого панхроматического пути
21.2.6. Правильность и время выполнения
21.2.7. Рандомизация спешит на помощь
21.2.8. Окончательный алгоритм
21.2.9. Время выполнения и правильность
21.2.10. Пересмотр сетей белок-белковых взаимодействий
21.2.11. Решения к тестовым заданиям 21.2–21.4
21.3. Алгоритмы для конкретных задач против волшебных ящиков
21.3.1. Редукции и волшебные ящики
21.3.2. Решатели задач MIP и SAT
21.3.3. Чему вы научитесь и чему не научитесь
21.3.4. Ошибки новичка повторно
21.4. Решатели задач MIP
21.4.1. Пример: задача о рюкзаке
21.4.2. Задачи MIP в более общем случае
21.4.3. Решатели задач MIP: некоторые отправные точки
21.5. Решатели задач SAT
21.5.1. Пример: раскраска графа
21.5.2. Выполнимость булевых формул
21.5.3. Кодирование раскраски графа как задачи SAT
21.5.4. Решатели задач SAT: некоторые отправные точки
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 22. Доказательство NP-трудных задач
22.1. Редукции повторно
22.2. Задача 3-SAT и теорема Кука — Левина
22.3. Общая картина
22.3.1. Ошибка новичка повторно
22.3.2. Восемнадцать редукций
22.3.3. Зачем продираться через доказательства NP-трудности?
22.3.4. Решение к тестовому заданию 22.1
22.4. Шаблон для редукций
22.5. Задача о независимом множестве является NP-трудной
22.5.1. Главная идея
22.5.2. Доказательство теоремы 22.2
*22.6. Ориентированный гамильтонов путь является NP-трудным
22.6.1. Кодирование переменных и присвоения истинности
22.6.2. Кодирование ограничений
22.6.3. Доказательство теоремы 22.4
22.7. Задача коммивояжера является NP-трудной
22.7.1. Задача о неориентированном гамильтоновом пути
22.7.2. Доказательство теоремы 22.7
22.8. Задача о сумме подмножества является NP-трудной
22.8.1. Базовый подход
22.8.2. Пример: четырехвершинный цикл
22.8.3. Пример: пятивершинный цикл
22.8.4. Доказательство теоремы 22.9
Задачи на закрепление материала
Задачи повышенной сложности
Глава 23. P, NP и все такое прочее
*23.1. Накопление свидетельств труднорешаемости
23.1.1. Построение убедительного случая с помощью редукций
23.1.2. Выборка множества C для задачи коммивояжера
*23.2. Решение, поиск и оптимизация
*23.3. NP: задачи с легко распознаваемыми решениями
23.3.1. Определение класса сложности NP
23.3.2. Примеры задач в NP
23.3.3. Задачи NP поддаются решению исчерпывающим поиском
23.3.4. NP-трудные задачи
23.3.5. Теорема Кука — Левина повторно
23.3.6. Решение к тестовому заданию 23.1
*23.4. Предположение, что P ≠ NP
23.4.1. P: задачи NP, поддающиеся решению за полиномиальное время
23.4.2. Формальное определение предположения
23.4.3. Статус предположения, что P ≠ NP
*23.5. Гипотеза об экспоненциальном времени
23.5.1. Требуют ли NP-трудные задачи экспоненциального времени?
23.5.2. Сильная гипотеза об экспоненциальном времени
23.5.3. Нижние границы времени выполнения для простых задач
*23.6. NP-полнота
23.6.1. Редукции Левина
23.6.2. Самые трудные задачи в NP
23.6.3. Существование NP-полных задач
Задачи на закрепление материала
Задачи повышенной сложности
Глава 24. Практический пример: стимулирующий аукцион FCC
24.1. Перенацеливание беспроводного спектра
24.1.1. От телевидения к мобильным телефонам
24.1.2. Недавнее перераспределение спектра
24.2. Жадные эвристики для выкупа лицензий
24.2.1. Четыре временных упрощающих допущения
24.2.2. Засада со стороны взвешенного независимого множества
24.2.3. Жадные эвристические алгоритмы
24.2.4. Многоканальный случай
24.2.5. Засада со стороны раскраски графа
24.2.6. Решение к тестовому заданию 24.1
24.3. Проверка допустимости
24.3.1. Кодирование в качестве задачи выполнимости
24.3.2. Встраивание реберных ограничений
24.3.3. Задача о переупаковке
24.3.4. Трюк № 1: предварительные решатели (в поисках легкого выхода)
24.3.5. Трюк № 2: предварительная обработка и упрощение
24.3.6. Трюк № 3: портфель решателей задач SAT
24.3.7. Терпимость к отказам
24.3.8. Решение к тестовому заданию 24.2
24.4. Реализация в виде нисходящего тактового аукциона
24.4.1. Аукционы и алгоритмы
24.4.2. Пример
24.4.3. Переосмысление жадного алгоритма FCCGreedy
24.4.4. Пора получить компенсацию
24.5. Окончательный результат
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Эпилог: полевое руководство по разработке алгоритмов
Подсказки и решения
Книги Тима Рафгардена