Аноним

Задача коммивояжера: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Задача коммивояжера''' (''Travelling salesman problem'') - Коммивояжер должен посетить ка...)
 
Нет описания правки
Строка 1: Строка 1:
'''Задача коммивояжера''' (''Travelling salesman problem'') -  
'''Задача коммивояжера''' (''[[Travelling salesman problem]]'') - Коммивояжер должен посетить каждый из <math>n</math> городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти ''[[кратчайший маршрут]]'', зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном [[взвешенный граф|взвешенном графе]] требуется найти [[гамильтонов цикл]] (или [[гамильтонова цепь|цепь]]) наименьшего [[вес цикл|веса]] ([[длина цепи|длины]]).
Коммивояжер должен посетить каждый из <math>n</math> городов по одному
разу, выехав из некоторого из этих городов и вернувшись в
него же. Требуется найти ''кратчайший маршрут'', зная расстояния
между каждой парой городов. Математическая постановка этой
задачи состоит в следующем: в полном взвешенном графе
требуется найти гамильтонов цикл (или цепь) наименьшего веса
(длины).


Данная задача является ''NP-полной''; для ее решения не
Данная задача является ''<math>\mathcal{NP}</math>-полной''; для ее решения не
известно эффективного (''полиномиального'') алгоритма.
известно эффективного (''полиномиального'') алгоритма.
Важность этой задачи
Важность этой задачи