SHARE
TWEET

Untitled

a guest Apr 24th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int main() {
  2.     std::default_random_engine generator;
  3.     std::normal_distribution<double> distribution(0, 100);
  4.  
  5.     for (int size = 2; size <= 14; ++size) {
  6.         for (int test = 1; test <= 100; ++test) {
  7.             std::cout << "size: " << size << std::endl << "test: " << test << std::endl;
  8.             ArcGraph *Graph = new ArcGraph(size);
  9.  
  10.             std::vector<float> x;
  11.             std::vector<float> y;
  12.  
  13.                 for (int i = 0 ; i < size; ++i) {  // генерируем координаты
  14.                     float x_coord = distribution(generator);
  15.                     float y_coord = distribution(generator);
  16.                     x.push_back(x_coord);
  17.                     y.push_back(y_coord);
  18.                 }
  19.  
  20.                 for (int i = 0; i < size; ++i) {
  21.                     for (int k = i + 1; k < size; ++k) {
  22.                         float dist = sqrt((x[i] - x[k]) * (x[i] - x[k]) + (y[i] - y[k]) * (y[i] - y[k]));
  23.                         Graph->AddEdge(i, k, dist);  // добавляем все ребра
  24.                     }
  25.             }
  26.  
  27.             float the_shortest_route = Graph->TheShortestRoute(); // кратчайший путь (перебором)
  28.  
  29.             MinSpanningTree *MSTGraph = new MinSpanningTree(size);
  30.             MSTGraph->BuildST(Graph);
  31.             float short_route = MSTGraph->ShortestRoute();
  32.  
  33.             //assert(the_shortest_route <= short_route);
  34.             //assert(short_route <= 2 * the_shortest_route);
  35.  
  36.             std::cout << std::fixed << std::setprecision(2) << "the shortest route length:  " << the_shortest_route << std::endl;
  37.  
  38.             std::cout << std::fixed << std::setprecision(2) << "found route length:         " << short_route << std::endl;
  39.  
  40.             std::cout << std::fixed << std::setprecision(2) << "ratio:                      " <<  short_route / the_shortest_route << std::endl;
  41.             std::cout << std::endl;
  42.  
  43.             delete Graph;
  44.             delete MSTGraph;
  45.         }
  46.         std::cout <<"-----------------------------------" << std::endl << std::endl;
  47.     }
  48.  
  49.     std:: cout << "All tests were passed successfully" << std::endl;
  50.  
  51.     return 0;
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top