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

По кнопкам "Купить бумажную книгу" или "Купить электронную книгу" можно купить в официальных магазинах эту книгу, если она имеется в продаже, или похожую книгу. Результаты поиска формируются при помощи поисковых систем Яндекс и Google на основании названия и авторов книги.

Наш сайт не занимается продажей книг, этим занимаются вышеуказанные магазины. Мы лишь даем пользователям возможность найти эту или похожие книги в этих магазинах.

Список книг, которые предлагают магазины, можно увидеть перейдя на одну из страниц покупки, для этого надо нажать на одну из этих кнопок.

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

Фрагмент из книги:
Задача о гамильтоновом цикле: проверить, есть ли в графе цикл, проходящий по каждой вершине ровно один раз.
Задача коммивояжёра: найти в данном полном взвешенном графе гамильтонов цикл минимального веса.
Периодически мы будем искать не цикл, а путь.
Применения: проектирование схем, планирование, сборка генома.
Сложность полного перебора: O(n!).

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


Неприближаемость.
Предположим, что существует а-приближённый алгоритм для задачи коммивояжёра.
Возьмём тогда произвольный (невзвешенный и необязательно полный) граф и присвоим всем его рёбрам вес 1.
Между любыми двумя не соединёнными ребром вершинами добавим ребро веса аn + 1.
Заметим теперь, что если в исходном графе существует гамильтонов цикл, то в новом графе существует гамильтонов цикл веса n.
Если же такого цикла в исходном графе нет, то самый лёгкий цикл в новом графе имеет вес хотя бы (аn + 1) + (n − 1) > аn.

ОГЛАВЛЕНИЕ.
1 Введение.
2 Эвристики.
Метод ветвей и границ.
Метод локального поиска.
3 Приближённые алгоритмы.
1.5-приближение для Metric-TSP.
Неприближаемость общего случая.
4 Точные алгоритмы.
Динамическое программирование.
Формула включений-исключений.
Матрица Татта и перманент.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы для задачи коммивояжёра, Куликов А., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги



Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 

Книги, учебники, обучение по разделам




Не нашёл? Найди:





2025-04-27 03:04:30