Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //230
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include<math.h>
- #include<vector>
- #include<climits>
- #include <queue>
- #include<string>
- #include <iomanip>
- #include <algorithm>
- #include <random>
- using namespace std;
- int n;
- struct gtip {
- vector <int> g;
- double f;
- };
- vector <gtip> pop(20);
- double put[31][31];
- gtip dirtyfuck(int x, int y)
- {
- gtip C;
- bool u[31]{ 0 };
- double h = 1 - (pop[x].f / (pop[x].f + pop[y].f));
- for (int i = 0; i < n; i++)
- {
- int j = i;
- double l = (double)(rand()) / RAND_MAX;
- if (l <= h)
- {
- while (u[pop[x].g[j]] == 1)
- {
- if (j == n - 1)
- j = 0;
- else
- j++;
- }
- C.g.push_back(pop[x].g[j]);
- u[pop[x].g[j]] = 1;
- }
- else
- {
- while (u[pop[y].g[j]] == 1)
- {
- if (j == n - 1)
- j = 0;
- else
- j++;
- }
- C.g.push_back(pop[y].g[j]);
- u[pop[y].g[j]] = 1;
- }
- }
- return C;
- }
- bool comp(gtip x, gtip y)
- {
- if (x.f < y.f)
- return true;
- return false;
- }
- double fitness(gtip C)
- {
- double s = 0;
- for (int i = 0; i < n - 1; i++)
- {
- s += put[C.g[i]][C.g[i + 1]];
- }
- s += put[C.g[0]][C.g[n-1]];
- return s;
- }
- gtip mut(gtip C)
- {
- int a1, a2;
- a1 = rand() % n;
- a2 = rand() % n;
- swap(C.g[a1], C.g[a2]);
- return C;
- }
- void genetic()
- {
- int c = 0;
- gtip det[191];
- for (int i = 0; i < 20; i++)
- for (int j = i + 1; j < 20; j++)
- {
- det[c] = dirtyfuck(i, j);
- det[c] = mut(det[c]);
- det[c].f = fitness(det[c]);
- c++;
- }
- det[c] = pop[0];
- sort(det, det + 191, comp);
- for (int i = 0; i < 20; i++)
- pop[i] = det[i];
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> n;
- srand(time(NULL));
- cout.precision(6);
- vector <pair<int, int>> v(n);
- for (int i = 0; i < n; i++)
- {
- cin >> v[i].first >> v[i].second;
- }
- for (int i = 0; i<n - 1; i++)
- for (int j = i + 1; j < n; j++)
- {
- int a1, a2;
- a1 = (v[i].first - v[j].first)*(v[i].first - v[j].first);
- a2 = (v[i].second - v[j].second)*(v[i].second - v[j].second);
- put[i][j] = sqrt(a1 + a2);
- put[j][i] = put[i][j];
- }
- for (int i = 0; i < 20; i++)
- {
- for (int j = 0; j < n; j++)
- {
- pop[i].g.push_back(j);
- }
- random_shuffle(pop[i].g.begin(), pop[i].g.end());
- }
- for (int i = 0; i < 20; i++)
- {
- pop[i].f = fitness(pop[i]);
- }
- for (int i = 0; i < 200; i++)
- {
- genetic();
- }
- cout << fixed << pop[0].f << endl;
- for (int i = 0; i < n; i++)
- cout << pop[0].g[i] + 1 << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement