fork download 
  1. #include <iostream>
  2. #include <random>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. random_device rd;
  9. mt19937 gen(rd());
  10.  
  11. const int TL = 100, PROB_DE_OCORRENCIA = 2, PRIZE = 400;
  12.  
  13. int get_row_size(int N);
  14. int get_col_size(int M);
  15. vector<vector<int>> create_graph(int N, int M);
  16. int get_evaluation(vector<vector<int>> graph, vector<pair<int, int>> solution);
  17. vector<vector<pair<int, int>>> genetic(vector<vector<int>> graph, int N, int M);
  18. vector<pair<int, int>> get_random_solution(int N, int M);
  19. pair<vector<pair<int, int>>, vector<pair<int, int>>> choose_parents(vector<vector<pair<int, int>>> population);
  20. vector<pair<int, int>> get_free_connections(vector<vector<int>> incomplete_graph, int N, int M);
  21. pair<vector<pair<int, int>>, vector<pair<int, int>>> crossover(vector<vector<pair<int, int>>> parents, int N, int M);
  22. vector<pair<int, int>> mutate(vector<pair<int, int>> solution, int N, int M);
  23.  
  24. int main() {
  25.   int N = 5, M = 5;
  26.  
  27.   vector<vector<int>> graph = create_graph(N, M);
  28.   for(int i = 0, par = 2; i < N; ++i, par += 2) {
  29.     for(int j = 0, impar = 1; j < M; ++j, impar += 2) {
  30.       cout<<graph[par][impar]<<' ';
  31.     }
  32.     cout<<'\n';
  33.   }
  34.   vector<vector<pair<int, int>>> ans = genetic(graph, N, M);
  35.   int count = 0;
  36.   for(vector<pair<int, int>> v : ans) {
  37.     cout<<"Solution "<<++count<<':'<<'\n';
  38.     for(pair<int, int> vv : v) {
  39.       cout<<vv.first<<' '<<vv.second<<'\n';
  40.     }
  41.     cout<<'\n';
  42.   }
  43.  
  44.   return 0;
  45. }
  46.  
  47. int get_row_size(int N) {
  48.   return 3 * N + 5;
  49. }
  50.  
  51. int get_col_size(int M) {
  52.   return 3 * M + 5;
  53. }
  54.  
  55. vector<vector<int>> create_graph(int N, int M) {
  56.   vector<vector<int>> graph(get_row_size(N), vector<int>(get_col_size(M)));
  57.   uniform_int_distribution<> get_random(1, 100);
  58.   for(int i = 0, par = 2; i < N; ++i, par += 2) {
  59.     for(int j = 0, impar = 1; j < M; ++j, impar += 2) {
  60.       graph[par][impar] = get_random(gen);
  61.     }
  62.   }
  63.   return graph;
  64. }
  65.  
  66. int get_evaluation(vector<vector<int>> graph, vector<pair<int, int>> solution) {
  67.   int somatorio_dos_pesos = 0;
  68.   set<int> vertices;
  69.   for(auto [vertice1, vertice2] : solution) {
  70.     somatorio_dos_pesos += graph[vertice1][vertice2];
  71.     vertices.emplace(vertice1), vertices.emplace(vertice2);
  72.   }
  73.   const int numero_de_vertices = vertices.size();
  74.   return numero_de_vertices * PRIZE - somatorio_dos_pesos;
  75. }
  76.  
  77. vector<vector<pair<int, int>>> genetic(vector<vector<int>> graph, int N, int M) {
  78.   uniform_int_distribution<> get_random(1, 100);
  79.   const int MAX = 5 * max(N, M);
  80.   const int HALF = MAX / 2;
  81.  
  82.   vector<vector<pair<int, int>>> generation;
  83.   for(int i = 0; i <= MAX; ++i) {
  84.     generation.push_back( get_random_solution(N, M) );
  85.   }
  86.   for(int i = 1, t = 1; t < TL; ++i, ++t) {
  87.     for(int j = 1; j <= HALF; ++j) {
  88.       const auto [parent1, parent2] = choose_parents( generation );
  89.       const vector<vector<pair<int, int>>> parents = {parent1, parent2};
  90.       auto [child1, child2] = crossover(parents, N, M);
  91.       // auto [child1, child2] = pair<vector<pair<int, int>>, vector<pair<int, int>>>{parents[0], parents[1]};
  92.  
  93.       if(get_random(gen) < PROB_DE_OCORRENCIA) {
  94.         child1 = mutate(child1, N, M);
  95.       }
  96.       if(get_random(gen) < PROB_DE_OCORRENCIA) {
  97.         child2 = mutate(child2, N, M);
  98.       }
  99.       generation.push_back(child1);
  100.       generation.push_back(child2);
  101.     }
  102.  
  103.     const auto sort_comparator = [&](vector<pair<int, int>> a, vector<pair<int, int>> b) -> bool {
  104.       return get_evaluation(graph, a) > get_evaluation(graph, b);
  105.     };
  106.  
  107.     sort(generation.begin(), generation.end(), sort_comparator);
  108.  
  109.     generation.resize( MAX );
  110.   }
  111.   return generation;
  112. }
  113.  
  114. vector<pair<int, int>> get_random_solution(int N, int M) {
  115.   vector<pair<int, int>> solution;
  116.   vector<int> free_verticesN, free_verticesM, vertex_used(max(get_row_size(N), get_col_size(M)), 0);
  117.  
  118.   for(int i = 1, val = 2; i < N; ++i, val += 2) {
  119.     free_verticesN.push_back(val);
  120.   }
  121.   for(int i = 0, val = 1; i < M; ++i, val += 2) {
  122.     free_verticesM.push_back(val);
  123.   }
  124.  
  125.   for(int i = 1; i <= min(N, M); ++i) {
  126.     uniform_int_distribution<> N_get_random(0, free_verticesN.size()-1);
  127.     uniform_int_distribution<> M_get_random(0, free_verticesM.size()-1);
  128.     const int random_index_n = N_get_random(gen);
  129.     const int random_index_m = M_get_random(gen);
  130.  
  131.     const int vertex1 = free_verticesN[random_index_n];
  132.     const int vertex2 = free_verticesM[random_index_m];
  133.  
  134.     solution.push_back({ vertex1, vertex2 });
  135.  
  136.     vertex_used[vertex1]++;
  137.     vertex_used[vertex2]++;
  138.     if(vertex_used[vertex1] == 2) free_verticesN.erase(free_verticesN.begin() + random_index_n);
  139.     if(vertex_used[vertex2] == 2) free_verticesM.erase(free_verticesM.begin() + random_index_m);
  140.   }
  141.   return solution;
  142. }
  143.  
  144. pair<vector<pair<int, int>>, vector<pair<int, int>>> choose_parents(vector<vector<pair<int, int>>> population) {
  145.   uniform_int_distribution<> get_random(0, population.size() - 1);
  146.   const int rand_parent1 = get_random(gen);
  147.   const int rand_parent2 = get_random(gen);
  148.   return { population[rand_parent1], population[rand_parent2] };
  149. }
  150.  
  151. vector<pair<int, int>> get_free_connections(vector<vector<int>> incomplete_graph, int N, int M) {
  152.  
  153.   vector<pair<int, int>> free_connections;
  154.  
  155.   for(int i = 0, par = 2; i < N; ++i, par += 2) {
  156.     for(int j = 0, impar = 1; j < M; ++j, impar += 2) {
  157.       if(incomplete_graph[i][j] == false) {
  158.         free_connections.emplace_back(par, impar);
  159.       }
  160.     }
  161.   }
  162.  
  163.   return free_connections;
  164. }
  165.  
  166. pair<vector<pair<int, int>>, vector<pair<int, int>>> crossover(vector<vector<pair<int, int>>> parents, int N, int M) {
  167.   //// Child 1 = Half(Parent1) + Half2(Parent2)
  168.   //// Child 2 = Half(Parent2) + Half2(Parent1)
  169.  
  170.   // probabilidade de troca = 50%;
  171.   uniform_int_distribution<> get_random(0, 1);
  172.   const int swap_ = get_random(gen);
  173.   if(swap_) {
  174.     swap(parents[0], parents[1]);
  175.   }
  176.  
  177.   vector<vector<vector<int>>> graph(2, vector<vector<int>>(get_row_size(N), vector<int>(get_col_size(M), false)));
  178.   vector<vector<pair<int, int>>> connections(2);
  179.   int num_of_connections[2] = {0};
  180.   const int HALF = min(N, M) / 2;
  181.  
  182.   for(int i = 0; i < HALF; ++i) {
  183.     for(int parent = 0; parent < 2; ++parent) {
  184.       const auto [vertex1, vertex2] = parents[parent][i];
  185.       const int child = parent;
  186.       graph[child][vertex1][vertex2] = true;
  187.       connections[child].emplace_back(vertex1, vertex2);
  188.       ++num_of_connections[child];
  189.     }
  190.   }
  191.   for(int i = HALF; i < min(N, M); ++i) {
  192.     for(int parent = 0; parent < 2; ++parent) {
  193.       const auto [vertex1, vertex2] = parents[parent][i];
  194.       const int child = parent;
  195.       if(graph[child][vertex1][vertex2] == false) {
  196.         graph[child][vertex1][vertex2] = true;
  197.         connections[child].emplace_back(vertex1, vertex2);
  198.         ++num_of_connections[child];
  199.       }
  200.     }
  201.   }
  202.  
  203.   vector<pair<int, int>> free_connections[2];
  204.   free_connections[0] = get_free_connections(graph[0], N, M);
  205.   free_connections[1] = get_free_connections(graph[1], N, M);
  206.  
  207.   for(int child = 0; child < 2; ++child) {
  208.     vector<int> vertex_used(max(get_row_size(N), get_col_size(M)));
  209.     while(num_of_connections[child] < min(N, M)) {
  210.       uniform_int_distribution<> get_random_index(0, free_connections[child].size()-1);
  211.       int random_index, vertex1, vertex2;
  212.       bool valid_edge = false;
  213.       while(valid_edge == false) {
  214.         random_index = get_random_index(gen);
  215.         pair<int, int> vertices = free_connections[child][random_index];
  216.         vertex1 = vertices.first, vertex2 = vertices.second;
  217.         if(vertex_used[vertex1] == false && vertex_used[vertex2] == false) {
  218.           connections[child].emplace_back(free_connections[child][random_index]);
  219.           valid_edge = true;
  220.           ++num_of_connections[child];
  221.         }
  222.         free_connections[child].erase(free_connections[child].begin() + random_index);
  223.       }
  224.     }
  225.   }
  226.  
  227.   return pair<vector<pair<int, int>>, vector<pair<int, int>>>(connections[0], connections[1]);
  228. }
  229.  
  230. vector<pair<int, int>> mutate(vector<pair<int, int>> solution, int N, int M) {
  231.   vector<vector<int>> graph(get_row_size(N), vector<int>(get_col_size(M), false));
  232.   for(auto [vertex1, vertex2] : solution) {
  233.     graph[vertex1][vertex2] = true;
  234.   }
  235.   vector<pair<int, int>> free_edges = get_free_connections(graph, N, M);
  236.  
  237.   uniform_int_distribution<> get_random_index_of_used_edges(0, solution.size()-1);
  238.   uniform_int_distribution<> get_random_index_of_free_edges(0, free_edges.size()-1);
  239.   const int random_index_of_used_edges = get_random_index_of_used_edges(gen);
  240.   const int random_index_of_free_edges = get_random_index_of_free_edges(gen);
  241.   solution.erase(solution.begin() + random_index_of_used_edges);
  242.   solution.emplace_back(free_edges[random_index_of_free_edges]);
  243.   return solution;
  244. }
  245.  
