API tools faq
paste
Advertisement
shamiul93

TSP.cpp

shamiul93
Jan 20th, 2019
106
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.54 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. //#define NN_SIMPLE_TEST 0
  4. //#define NN_RANDOM_TEST 1
  5. #define TWO_OPT_TEST 2
  6.  
  7. using namespace std;
  8. #define MAX 105
  9.  
  10. struct Point {
  11. double x;
  12. double y;
  13.  
  14. Point() {
  15.  
  16. }
  17.  
  18. Point(double a, double b) {
  19. x = a;
  20. y = b;
  21. }
  22.  
  23. double deg2rad(double deg) {
  24. return deg * (3.14159 / 180);
  25. }
  26.  
  27.  
  28. double getDistanceFromLatLonInKm(double lat1, double lon1, double lat2, double lon2) {
  29. double R = 6371; // Radius of the earth in km
  30. double dLat = deg2rad(lat2 - lat1); // deg2rad below
  31. double dLon = deg2rad(lon2 - lon1);
  32. double a = sin(dLat / 2.0) * sin(dLat / 2.0) +
  33. cos(deg2rad(lat1)) * cos(deg2rad(lat2)) * sin(dLon / 2) * sin(dLon / 2);
  34. double c = 2 * atan2(sqrt(a), sqrt(1 - a));
  35. double d = R * c; // Distance in km
  36. return d;
  37. }
  38.  
  39.  
  40. double dist(Point other) {
  41. return getDistanceFromLatLonInKm(x, y, other.x, other.y);
  42. // return hypot(x - other.x, y - other.y);
  43. }
  44. };
  45.  
  46. int n;
  47. Point pt[MAX];
  48. bool Vis[MAX];
  49. vector<int> Tour;
  50. int bestStartNNSimple;
  51.  
  52.  
  53. class distAndPoint {
  54. public:
  55. Point p;
  56. int d;
  57. int realIdx;
  58.  
  59. distAndPoint() {
  60.  
  61. }
  62.  
  63. distAndPoint(Point pp, int x, int ridx) {
  64. p = pp;
  65. d = x;
  66. realIdx = ridx;
  67. }
  68.  
  69. bool operator<(const distAndPoint &dp) {
  70. return (d < dp.d);
  71. }
  72.  
  73. };
  74.  
  75.  
  76. double Cost(vector<int> Tour) {
  77. double Ans = 0;
  78. int Size = (int) Tour.size();
  79. for (int i = 0; i < Size; i++) {
  80. int xx = Tour[i];
  81. int yy = Tour[(i + 1) % Size];
  82. Ans += pt[xx].dist(pt[yy]);
  83. }
  84. return Ans;
  85. }
  86.  
  87. void PrintSolution(vector<int> Tour) {
  88. printf("Solution Cost : %lf\n", Cost(Tour));
  89. printf("Tour Description : ");
  90. for (int i = 0; i < Tour.size(); i++)
  91. printf("%d ", Tour[i]);
  92. printf("\n\n");
  93. }
  94.  
  95.  
  96. class nnTourObject {
  97. public:
  98. vector<int> tourList;
  99. int cost;
  100.  
  101. nnTourObject() {}
  102.  
  103. double Cost() {
  104. double Ans = 0;
  105. int Size = static_cast<int>(tourList.size());
  106. for (int i = 0; i < Size; i++) {
  107. int xx = tourList[i];
  108. int yy = tourList[(i + 1) % Size];
  109. Ans += pt[xx].dist(pt[yy]);
  110. }
  111. return Ans;
  112. }
  113.  
  114. nnTourObject(vector<int> v) {
  115. tourList = v;
  116. cost = static_cast<int>(Cost());
  117. }
  118.  
  119. bool operator<(const nnTourObject &nt) {
  120. return (cost < nt.cost);
  121. }
  122. };
  123.  
  124. vector<nnTourObject> nnGreedySimple_5_Tours;
  125. vector<nnTourObject> nnGreedyRandom_5_Tours;
  126. vector<nnTourObject> twoOptFirst_4_Tours;
  127. vector<nnTourObject> twoOptBest_4_Tours;
  128.  
  129.  
  130. void printVector(vector<int> vec) {
  131. for (int i = 0; i < vec.size(); i++) {
  132. cout << vec[i] << " ";
  133. }
  134. cout << endl;
  135. }
  136.  
  137. /*****************NN Simple Start**********************/
  138.  
  139. int FindNearestUnvisited(int x) {
  140. double Min = LLONG_MAX;
  141. int Idx = -1;
  142. for (int i = 0; i < n; i++) {
  143. if (Vis[i])
  144. continue;
  145. if (pt[x].dist(pt[i]) < Min) {
  146. Min = pt[x].dist(pt[i]);
  147. Idx = i;
  148. }
  149. }
  150. return Idx;
  151. }
  152.  
  153.  
  154. void nnGreedySimple(int startIdx) {
  155. Tour.clear();
  156. memset(Vis, 0, sizeof(Vis));
  157.  
  158. int Start = startIdx;
  159. int Last = Start;
  160. Vis[Last] = 1;
  161. Tour.push_back(Start);
  162.  
  163. while (Tour.size() < n) {
  164. int Idx = FindNearestUnvisited(Last);
  165. Vis[Idx] = 1;
  166. Tour.push_back(Idx);
  167. }
  168. }
  169.  
  170. vector<nnTourObject> nnGreedySimpleUtil() {
  171. vector<nnTourObject> nn_5_Tours;
  172.  
  173. int t = 0;
  174. while (t < 5) {
  175. t++;
  176.  
  177. int randomStart = rand() % n;
  178.  
  179. nnGreedySimple(randomStart);
  180.  
  181. nnTourObject nnTour(Tour);
  182. nn_5_Tours.push_back(nnTour);
  183. }
  184.  
  185. sort(nn_5_Tours.begin(), nn_5_Tours.end());
  186.  
  187. #ifdef NN_SIMPLE_TEST
  188. cout << "Nearest Neighbor Greedy Simple Tour: " << endl;
  189. cout << "Best Case: " << endl;
  190. cout << " Start Node: " << nn_5_Tours[0].tourList[0] << endl;
  191. cout << " Tour : ";
  192. printVector(nn_5_Tours[0].tourList);
  193. cout << " Cost: " << nn_5_Tours[0].cost << endl;
  194. #endif
  195.  
  196. bestStartNNSimple = nn_5_Tours[0].tourList[0];
  197.  
  198. #ifdef NN_SIMPLE_TEST
  199. cout << "Worst Case: " << endl;
  200. cout << " Start Node: " << nn_5_Tours[4].tourList[0] << endl;
  201. cout << " Tour : ";
  202. printVector(nn_5_Tours[4].tourList);
  203. cout << " Cost: " << nn_5_Tours[4].cost << endl;
  204. #endif
  205.  
  206. double sum = 0;
  207. for (int i = 0; i < nn_5_Tours.size(); i++) {
  208. sum += nn_5_Tours[i].cost;
  209. }
  210. sum = sum / nn_5_Tours.size();
  211.  
  212. #ifdef NN_SIMPLE_TEST
  213. cout << "Average Cost: " << sum << endl;
  214. #endif
  215. nnGreedySimple_5_Tours = nn_5_Tours;
  216.  
  217. return nn_5_Tours;
  218. }
  219.  
  220. /*****************NN Simple End**********************/
  221.  
  222.  
  223.  
  224. /***********NN Random Start***************/
  225.  
  226. int FindNearestRandomUnvisited(int x) {
  227. vector<distAndPoint> nearest_nodes;
  228.  
  229. for (int i = 0; i < n; i++) {
  230. if (!Vis[i]) {
  231. distAndPoint tem(pt[i], pt[x].dist(pt[i]), i);
  232. nearest_nodes.push_back(tem);
  233. }
  234. }
  235.  
  236. sort(nearest_nodes.begin(), nearest_nodes.end());
  237.  
  238. int divisor = 5;
  239. if (nearest_nodes.size() < 5) divisor = static_cast<int>(nearest_nodes.size());
  240. int randomIdx = rand() % divisor;
  241.  
  242. distAndPoint tem = nearest_nodes[randomIdx];
  243. int Idx = tem.realIdx;
  244.  
  245. return Idx;
  246. }
  247.  
  248.  
  249. void nnGreedyRandomized(int startIdx) {
  250. Tour.clear();
  251. memset(Vis, 0, sizeof(Vis));
  252.  
  253. int Start = startIdx;
  254. int Last = Start;
  255. Vis[Last] = true;
  256. Tour.push_back(Start);
  257.  
  258. while (Tour.size() < n) {
  259.  
  260. int Idx = FindNearestRandomUnvisited(Last);
  261. Vis[Idx] = true;
  262. Tour.push_back(Idx);
  263. }
  264. }
  265.  
  266.  
  267. vector<nnTourObject> nnGreedyRandomizedUtil() {
  268. vector<nnTourObject> nn_5_Tours;
  269. vector<nnTourObject> simpleNNTour;
  270.  
  271. int t = 0;
  272.  
  273. while (t < 10) {
  274. t++;
  275. nnGreedyRandomized(bestStartNNSimple);
  276. nnTourObject nnTour(Tour);
  277. nn_5_Tours.push_back(nnTour);
  278. }
  279.  
  280. sort(nn_5_Tours.begin(), nn_5_Tours.end());
  281.  
  282. #ifdef NN_RANDOM_TEST
  283. cout << "Nearest Neighbor Greedy Randomized Tour: " << endl;
  284. cout << "Best Case: " << endl;
  285. cout << " Start Node: " << nn_5_Tours[0].tourList[0] << endl;
  286. cout << " Tour : ";
  287. printVector(nn_5_Tours[0].tourList);
  288. cout << " Cost: " << nn_5_Tours[0].cost << endl;
  289.  
  290. cout << "Worst Case: " << endl;
  291. cout << " Start Node: " << nn_5_Tours[4].tourList[0] << endl;
  292. cout << " Tour : ";
  293. printVector(nn_5_Tours[4].tourList);
  294. cout << " Cost: " << nn_5_Tours[4].cost << endl;
  295. #endif
  296.  
  297. double sum = 0;
  298. for (int i = 0; i < nn_5_Tours.size(); i++) {
  299. sum += nn_5_Tours[i].cost;
  300. }
  301. sum = sum / nn_5_Tours.size();
  302.  
  303. #ifdef NN_RANDOM_TEST
  304. cout << "Average Cost: " << sum << endl;
  305. #endif
  306.  
  307. nnGreedyRandom_5_Tours = nn_5_Tours;
  308.  
  309. return nn_5_Tours;
  310. }
  311.  
  312. /***********NN Random End***************/
  313.  
  314. /************2-Opt First improve Start***************/
  315. void TwoOptHeuristicFirstImprovement(vector<int> vec) {
  316. Tour.clear();
  317. memset(Vis, 0, sizeof(Vis));
  318.  
  319. Tour = vec;
  320.  
  321. while (true) {
  322. double Curr = Cost(Tour);
  323. bool Changed = false;
  324.  
  325. for (int i = 0; i < Tour.size(); i++) {
  326. for (int j = i + 2; j < Tour.size(); j++) {
  327. reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
  328. double NewCost = Cost(Tour);
  329. if (NewCost < Curr) {
  330. Changed = true;
  331. break;
  332. }
  333. reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
  334. }
  335. if (Changed)
  336. break;
  337. }
  338. if (!Changed)
  339. break;
  340. }
  341. }
  342.  
  343. /***************2-Opt best improve start***********/
  344. void TwoOptHeuristicBestImprovement(vector<int> vec) {
  345. int ii = 0, jj = 0;
  346. Tour.clear();
  347. memset(Vis, 0, sizeof(Vis));
  348.  
  349. Tour = vec;
  350.  
  351. while (true) {
  352. double Curr = Cost(Tour);
  353. bool Changed = false;
  354.  
  355. for (int i = 0; i < Tour.size(); i++) {
  356. for (int j = i + 2; j < Tour.size(); j++) {
  357. reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
  358. double NewCost = Cost(Tour);
  359. if (NewCost < Curr) {
  360. Changed = true;
  361. ii = i;
  362. jj = j;
  363. Curr = NewCost;
  364. }
  365. reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
  366. }
  367. if (Changed) {
  368. reverse(Tour.begin() + ii + 1, Tour.begin() + jj + 1);
  369. break;
  370. }
  371. }
  372.  
  373. if (!Changed)
  374. break;
  375. }
  376. }
  377.  
  378.  
  379. // twoOptType == 1 -> First , 2 -> Best
  380. // NNorSH == 1 -> NN , 2 -> SH
  381.  
  382. vector<nnTourObject> twoOptUtil(int NNorSH, int twoOptType) {
  383. string name = "";
  384. vector<nnTourObject> myTourResults;
  385. vector<nnTourObject> bestToursOfNNHandSH;
  386.  
  387. if (NNorSH == 1) {
  388. bestToursOfNNHandSH.push_back(nnGreedyRandom_5_Tours[0]);
  389. bestToursOfNNHandSH.push_back(nnGreedyRandom_5_Tours[1]);
  390. bestToursOfNNHandSH.push_back(nnGreedyRandom_5_Tours[2]);
  391. bestToursOfNNHandSH.push_back(nnGreedySimple_5_Tours[0]);
  392.  
  393. if (twoOptType == 1) {
  394. for (int i = 0; i < bestToursOfNNHandSH.size(); i++) {
  395. TwoOptHeuristicFirstImprovement(bestToursOfNNHandSH[i].tourList);
  396. nnTourObject tem(Tour);
  397. myTourResults.push_back(tem);
  398. }
  399. name = "2-Opt First for NNH Greedy Random." ;
  400. } else if(twoOptType == 2)
  401. {
  402. for (int i = 0; i < bestToursOfNNHandSH.size(); i++) {
  403. TwoOptHeuristicBestImprovement(bestToursOfNNHandSH[i].tourList);
  404. nnTourObject tem(Tour);
  405. myTourResults.push_back(tem);
  406. }
  407. name = "2-Opt Best for NNH Greedy Random." ;
  408. }
  409.  
  410. } else if (NNorSH == 2) {
  411. //SH vectors go here.
  412. // bestToursOfNNHandSH.push_back(shGreedyRandom_5_Tours[0]);
  413. // bestToursOfNNHandSH.push_back(shGreedyRandom_5_Tours[1]);
  414. // bestToursOfNNHandSH.push_back(shGreedyRandom_5_Tours[2]);
  415. // bestToursOfNNHandSH.push_back(shGreedySimple_5_Tours[0]);
  416. //
  417. // if (twoOptType == 1) {
  418. // for (int i = 0; i < bestToursOfNNHandSH.size(); i++) {
  419. // TwoOptHeuristicFirstImprovement(bestToursOfNNHandSH[i].tourList);
  420. // nnTourObject tem(Tour);
  421. // myTourResults.push_back(tem);
  422. // }
  423. //name = "2-Opt First for SH Greedy Random." ;
  424. // } else if(twoOptType == 2)
  425. // {
  426. // for (int i = 0; i < bestToursOfNNHandSH.size(); i++) {
  427. // TwoOptHeuristicBestImprovement(bestToursOfNNHandSH[i].tourList);
  428. // nnTourObject tem(Tour);
  429. // myTourResults.push_back(tem);
  430. // }
  431. //name = "2-Opt First for SH Greedy Random." ;
  432. // }
  433. }
  434.  
  435.  
  436. sort(myTourResults.begin(), myTourResults.end());
  437.  
  438. #ifdef TWO_OPT_TEST
  439. cout << name << " : " << endl;
  440. cout << "Best Case: " << endl;
  441. cout << " Start Node: " << myTourResults[0].tourList[0] << endl;
  442. cout << " Tour : ";
  443. printVector(myTourResults[0].tourList);
  444. cout << " Cost: " << myTourResults[0].cost << endl;
  445.  
  446. cout << "Worst Case: " << endl;
  447. cout << " Start Node: " << myTourResults[myTourResults.size()-1].tourList[0] << endl;
  448. cout << " Tour : ";
  449. printVector(myTourResults[myTourResults.size()-1].tourList);
  450. cout << " Cost: " << myTourResults[myTourResults.size()-1].cost << endl;
  451. #endif
  452.  
  453. double sum = 0;
  454. for (int i = 0; i < myTourResults.size(); i++) {
  455. sum += myTourResults[i].cost;
  456. }
  457. sum = sum / myTourResults.size();
  458.  
  459. #ifdef TWO_OPT_TEST
  460. cout << "Average Cost: " << sum << endl;
  461. #endif
  462.  
  463. return myTourResults;
  464. }
  465.  
  466.  
  467. int main() {
  468. // freopen("pr76.tsp", "r", stdin);
  469. freopen("berlin52.tsp", "r", stdin);
  470. // freopen("st70.tsp", "r", stdin);
  471.  
  472. freopen("out.txt", "w", stdout);
  473.  
  474.  
  475. srand(time(NULL));
  476.  
  477. scanf("%d", &n);
  478. for (int i = 0; i < n; i++) { scanf("%lf %lf", &pt[i].x, &pt[i].y); }
  479.  
  480. /***************Run NN_Greedy_Simple()*****************/
  481.  
  482. nnGreedySimple_5_Tours = nnGreedySimpleUtil();
  483. nnGreedyRandom_5_Tours = nnGreedyRandomizedUtil();
  484.  
  485. twoOptFirst_4_Tours = twoOptUtil(1,2);
  486.  
  487. // (nnsh, twoOptType)..
  488. // NNorSH == 1 -> NN , 2 -> SH
  489. // twoOptType == 1 -> First , 2 -> Best
  490. vector<nnTourObject> vn;
  491. vn = twoOptFirst_4_Tours;
  492.  
  493. for (int i = 0; i < vn.size(); i++) {
  494. cout << "################## Tour No. " << i + 1 << " : Cost = " << vn[i].Cost()
  495. << " ################" << endl;
  496. printVector(vn[i].tourList);
  497. cout << "###########################################################" << endl;
  498. }
  499.  
  500. cout << "****************************************************************************" << endl ;
  501.  
  502. twoOptBest_4_Tours = twoOptUtil(1, 1);
  503.  
  504. vn = twoOptBest_4_Tours;
  505.  
  506. for (int i = 0; i < vn.size(); i++) {
  507. cout << "################## Tour No. " << i + 1 << " : Cost = " << vn[i].Cost()
  508. << " ################" << endl;
  509. printVector(vn[i].tourList);
  510. cout << "###########################################################" << endl;
  511. }
  512.  
  513.  
  514. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!