Решение задачи коммивояжера c использованием генератора перестановок

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

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

Математическая модель задачи может быть записана следующим образом:

 

 

где – неизвестные (номера выбранных городов), которые требуется найти.

Решением задачи будет вектор . Каждый элемент этого вектора может принимать целое значение из отрезка . При этом все значения должны быть разными.

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

На рис. 6 изображена схема решения задачи коммивояжера с применением генератора перестановок. Задача решается для пяти городов.

 

Рис. 6. Схема решения задачи коммивояжера

 

Расстояние между городами задается следующей матрицей

 

 

 

Элемент матрицы определяет расстояние между городами и где Факт отсутствия пути из города в город обозначается значением (бесконечность) соответствующего элемента.

Следует отметить следующие два момента, прежде чем будет пояснена схема на рис. 6:

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

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

На рис. 6 в качестве стартового города выбран город с номером . Поэтому перебор маршрутов осуществляется для городов с номерами 1, 2, 3, 4.

Левая часть схемы на рис. 6 практически идентична левой части схемы на рис. 1. Главное отличие заключается в том, что в качестве исходного массива выбран Причем перестановкам подлежит только внутренняя, заключенная между нулями, часть исходного массива. В остальном принцип построения перестановок тот же, что и на рис 1.

В правой части схемы изображены все возможные кольцевые маршруты, которые образованы из исходного массива путем перестановок всех, кроме обрамляющих нулей, элементов. Количество маршрутов равно количеству перестановок из четырех городов. Для каждого маршрута в округлой рамке указана длина. Длина кольцевых маршрутов, для которых не могут быть построены в силу отсутствия пути хотя бы между одной парой городов, на схеме обозначена символом Оптимальный маршрут длиной единиц выделен затемненной рамкой.

На рис. 7 и 8 представлен пример реализации на C++ функции salesman, вычисляющей оптимальный кольцевой маршрут коммивояжера. Функция имеет два входных параметра: n (количество городов) и d(двумерный массив размерностью n на n, содержащий элементы матрицы расстояний), а также один возвращаемый параметр r(массив размерностью n, содержащий оптимальный маршрут).

 

//-- Salesman.h // -- решение задачи коммивояжера перебором вариантов #define INF 0x7fffffff// бесконечность #include "Combi.h" int salesman (// функция возвращает длину оптимального маршрута int n,// [in] количество городов const int *d,// [in] массив [n*n] расстояний int *r// [out] массив [n] маршрут 0 x x x x );

 

Рис. 7. Функция salesman, решающая задачу коммивояжера

// -- Salesman.cpp #include "stdafx.h" #include "Salesman.h" int sum (int x1, int x2)// суммирование с учетом бесконечности { return (x1 == INF || x2 == INF)? INF: (x1 + x2); }; int* firstpath(int n)// формирование 1го маршрута 0,1,2,..., n-1, 0 { int *rc = new int[n+1]; rc[n] = 0; for (int i = 0; i < n; i++) rc[i] = i; return rc; }; int* source(int n)// формирование исходного массива 1,2,..., n-1 { int *rc = new int[n-1]; for (int i = 1; i < n; i++) rc[i-1] = i; return rc; }; void copypath(int n, int *r1, const int *r2)// копировать маршрут { for (int i = 0; i < n; i++) r1[i] = r2[i]; }; int distance(int n, int *r, const int *d)// длина маршрута { int rc = 0; for (int i = 0; i < n-1; i++) rc = sum(rc, d[r[i]*n+r[i+1]]); return sum (rc, d[r[n-1]*n + 0]);//+последняя дуга (n-1,0) }; void indx(int n, int *r, const int *s, const short *ntx) { for (int i = 1; i < n; i++) r[i] = s[ntx[i-1]];} int salesman ( int n,// [in] количество городов const int *d,// [in] массив [n*n] расстояний int *r// [out] массив [n] маршрут 0 x x x x ) { int *s = source(n), *b = firstpath(n), rc = INF, dist = 0; combi::permutation p(n-1); int k = p.getfirst(); while (k >= 0)// цикл генерации перестановок { indx(n, b, s, p.sset);// новый маршрут if ((dist = distance(n,b,d)) < rc) { rc = dist; copypath(n,r,b); } k = p.getnext(); }; return rc; }

 

Рис. 8. Реализация функции salesman

 

В функции salesmanприменяется генератор перестановок (combi::permutation). Кроме того она вызывает шесть вспомогательных функций: indx (формирование перестановки городов на основе массива идексов), distance(вычисление длины кольцевого маршрута), copypath(копирование маршрута), source (формирование исходного массива), firstpath(формирование первого маршрута) и sum (суммирование двух чисел с учетом того, что одно из них может быть равно бесконечности).

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

На рис. 9 и 10 приведен пример вызова функции salesmanдля решения задачи с исходными данными к схеме на рис. 6.

 

// --- main #include "stdafx.h" #include <iostream> #include <iomanip> #include "Salesman.h" #define N 5 int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int d[N][N] = {//0 1 2 3 4 { 0, 45, INF, 25, 50},// 0 { 45, 0, 55, 20, 100},// 1 { 70, 20, 0, 10, 30},// 2 { 80, 10, 40, 0, 10},// 3 { 30, 50, 20, 10, 0}};// 4 int r[N];// результат int s = salesman ( N,// [in] количество городов (int*)d,// [in] массив [n*n] расстояний r// [out] массив [n] маршрут 0 x x x x ); std::cout<<std::endl<<"-- Задача коммивояжера -- "; std::cout<<std::endl<<"-- количество городов: "<<N; std::cout<<std::endl<<"-- матрица расстояний : "; for(int i = 0; i < N; i++) { std::cout<<std::endl; for (int j = 0; j < N; j++) if (d[i][j]!= INF) std::cout<<std::setw(3)<<d[i][j]<< " "; else std::cout<<std::setw(3)<<"INF"<<" "; } std::cout<<std::endl<<"-- оптимальный маршрут: "; for(int i = 0; i < N; i++) std::cout<<r[i]<<"-->"; std::cout<<0; std::cout<<std::endl<<"-- длина маршрута : "<<s; std::cout<<std::endl; system("pause"); return 0; }

 

Рис. 9. Пример решения задачи коммивояжера

 

 

Рис. 10. Результат выполнения программы, представленной на рис. 4.9

 

На рис. 11 представлена программа, позволяющая оценить продолжительность решения задачи коммивояжера в зависимости от количества городов.

 

// -- main #include "stdafx.h" #include "Auxil.h" #include <iostream> #include <iomanip> #include <time.h> #include "Salesman.h" #define SPACE(n) std::setw(n)<<" " #define N 12 int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int d[N*N+1], r[N]; auxil::start(); for(int i = 0; i <= N*N; i++) d [i] = auxil::iget(10,100); std::cout<<std::endl<<"-- Задача коммивояжера -- "; std::cout<<std::endl<<"-- количество ------ продолжительность -- "; std::cout<<std::endl<<" городов вычисления "; clock_t t1, t2; for (int i = 7; i <= N; i++) { t1 = clock(); salesman (i, (int*)d, r); t2 = clock(); std::cout<<std::endl<<SPACE(7)<<std::setw(2)<<i <<SPACE(15)<<std::setw(5)<<(t2-t1); } std::cout<<std::endl; system("pause"); return 0; }

 

Рис. 11. Вычисление продолжительности решения задачи коммивояжера при разном количестве городов

 

В программе применяются функции auxil::start и auxil::iget, позволяющие сгенерировать расстояния между городами случайным образом, которые берутся из первой лабораторной работы.

На рис. 12 приведен результат выполнения программы, представленной на рис. 11, а на рис. 13 изображен график, построенный по этим результатам.

 

 

 

Рис. 12. Результат выполнения программы, представленной на рис. 11

 

Зависимость продолжительности вычисления
от количества городов
Количество городов
Продолжительность
вычисления, с

 

Рис. 13. Зависимость продолжительности вычисления функции salesman от значения параметра n

 

Вид графика на рис. 4.13 вполне согласуется с оценкой сложности алгоритма генерации перестановок элементов.

Сложность