Задача коммивояжера (ЗК)

Условие. Заданы: конечное множество городов , расстояние между каждой парой городов , и число (граница) .

Вопрос. Существует ли маршрут, проходящий через все города из множества , длина которого не превосходит ?

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

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

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

Ограничение теории NP-полных задач только задачами распознавания обусловлено тем, что задачи распознавания имеют эквивалент, удобный для изучения методами теории вычислений ‑ формальный язык.

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

, где

, ,

Язык и ставится в соответствие задаче .

Индивидуальную задачу коммивояжера можно описать с помощью алфавита: .

При кодировании задачи коммивояжера сначала записывается размерность задачи, потом разделитель «двойной слэш», потом матрица расстояний (по строкам: разделитель между элементами ‑ «слэш»), потом разделитель «двойной слэш», число .

При использовании представленной схемы кодирования задача коммивояжера из примера 6.1 главы 6 представляется следующей цепочкой символов (словом):

4// /4/1/8//4/ /3/7//1/3/ /5//8/7/5/ //15.

Длина слова (в данном примере ‑ 41) для кодирования индивидуальной задачи называется длиной входа и существенно зависит от выбранной схемы кодирования.

Считаем, что в качестве схемы кодирования используется «разумная» схема, характеризующуюся, с одной стороны, сжатостью (нет лишней информации), а с другой стороны, декодируемостью ‑ возможностью восстановления по формальной записи индивидуальной задачи.

При применении формальной теории NP-полноты к задачам распознавания говорят, что некоторый результат имеет место для задачи при схеме кодирования , если этот результат имеет место для языка .

Если сформулировать в терминах языка любое новое понятие или свойство, оно фактически не будет зависеть от способа кодирования, т.е., если и ‑ любые две разумные схемы кодирования задачи , то рассматриваемое свойство языков и выполняется или не выполняется для них одновременно.

Это свойство позволяет, не указывая явно схемы кодирования, (неформально) говорить о том, что рассматриваемое свойство для задачи выполняется или не выполняется. Однако при этом подразумевается, что в случае необходимости можно указать такую схему кодирования , что рассматриваемое свойство выполняется для языка .

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

Определение 5.2. Функция полиномиально эквивалентна длине входа индивидуальной задачи, получаемой при любой разумной схеме кодирования, если для любой разумной схемы кодирования задачи существует два полинома и , обладающие свойством: