Лістинг програми розв’язку задачі комівояжера

#pragma comment (linker, "/STACK:16777216")

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <algorithm>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <cstring>

#include <numeric>

#include <complex>

#include <string>

#include <ctime>

 

using namespace std;

 

typedef long long LL;

typedef unsigned long long ULL;

typedef pair <int, int> pnt;

 

 

#define FI(i,a) for (int i=0; i<(a); ++i)

#define FOR(i,s,e) for (LL i=(s); i<(e); ++i)

#define MEMS(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define mp make_pair

#define ALL(a) a.begin(),a.end()

#define V(t) vector < t >

#define sz size()

#define MAX(a,b) ((a)>(b)?(a):(b))

#define MIN(a,b) ((a)<(b)?(a):(b))

#define ABS(a) ((a)>(0)?(a):(-(a)))

 

#define dout(a) cerr << a << endl

#define sout(a) cerr << a << " "

 

const double pi = 3.14159265358979323846264338327950288419716939937511;

const double eps = 1e-11;

//*

char ch_ch_ch[1<<20];

string gs() {scanf("%s",ch_ch_ch); return string(ch_ch_ch);}

string gl() {gets(ch_ch_ch); return string(ch_ch_ch);}

inline int gi() {int x; scanf("%d",&x); return x;}

//*/

 

const int inf = 1000000000;

 

// code starts here

 

int iterNumber = 80;

int populationSize = 200;

const int bestToSelect = 30;

double mutationProbability = 0.2;

const double crossoverProbability = 1.0;

const double genomeWinningProbability = 1.0;

 

typedef V(int) Genome;

typedef V(Genome) Population;

 

 

V(V(double)) adj;

 

inline double pathLength(Genome v)

{

v.pb(v[0]);

double res = 0;

FI(i,(int)v.sz-1) res+=adj[v[i]][v[i+1]];

return res;

}

 

 

inline double fitness(Genome v)

{

return -pathLength(v);

}

 

bool revSortByFitness(const Genome &a, const Genome &b)

{

return fitness(a) > fitness(b);

}

 

 

inline void outPath(Genome v)

{

FI(i,v.sz) printf("%d -> ",v[i]);

printf("%d\n",v[0]);

}

 

inline void printInfo(int iteration, Population pop)

{

sort(ALL(pop),revSortByFitness);

printf("\nGeneration #%d\n",iteration);

double av = 0;

FI(i,pop.sz) av += pathLength(pop[i]);

av/=pop.sz;

printf("Average path length: %lf\n",av);

printf("Best path length: %lf\n",pathLength(pop[0]));

printf("Best path: "); outPath(pop[0]);

 

}

 

Population generateRandomPopulation(int n, int cnt)

{

Population pop(cnt);

Genome g(n);

FI(i,n) g[i] = i;

FI(i,cnt) {random_shuffle(ALL(g)); pop[i] = g;}

return pop;

}

 

inline Genome crossover(Genome a, Genome b)

{

Genome c(a.sz,0);

int pbeg = 0, pend = c.sz-1, itNum = 0;

int pA = pbeg, pB = pend;

bool *inherited = new bool[c.sz+1];

FI(i,c.sz+1) inherited[i]=0;

while (pbeg<=pend)

{

if (itNum & 1)

{

while (pB >= 0 && inherited[b[pB]]) pB--;

if (pB >= 0) {c[pend--] = b[pB]; inherited[b[pB]] = 1;}

} else

{

while (pA < a.sz && inherited[a[pA]]) pA++;

if (pA < a.sz) {c[pbeg++] = a[pA]; inherited[a[pA]] = 1;}

}

itNum^=1;

}

return c;

}

 

inline Population doCrossover(Population pop)

{

Population newPop = pop;

FI(i,pop.sz)

newPop.push_back(crossover(pop[i],pop[rand()%pop.sz]));

return newPop;

}

 

inline void mutate(Genome &v)

{

int p1 = rand()%v.sz;

int p2;

do {p2 = rand()%v.sz;

} while (p2==p1);

int val = v[p1];

for (int i = p1; i!=p2; i=(i+1)%v.sz) v[i] = v[(i+1)%v.sz];

v[p2] = val;

 

}

 

inline Population doMutation(Population pop)

{

FI(i,pop.sz) if ((rand()%10000)/10000.0 < mutationProbability)

mutate(pop[i]);

return pop;

}

 

inline Genome winner(Genome a, Genome b)

{

if (fitness(a) < fitness(b)) swap(a,b);

return a;

}

 

inline Population doSelection(Population pop)

{

sort(ALL(pop),revSortByFitness);

Population newPop;

 

/* simple selection (the best half)

FI(i,populationSize) newPop.push_back(pop[i]);

return newPop; //*/

 

FI(i,bestToSelect)

newPop.push_back(pop[i]);

int pos = bestToSelect;

FOR(i,bestToSelect,populationSize)

{

if (pos+1>=pop.sz) pos = 0;

newPop.push_back(winner(pop[pos],pop[pos+1]));

pos+=2;

}

 

return newPop;

}

 

Genome geneticSolve(V(V(double)) a, int n, int iterNumber)

{

printf("\nEVOLUTION STARTS...\n");

adj = a;

Population population = generateRandomPopulation(n,populationSize);

FI(it,iterNumber)

{

population = doCrossover(population);

population = doMutation(population);

population = doSelection(population);

printInfo(it,population);

}

printf("\nEND OF EVOLUTION\n");

sort(ALL(population),revSortByFitness);

return population[0];

}

 

void solution()

{

clock_t beg_time = clock();

 

/*cout << 30 << endl;

V(int) dist(30);

FI(j,30) dist[j] = min(j,30-j);

FI(i,30) {FI(j,30) printf("%d ",dist[(j+30-i)%30]); printf("\n");}

return;*/

 

printf("Enter population size: ");

cin >> populationSize;

printf("Enter mutation probability: ");

cin >> mutationProbability;

printf("Enter generations count: ");

cin >> iterNumber;

 

freopen("in.txt","r",stdin);

freopen("out.txt","w",stdout);

 

V(V(double)) a;

int n;

cin >> n;

a.resize(n, V(double)(n,0));

FI(i,n) FI(j,n) cin >> a[i][j];

V(int) res = geneticSolve(a,n,iterNumber);

 

printf("FINAL RESULT:\nLength: %lf\n",pathLength(res));

FI(i,n) printf("%d -> ",res[i]);

printf("%d\n",res[0]);

 

fprintf(stdout,"*** Time: %.3lf ***\n",1.0*(clock()-beg_time)/CLOCKS_PER_SEC);

 

 

}

// code ends here

 

int main(int argc, char** argv)

{

 

#ifdef TYTKO_ACM

// freopen("in.txt","r",stdin);

// freopen("in.txt", "w", stdout);

 

#else

// freopen("in.txt","r",stdin);

// freopen("out.out", "w", stdout);

// freopen("elect.in", "r", stdin);

#endif

 

solution();

 

#ifdef TYTKO_ACM

 

#endif

return 0;

}