Изменения

'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости. == Формулировка задачи ==Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

 Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.

Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G G?= ?(V, E?E)</tex> <tex> N </tex>вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> pw(i, jj)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.

Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>S s = 0 </tex>.

min_{j: mask_j=1, (i, j) \in E} \begin{Bmatrix} pw(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\

Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Восстановить сам цикл несложно. Для этого воспользуемся соотношением Данное решение требует <tex> d[i][mask] = pO(i, j) + d[j][mask - {2^j] n}\times{n})</tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния памяти и <tex> i = 0 </tex>, <tex> mask = O({2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - }\times{n^2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 })</tex>времени.

Данное решение требует Для того, чтобы восстановить сам пут, воспользуемся соотношением <tex>Od[i][mask] = w({i, j) + d[j][mask - 2^n}\times{n})j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex> памяти и , <tex>O({mask = 2^n}\times{n- 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^2})j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex> времени.

for mask = 0 to mask = 2 ^ ** n - 1

if pw(i, j) существует d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ ** n] + w(i, j]);

writeData(); // запись данных, ответ хранится в print d[0][2 ^ ** n - 1];