4635
правок
Задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача коммивояжера''' (''[[Travelling salesman problem]]'') | '''Задача коммивояжера''' (''[[Travelling salesman problem]]'') — Коммивояжер должен посетить каждый из <math>n</math> городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти ''[[кратчайший путь|кратчайший маршрут]]'', зная [[расстояние между вершинами|расстояния]] между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном [[взвешенный граф|взвешенном графе]] требуется найти [[гамильтонов цикл]] (или [[гамильтонова цепь|цепь]]) наименьшего [[вес цикла|веса]] ([[длина цепи|длины]]). | ||
Данная задача является [[NP-Полная задача|''<math>\mathcal{NP}</math>-полной]]''; для ее решения не | Данная задача является [[NP-Полная задача|''<math>\mathcal{NP}</math>-полной]]''; для ее решения не | ||
| Строка 7: | Строка 7: | ||
связи с чем она играет роль эталонной задачи. | связи с чем она играет роль эталонной задачи. | ||
==Литература== | ==Литература== | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||