\documentclass[11pt]{article}
\usepackage[utf-8]{inputenc}
\usepackage[T2A,T1]{fontenc}
\usepackage[russian]{babel}
%\usepackage{amsmath,amssymb,amsfonts}
\usepackage{amsmath,amssymb,amsfonts,textcomp}
\begin{document}
\fontencoding{T2A}\selectfont
\begin{titlepage}
\huge{\textbf{TSP - Traveling Salesman Problem\newline ЗК - Задача Коммивояжёра}}\newline\newline
\LARGE{Автор: Бродников Александр Петрович}\newline\newline
\LARGE{Email: chillugy@omsknet.ru}\newline\newline
\LARGE{Homepage: http://chillugy.narod.ru}\newline\newline
\LARGE{Date: 05 Nov 2006}
\end{titlepage}
\newpage
%\maketitle{}
%\title{Title Титул}
\section{Введение}
\par
\textbf{\textit{TSP (Traveling Salesman Problem) - ЗК (Задача Коммивояжёра)}} - одна из задач линейного программирования, принадлежащая к числу $\mathbf{NP}$-полных задач. Постановка задачи такова: имеется связный граф, ориентированный или неориентированный, из $\mathbf n$ вершин, соединённых рёбрами. Каждое из рёбер имеет числовую стоимость. Требуется построить маршрут (замкнутый обход), проходящий через каждую вершину графа строго по одному разу так, чтобы минимизировать общую суммарную стоимость маршрута. Предполагается, что хотя бы один замкнутый обход существует.

\section{Элементы теории}
\subsection{Классы эквивалентности}
\par
Если для каждого ребра, входящего в вершину $\mathbf{V_i}$, к стоимости этого ребра $\mathbf{\sigma_{ij}}$ прибавить величину $\mathbf{\epsilon_i}$, и для каждого ребра, исходящего из вершины $\mathbf{V_i}$, к стоимости добавить величину $\mathbf{\tau_i}$, то суммарная стоимость любого обхода увеличится на постоянную для всех обходов величину, т.е. $\mathbf{S_{new}=S_{old}+\epsilon_i+\tau_i}$. Это означает, что оптимальный обход не изменится, изменится только его стоимость на известную заранее величину, и вместо начальной задачи с тем же успехом можно искать решение задачи модифицированной. В случае симметричной матрицы стоимостей, т.е. неориентированного графа, обе добавляемых величины должны быть равны. Будем называть две индивидуальных симметричных $\mathbf{TSP}$-задачи со стоимостями $\mathbf{\sigma_{ij}}$ и $\mathbf{\hat\sigma_{ij}}$ эквивалентными, если существует такой вектор $\mathbf{E}$ добавленных стоимостей $\textbf{(термин!)}$, что $$\mathbf{\hat\sigma_{ij}=\sigma_{ij}+E_i+E_j}$$
\par
В несимметричном случае для эквивалентности задач должны существовать два вектора $\mathbf E$ и $\mathbf F$ добавленных стоимостей, таких, что
$$\mathbf{\hat\sigma_{ij}=E_i+\sigma_{ij}+F_j}$$
\par
Аналогично легко убедиться, что если для каждого ребра графа прибавить к его стоимости одну и ту же величину, то задача останется в этом же классе эквивалентности. Это позволяет считать минимальную стоимость ребра графа равной $0$ (слипшиеся точки). 
\newline
\par
Для ориентированного графа назовём функцию $\mathbf{Offset\left(i, \sigma_{in}, \sigma_{out}\right)}$ тернарной функцией или операцией смещения для вершины $\mathbf i$. Эта операция применима к каждому входящему в вершину $\mathbf{v_i}$ ребру и увеличивает его стоимость на $\mathbf{\sigma_{in}}$. Она же применима к каждому исходящему из вершины $\mathbf{v_i}$ ребру и увеличивает его стоимость на $\mathbf{\sigma_{out}}$. Величины $\mathbf{\sigma_{in}}$ и $\mathbf{\sigma_{out}}$ могут иметь любые значения и знаки. Для неориентированного графа (т.е. для графа с симметричной матрицей) операция смещения бинарна с двумя параметрами: $\mathbf{i}$ и $\mathbf{\sigma}$. Любая операция смещения оставляет задачу в том же классе эквивалентности.
\newline
\par
Множество индивидуальных задач $\mathbf{TSP}$ разделяется на смежные классы эквивалентных между собой задач. Возникает потребность развить теорию, найти в каждом классе экстремальные элементы, т.е. такие задачи, которые приводили бы к решению кратчайшим путём. В других ветвях математики такие элементы часто называются нормальными, каноническими, и т.д.
\newline
\par
Сразу можно заметить, что искать алгоритмы решения $\mathbf{TSP}$-задачи для графов с выполненным неравенством треугольника, или для планарных графов, вероятно, бессмысленно, и эти темы следует закрыть. Действительно, для любого графа $\mathbf{TSP}$-задачи с нарушениями неравенства треугольника можно построить такую ей эквивалентную, для которой это неравенство соблюдается. Добиться этого можно, просто прибавив к стоимости каждого ребра большую величину, например, равную максимальной стоимости ребра в первоначальном графе. Либо кропотливо модифицировать каждый проблемный треугольник, выполняя операцию с положительным вычисленным смещением для нужной вершины. Следует отметить, что неравенство треугольника устойчиво к положительным смещениям, и, значит, новых нарушений неравенства треугольника не возникнет.
\newline
\par
У планарного графа стоимость ребра равна его длине. Для любых четырёх вершин графа $\mathbf{A,B,C,D}$ с точностью до переименования вершин выполняется одно из двух равенств:
$$\mathbf{S_{\Delta BCD}=S_{\Delta ABC}+S_{\Delta ABC}+S_{\Delta ABD}}$$
$$\mathbf{S_{\Delta ABC}+S_{\Delta BCD}=S_{\Delta ABD}+S_{\Delta ACD}}$$
В этих формулах $\mathbf{S_{\Delta}}$ - площадь соответствующего треугольника, данную величину можно выразить через длины рёбер по формуле Герона, и тогда становится ясно, что у $\mathbf{TSP}$-задачи с планарным графом существует ей эквивалентная с непланарным графом.
\subsection{Нижняя оценка стоимости оптимального обхода}
\par
Дальнейшее изложение - только для неориентированных связных полных графов, $\mathbf{n\geqslant 4}$. 
\newline
\par
Если граф не полный, то можно превратить его в полный, приписав недостающим рёбрам достаточно большую стоимость, например, равную общей сумме всех стоимостей рёбер первоначального графа, либо присвоив специальное значение $\mathbf{+\infty}$ с естественными операциями сравнения и сложения.
\newline
\par
Для каждого графа $\mathbf{\Gamma}$ можно построить его подграф $\mathbf{\Gamma_{MST}}$ - Минимальное Остовное Дерево - $\mathbf{\left(Minimal\quad Spanning\quad Tree\right)}$. Этот подграф соединяет все вершины графа между собой, причём суммарная стоимость всех рёбер данного подграфа
$\mathbf{\Gamma_{MST}}$ минимальна. Если в графе $\mathbf{\Gamma}$ существуют рёбра равной стоимости, то подграф $\mathbf{\Gamma_{MST}}$, возможно, не единствен, но множества стоимостей рёбер, входящих в какой-либо подграф $\mathbf{\Gamma_{MST}}$, совпадают, и значит, суммарная стоимость одна и та же, хотя порёберный состав разных $\mathbf{\Gamma_{MST}}$ может быть различным.
\newline
\par
Пусть $\mathbf{\Gamma_{Opt}}$ - граф оптимального обхода.
Обозначим $\mathbf{S_{Opt}}$ - суммарная стоимость всех рёбер, входящих в оптимальный обход $\mathbf{\Gamma_{Opt}}$. Это есть цена решения индивидульной $\mathbf{TSP}$ - задачи. Таких обходов может быть несколько, с одной и той же величиной $\mathbf{S_{Opt}}$.
Обозначим, далее, $\mathbf{S_{MST}}$ - суммарная стоимость рёбер подграфа $\mathbf{\Gamma_{MST}}$,
$\mathbf{s_{OptMax}}$ - максимальная стоимость ребра в оптимальном обходе $\mathbf{\Gamma_{Opt}}$,
$\mathbf{s_{MSTMax}}$ - максимальная стоимость ребра в подграфе $\mathbf{\Gamma_{MST}}$.
\newline
\par
\textbf{Утверждение:}
$$\mathbf{S_{Opt}\geqslant S_{MST}+s_{MSTMax}}$$
\par
\textbf{Доказательство:}
Вынем из оптимального обхода $\mathbf{\Gamma_{Opt}}$ ребро с максимальной стоимостью $\mathbf{s_{OptMax}}$. Тогда получаем некоторый линейный подграф $\mathbf{\Gamma_{Ham}}$ исходного графа $\mathbf{\Gamma}$ - незамкнутый гамильтонов путь, проходящий через все вершины графа ровно по одному разу. Обозначим $\mathbf{S_{Ham}}$ - суммарную стоимость всех рёбер этого подграфа. Очевидно, что
$$\mathbf{S_{Opt}=S_{Ham}+s_{OptMax}}$$
$$\mathbf{S_{Ham}\geqslant S_{MST}}$$
\par
Затем вынем из подграфа $\mathbf{\Gamma_{MST}}$ ребро с максимальной стоимостью $\mathbf{s_{MSTMax}}$. Нет никаких проблем с неоднозначностью $\mathbf{MST}$. Тогда подграф $\mathbf{\Gamma_{MST}}$ распадётся на два собственных подграфа $\mathbf{\Gamma_1}$ и $\mathbf{\Gamma_2}$, каждый из которых является графом-деревом. В любом обходе первоначального графа $\mathbf{\Gamma}$ должны существовать по крайней мере два разных ребра, соединяющих подграфы $\mathbf{\Gamma_1}$ и $\mathbf{\Gamma_2}$. Стоимость любого из этих рёбер не ниже, чем $\mathbf{s_{MSTMax}}$. Очевидно, что
$$\mathbf{s_{OptMax}\geqslant s_{MSTMax}}$$
, так как принятие противоположного приводит к противоречию. Таким образом, первоначальное утверждение доказано. Приятная новость состоит в том, что эта нижняя оценка на самом деле достигается.
\subsection{Достаточный признак оптимальности}
Теперь можно сформулировать достаточный и легко вычисляемый признак оптимальности обхода:
\newline
\par
Если подграф $\mathbf{\Gamma_{MST}}$ является линейным графом и максимальная стоимость ребра $\mathbf{s_{MSTMax}}$ из этого графа равна стоимости ребра, замыкающего обход, то есть соединяющего концы линейного графа, то этот замкнутый обход будет оптимальным обходом первоначальной $\mathbf{TSP}$ - задачи.
\par
Доказательство очевидно из линейности $\mathbf{MST}$ и предыдущих рассуждений.
\section{Алгоритм}
Алгоритм решения $\mathbf{TSP}$ - задачи прост: нужно, исходя из первоначального графа $\mathbf{\Gamma}$, построить его подграф $\mathbf{\Gamma_{MST}}$, и затем последовательными векторами смещений привести $\mathbf{\Gamma_{MST}}$ к линейному графу, удовлетворяющему достаточному признаку оптимальности. Частных алгоритмов выбора векторов смещений существует достаточно много, и наилучший из них, по-видимому, ещё не найден. Тем не менее множество хороших алгоритмов уже получено. В файле $\mathbf{Avia.csv}$ приведена таблица дальностей полётов между $28$ городами СНГ. В файле $\mathbf{Airports.csv}$ находятся названия городов и финальный вектор смещений. В файле $\mathbf{Solution.csv}$ находится результирующий $\mathbf{\Gamma_{MST}}$. Все файлы $\mathbf{*.csv}$ - обычные текстовые файлы, их можно просмотреть в Блокноте или любом другом текством редакторе, либо загрузить в \textbf{Microsoft  Office Excel}.
\par
Общее число шагов, т.е. выборов вектора смещений, равно $56$. Бесполезно сравнивать это число с общим числом вариантов обхода - $$\mathbf{\frac{(n-1)!}{2}=\frac{27!}{2}}.$$ Время счёта - менее секунды, оно даже не измерялось, так как тестовая программа выполнялась в пошаговом режиме, и компьютер тратил время на перерисовку промежуточных таблиц. Сложность шага, т.е. выбора нового вектора смещений, примерно равна сложности пересортировки таблицы рёбер, т.е. $\mathbf{n^2\ln{n}}$. Сортировку таблицу рёбер можно применять, если $\mathbf{n}$ не очень велико. При больших значениях следует применять более быстрые алгоритмы, например, выбор из дерева. Это связано с тем, что подавляющее число ребёр фактически не принимает никакого участия в построении подграфа $\mathbf{\Gamma_{MST}}$. Было выполнено большое число тестовых расчётов для отладки алгоритмов, обычно $\mathbf{n}$ было в пределах $20$, но был и пример с $\mathbf{n=50}$. Стоимости рёбер были получены от датчика случайных чисел, что не есть хорошо, хотелось бы и реальных примеров. 
\section{Проверка оптимальности решения}
Проверка оптимальности несложна. Имея результирующий вектор смещений $\mathbf{\sigma[1:n]}$, необходимо выполнить для каждой $\mathbf{i}$-той вершины графа операцию $\mathbf{Offset\left(i,\sigma[i]\right)}$, отсортировать рёбра графа по возрастанию, построить подграф $\mathbf{\Gamma_{MST}}$ и убедиться, что он удовлетворяет достаточным условиям оптимальности.
\end{document} 
 
