Задача коммивояжёра есть NP-полная задача[2] . Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

Назовём языком множество слов над алфавитом Σ. Задачей здесь является определение того, принадлежит данное слово языку или нет. Язык L ₁ называется сводимым (по Карпу) к языку L ₂ , если существует функция, , вычислимая за полиномиальное время, обладающая следующим свойством: f(x) принадлежит L ₂ тогда и только тогда, когда x принадлежит L ₁ . Язык L ₂ называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден и при этом сам лежит в классе NP. Таким образом, если будет найден алгоритм, решающий хоть одну NP-полную задачу за полиномиальное время, все NP-задачи будут лежать в классе P.

Вернемся к задаче коммивояжера.

Математическая модель.

Исходные параметры модели.

Пусть i=0,1,2,...,m - номера городов, i=0 - номер выделенного города (начало и окончание маршрута). Обозначим через R=r(i,j) - (m+1)(m+1) матрицу расстояний, элемент которой r(i,j) - расстояние между городом с номером i и городом с номером j.

Варьируемые параметры модели.

Обозначим через X=x(i,j) - (m+1)(m+1) матрицу неизвестных, элемент которой x(i,j) =1, если коммивояжер из города с номером i переедет в город с номером j, x(i,j) = 0, в противном случае; u(i) - специальные переменные, i=1,2,...m.

Ограничения математической модели.

x(i,j) =1, j=1,2,...,m, (1)

x(i,j) =1, i=1,2,...,m, (2)

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, ij., (3)

x(i,j) {0,1}. (4)

Здесь условия (1) означают, что коммивояжер ровно один раз въедет в каждый город (кроме города с номером 0); условия (2) означают, что коммивояжер ровно один раз выедет из каждого города (кроме города с номером 0), ограничения (3) означают существование лишь одного цикла, начинающегося в городе с номером 0, проходящего через все города и завершающегося в городе с номером 0; ограничения (4) являются естественными условиями на введенные переменные.

Покажем, что условия (3) являются необходимыми и достаточными условиями существования лишь одного цикла.

Действительно, пусть это не так и найдется подцикл с числом городов k<m, не проходящий через город с номером 0. Складывая все неравенства (3) при условиях, что x(i,j)=1 по городам подцикла, получим mk (m-1)k (все u(i) и u(j) взаимно уничтожаются), что противоречит существованию подцикла длины k<m.

С другой стороны, покажем, что для цикла, проходящего через все города, начинающегося и заканчивающегося в городе с номером 0, найдутся величины u(i), удовлетворяющие условиям (3).

Положим u(i)=p, если город с номером i будет посещен коммивояжером p-ым по порядку, p=1,2,...,m.

Пусть x(i,j) = 0. Тогда условия (3) примут вид:

u(i) - u(j) m-1, что верно, так как p<m+1 и p>0.

Пусть x(i,j) = 1. Тогда, так как если u(i) = p, то u(j)=p+1 (это следует из того, что город с номером j будет следующим в маршруте коммивояжера после города с номером i). Получим:

u(i) - u(j) + m x(i,j) = p - (p+1) +m = m - 1, что и доказывает правомочность присутствия в модели ограничений (3).

Постановка оптимизационной задачи.

Критерий оптимальности для задачи коммивояжера имеет вид:

F(X)= r(i,j) x(i,j) min . (5)

Задача (1) - (5) называется задачей коммивояжера или задачей бродячего торговца.

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

Задача выполнимости булевых формул. Задача выполнимости булевых формул (SAT или ВЫП) — задача распознавания, важная для теории вычислительной сложности.

Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И ), (ИЛИ ) и (HE ). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной.

Согласно теореме Кука, доказанной Стивеном Куком в 1971-м году, проблема SAT NP-полна.