Алгоритмы для задачи коммивояжёра, Куликов А., 2012.
Фрагмент из книги:
Задача о гамильтоновом цикле: проверить, есть ли в графе цикл, проходящий по каждой вершине ровно один раз.
Задача коммивояжёра: найти в данном полном взвешенном графе гамильтонов цикл минимального веса.
Периодически мы будем искать не цикл, а путь.
Применения: проектирование схем, планирование, сборка генома.
Сложность полного перебора: O(n!).
Неприближаемость.
Предположим, что существует а-приближённый алгоритм для задачи коммивояжёра.
Возьмём тогда произвольный (невзвешенный и необязательно полный) граф и присвоим всем его рёбрам вес 1.
Между любыми двумя не соединёнными ребром вершинами добавим ребро веса аn + 1.
Заметим теперь, что если в исходном графе существует гамильтонов цикл, то в новом графе существует гамильтонов цикл веса n.
Если же такого цикла в исходном графе нет, то самый лёгкий цикл в новом графе имеет вес хотя бы (аn + 1) + (n − 1) > аn.
ОГЛАВЛЕНИЕ.
1 Введение.
2 Эвристики.
Метод ветвей и границ.
Метод локального поиска.
3 Приближённые алгоритмы.
1.5-приближение для Metric-TSP.
Неприближаемость общего случая.
4 Точные алгоритмы.
Динамическое программирование.
Формула включений-исключений.
Матрица Татта и перманент.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы для задачи коммивояжёра, Куликов А., 2012 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по программированию :: программирование :: Куликов
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Олимпиадное программирование, Антти Л., 2018
- Карьера программиста, Лакман М.Г., 2020
- Алгоритмы и программы, Решение олимпиадных задач, Порублев И.Н., Ставровский А.Б., 2007
- Пионеры программирования, Диалоги с создателями наиболее популярных языков программирования, Бьянкуцци Ф., Уорден Ш., 2011
Предыдущие статьи:
- Алгоритмические трюки для программистов, Уоррен Г.С., 2003
- Зимняя школа по программированию, 2010
- Зимняя школа по программированию, 2014
- Язык С++, Основы программирования, Марапулец Ю.В., 2019