Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритмическая сложность

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

Различные варианты задачи коммивояжера (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга, способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.

Также известно, что при условии не существует алгоритма, который для некоторого полинома вычислял бы такие решения задачи коммивояжера, которые отличались бы от оптимального максимум на коэффициент.

Однако, существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность, лучшую чем 1,5 от оптимальной. По предположению, существует (неизвестная) константа, такая, что ни один алгоритм с полиномиальным временем не может гарантировать точность. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема поиска приблизительных решений задачи (PTAS).

Замкнутый и незамкнутый варианты задачи

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

Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину (предполагаем, что вершины исходного графа пронумерованы числами от 0 до, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину, определяются следующим образом:

  • при от до

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на больше.

Вопросы:

1. Какие задачи на графы вы знаете?

2. Что такое задача о Кёнигсбергских мостах?

3. Кто первый предложил решение этой задачи?

4. Возможно ли пройти по всем мостам не посетив ни один из них дважды?

5. Что такое задача о четырех красках?

6. Есть ли формальное доказательство того, что требуемая задачей раскраска возможна?

7. Правда ли, что на основе задачи были разработаны игры?

8. Что такое задача о коммивояжере?

9. Сколько вариантов задачи вы знаете?

10. К какому классу задач она относится (по временной сложности)?

<== предыдущая лекция | следующая лекция ==>
Асимметричная и симметричная задачи | Деятельность, направленная на сохранение, укрепление и улучшение здоровья
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 454; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.