Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <assert.h>
  5. #include <vector>
  6. #include <unordered_set>
  7. #include <ctime>
  8. #include <set>
  9. #include <limits>
  10. #include <random>
  11. #include <iomanip>
  12.  
  13. using std::vector;
  14. using std::set;
  15. const int inf = std::numeric_limits<int>::max();
  16. const double  lowest=std:: numeric_limits<double> :: min();
  17. struct IGraph {
  18.     virtual ~IGraph() {}
  19.  
  20.     virtual void AddEdge(int from, int to, double lenght) = 0;
  21.  
  22.     virtual int VerticesCount() const = 0;
  23.  
  24.     virtual void GetNextVertices(int v, std::vector<std::pair<int, double >> &next) const = 0;
  25.  
  26.     virtual void GetPrevVertices(int v, std::vector<std::pair<int, double >> &prev) const = 0;
  27.  
  28.     virtual double getweight(int from, int to) const {}
  29. };
  30.  
  31. class MatrixGraph : public IGraph {
  32. public:
  33.     explicit MatrixGraph(int count);
  34.  
  35.     MatrixGraph(const IGraph &graph) {};
  36.  
  37.     virtual ~MatrixGraph() {};
  38.  
  39.     // Добавление ребра от from к to.
  40.     virtual void AddEdge(int from, int to, double length);
  41.  
  42.     virtual int VerticesCount() const;
  43.  
  44.     virtual void GetNextVertices(int vertex, std::vector<std::pair<int, double>> &next) const;
  45.  
  46.     virtual void GetPrevVertices(int vertex, std::vector<std::pair<int, double >> &prev) const {};
  47.  
  48.     double getweight(int from, int to) const;
  49.  
  50. private:
  51.     int Vertices_number;
  52.     std::vector<std::vector<double>> matrix;
  53. };
  54.  
  55. MatrixGraph::MatrixGraph(int count) : Vertices_number(count), matrix(count, std::vector<double>(count, 0.0)) {}
  56.  
  57. void MatrixGraph::AddEdge(int from, int to, double length) {
  58.     matrix[from][to] = length;
  59.     matrix[to][from] = length;
  60. }
  61.  
  62. int MatrixGraph::VerticesCount() const { return Vertices_number; }
  63.  
  64. void MatrixGraph::GetNextVertices(int vertex, std::vector<std::pair<int, double>> &next) const {
  65.     for (int i = 0; i < Vertices_number; ++i) {
  66.         if (matrix[vertex][i] != 0) {
  67.             next.push_back(std::make_pair(i, matrix[vertex][i]));
  68.         }
  69.     }
  70. }
  71.  
  72. double MatrixGraph::getweight(int from, int to) const { return matrix[from][to]; }
  73.  
  74. void MST(const IGraph &graph, IGraph &result) {
  75.     vector<std::pair<int, double>> key(graph.VerticesCount(), std::pair<int, double>(inf, -1));
  76.     vector<bool> visited(graph.VerticesCount(), false);
  77.     set<std::pair<double, int>> queue;
  78.     key[0].second = 0;
  79.     for (int i = 0; i < graph.VerticesCount(); i++)
  80.         queue.emplace(std::pair<double, int>(key[i].second, i));
  81.     while (!queue.empty()) {
  82.         int v = queue.begin()->second;
  83.         queue.erase(queue.begin());
  84.         visited[v] = true;
  85.         vector<std::pair<int, double>> related;
  86.         graph.GetNextVertices(v, related);
  87.         for (const std::pair<int, double> &u : related) {
  88.             if ((!visited[u.first] and key[u.first].second > u.second)
  89.                 or key[u.first].second + 1 < lowest) {
  90.                 // Decreasing key
  91.                 queue.erase(std::pair<double, int>(key[u.first].second, u.first));
  92.                 key[u.first].first = v;
  93.                 key[u.first].second = u.second;
  94.                 queue.emplace(key[u.first].second, u.first);
  95.             }
  96.         }
  97.     }
  98.  
  99.     for (unsigned i = 1; i < graph.VerticesCount(); i++)
  100.         result.AddEdge(i, key[i].first, key[i].second);
  101. }
  102.  
  103. void DFS(const IGraph &Graph, int dot, std::vector<int> &tour, std::vector<bool> &visited) {
  104.     std::vector<std::pair<int, double>> vertices;
  105.     Graph.GetNextVertices(dot, vertices);
  106.     for (auto c: vertices) {
  107.         if (!visited[c.first]) {
  108.             visited[c.first] = true;
  109.             tour.push_back(c.first);
  110.             DFS(Graph, c.first, tour, visited);
  111.         }
  112.  
  113.     }
  114. }
  115.  
  116. void finding_min_matching( IGraph&MST, const IGraph&graph){std:: vector< int> nechet;
  117.     for (int i=0;i<MST.degrees.size();++i){if (MST.degrees[i]%2==1){nechet.push_back(i);}}
  118.     double sum=0;
  119.     for (int i=0;i+1<nechet.size();i+=2){
  120.         sum+=graph.getweight(nechet[i],nechet[i+1]);
  121.     }
  122.     double min_sum=sum;
  123.     std :: vector<int> permutation=nechet;
  124.     while (std :: next_permutation(nechet.begin(),nechet.end())){
  125.         double sum1=0;
  126.         for (int i=0;i+1<nechet.size();i+=2){
  127.             sum1+=graph.getweight(nechet[i],nechet[i+1]);
  128.         }
  129.         if (sum1<min_sum){min_sum=sum1;for(int k=0;k<nechet.size();++k){permutation[k]=nechet[k];}}
  130.     }
  131.     for (int i=0;i+1<nechet.size();i+=2){
  132.         MST.AddEdge(nechet[i],nechet[i+1],graph.getweight(nechet[i],nechet[i+1]));
  133.     }}
  134.                                                            
  135. double mintourLenMst(const IGraph &Graph) {
  136.     std::vector<int> tour;
  137.     MatrixGraph mst(Graph.VerticesCount());
  138.     MST(Graph, mst);
  139.     std::vector<bool> visited(Graph.VerticesCount(), false);
  140.     visited[0] = true;
  141.     DFS(mst, 0, tour, visited);
  142.     finding_min_matching( mst, Graph);
  143.     double Tour = Graph.getweight(tour[Graph.VerticesCount() - 2], 0) + Graph.getweight(0, tour[0]);
  144.     for (int i = 1; i < Graph.VerticesCount() - 1; i++) { Tour += Graph.getweight(tour[i - 1], tour[i]); }
  145.     return Tour;
  146. }
  147.  
  148. double getTourLen(const IGraph &graph, std::vector<int> &tour) {
  149.     double tour_weight = graph.getweight(tour[graph.VerticesCount() - 2], 0) + graph.getweight(tour[0], 0);
  150.     for (int i = 1; i < graph.VerticesCount() - 1; ++i) {
  151.         tour_weight += graph.getweight(tour[i - 1], tour[i]);
  152.     }
  153.     return tour_weight;
  154. }
  155.  
  156. void getting_all_permitations(int depth, std::vector<int> &tour, const IGraph &Graph, double &min_tour) {
  157.     if (depth == tour.size()) {
  158.         double tour1 = getTourLen(Graph, tour);
  159.         if (tour1 < min_tour) { min_tour = tour1; }
  160.         return;
  161.     }
  162.     for (int i = 0; i <= depth; ++i) {
  163.         std::swap(tour[i], tour[depth]);
  164.         getting_all_permitations(depth + 1, tour, Graph, min_tour);
  165.         std::swap(tour[i], tour[depth]);
  166.     }
  167. }
  168.  
  169. double Min_tour_len(const IGraph &graph) {
  170.     if (graph.VerticesCount() <= 1) {
  171.         return 0;
  172.     }
  173.     std::vector<int> tour;
  174.     for (int i = 1; i < graph.VerticesCount(); ++i) {
  175.         tour.push_back(i);
  176.     }
  177.     double min_tour = getTourLen(graph, tour);
  178.     getting_all_permitations(1, tour, graph, min_tour);
  179.     return min_tour;
  180. }
  181.  
  182. int main() {
  183.     std::cout << "Average_quality" << " " << "Deviation" << std::endl;
  184.     int times = 100;
  185.     double avg_quality = 0;
  186.     std::vector<double> qualities;
  187.     for (int number_of_vertices = 2; number_of_vertices < 11; number_of_vertices++) {
  188.         for(int z=0;z<times;++z){
  189.  
  190.         std::random_device rd;
  191.         std::mt19937 gen(rd());
  192.         std::normal_distribution<double> d;
  193.         std::vector<std::pair<double, double>> coordinates;
  194.         std::vector<double> for_coords(2 * number_of_vertices);
  195.         for (int i = 0; i < number_of_vertices; ++i) {
  196.             double x_coord;
  197.             x_coord = d(gen);
  198.             for_coords[i * 2] = x_coord;
  199.         }
  200.         for (int i = 0; i < number_of_vertices; ++i) {
  201.             double y_coord;
  202.             y_coord = d(gen);
  203.             for_coords[i * 2 + 1] = y_coord;
  204.         }
  205.         for (int i = 0; i < number_of_vertices * 2; i += 2) {
  206.             coordinates.emplace_back(std::make_pair(for_coords[i], for_coords[i + 1]));
  207.         }
  208.         MatrixGraph graph(number_of_vertices);
  209.         for (int i = 0; i < number_of_vertices; ++i) {
  210.             for (int j = i; j < number_of_vertices; ++j) {
  211.                 double distance = sqrt(
  212.                         (coordinates[i].first - coordinates[j].first) * (coordinates[i].first - coordinates[j].first)
  213.                         + (coordinates[i].second - coordinates[j].second) *
  214.                           (coordinates[i].second - coordinates[j].second));
  215.                 graph.AddEdge(i, j, distance);
  216.             }
  217.         }
  218.             double ans1 = Min_tour_len(graph);
  219.             double ans2 = mintourLenMst(graph);
  220.             double quality = ans2 / ans1;
  221.             avg_quality += quality;
  222.             qualities.push_back(quality);
  223.            
  224.         }
  225.         avg_quality = avg_quality / times;
  226.         double sum = 0;
  227.         for (int i = 0; i < times; ++i) {
  228.             sum += ((qualities[i] - avg_quality) * (qualities[i] - avg_quality));
  229.         }
  230.         double deviation = sqrt(sum / (times - 1));
  231.         std::cout << std::setprecision(10) << avg_quality << " " << deviation << std::endl;
  232.     }
  233.     return 0;
  234. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement