Алгоритмы для задачи коммивояжёра, Куликов А., 2012

Алгоритмы для задачи коммивояжёра, Куликов А., 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 - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Куликов