Алгоритм

Алгоритм решения $\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}$ - обычные текстовые файлы, их можно просмотреть в Блокноте или любом другом текством редакторе, либо загрузить в Microsoft Office Excel.

Общее число шагов, т.е. выборов вектора смещений, равно $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}$. Стоимости рёбер были получены от датчика случайных чисел, что не есть хорошо, хотелось бы и реальных примеров.

Используются технологии uCoz