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

Задача коммивояжера (посмотреть исходный код)

Нет изменений в размере , 20 октября 2009

нет описания правки

4194

правки

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