Success #stdin #stdout 0.06s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
94 42 41 93 35 
66 90 77 87 2 
44 2 77 74 21 
26 79 88 82 94 
96 29 42 54 59 
Solution 1:
6 9
2 5
10 3
8 1
4 1

Solution 2:
6 9
2 5
10 3
8 1
4 1

Solution 3:
6 9
2 5
10 3
8 1
4 1

Solution 4:
6 9
2 5
10 3
8 1
4 1

Solution 5:
6 9
2 5
10 3
8 1
4 1

Solution 6:
6 9
2 5
10 3
8 1
4 1

Solution 7:
6 9
2 5
10 3
8 1
4 1

Solution 8:
6 9
2 5
10 3
8 1
4 1

Solution 9:
6 9
2 5
10 3
8 1
4 1

Solution 10:
6 9
2 5
10 3
8 1
4 1

Solution 11:
6 9
2 5
10 3
8 1
4 1

Solution 12:
6 9
2 5
10 3
8 1
4 1

Solution 13:
6 9
2 5
10 3
8 1
4 1

Solution 14:
6 9
2 5
10 3
8 1
4 1

Solution 15:
6 9
2 5
10 3
8 1
4 1

Solution 16:
6 9
2 5
10 3
8 1
4 1

Solution 17:
6 9
2 5
10 3
8 1
4 1

Solution 18:
6 9
2 5
10 3
8 1
4 1

Solution 19:
6 9
2 5
10 3
8 1
4 1

Solution 20:
6 9
2 5
10 3
8 1
4 1

Solution 21:
6 9
2 5
10 3
8 1
4 1

Solution 22:
6 9
2 5
10 3
8 1
4 1

Solution 23:
6 9
2 5
10 3
8 1
4 1

Solution 24:
6 9
2 5
10 3
8 1
4 1

Solution 25:
6 9
2 5
10 3
8 1
4 1
https://ideone.com/AipHeN
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!