Задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача коммивояжера''' (''Travelling salesman problem'') - Коммивояжер должен посетить ка...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача коммивояжера''' (''Travelling salesman problem'') - | '''Задача коммивояжера''' (''[[Travelling salesman problem]]'') - Коммивояжер должен посетить каждый из <math>n</math> городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти ''[[кратчайший маршрут]]'', зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном [[взвешенный граф|взвешенном графе]] требуется найти [[гамильтонов цикл]] (или [[гамильтонова цепь|цепь]]) наименьшего [[вес цикл|веса]] ([[длина цепи|длины]]). | ||
Коммивояжер должен посетить каждый из <math>n</math> городов по одному | |||
разу, выехав из некоторого из этих городов и вернувшись в | |||
него же. Требуется найти ''кратчайший маршрут'', зная расстояния | |||
между каждой парой городов. Математическая постановка этой | |||
задачи состоит в следующем: в полном взвешенном графе | |||
требуется найти гамильтонов цикл (или цепь) наименьшего веса | |||
(длины). | |||
Данная задача является ''NP-полной''; для ее решения не | Данная задача является ''<math>\mathcal{NP}</math>-полной''; для ее решения не | ||
известно эффективного (''полиномиального'') алгоритма. | известно эффективного (''полиномиального'') алгоритма. | ||
Важность этой задачи | Важность этой задачи | ||
Версия от 16:26, 20 октября 2009
Задача коммивояжера (Travelling salesman problem) - Коммивояжер должен посетить каждый из [math]\displaystyle{ n }[/math] городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) наименьшего веса (длины).
Данная задача является [math]\displaystyle{ \mathcal{NP} }[/math]-полной; для ее решения не известно эффективного (полиномиального) алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи, в связи с чем она играет роль эталонной задачи.
Литература
[Лекции],
[Кристофидес]