SHARE
TWEET

Untitled

a guest Apr 18th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Add a new point after the point that it is closest to.
  2. // If there is a tie, insert it after the first such point you find.
  3. // Passed a pointer to the first node in the tour, NULL if creating a new tour.
  4. // Returns pointer to the first node in the linked list after the addition.
  5. Node* addNearestNeighbor(Node* first, double x, double y)
  6. {
  7.   if ( tourSize(first) == 0 ) {
  8.     // Makes a new node.
  9.     Node* randomNode = (Node*) malloc(sizeof(Node));
  10.     randomNode -> x = x;
  11.     randomNode -> y = y;
  12.     randomNode -> next = randomNode;
  13.     first = randomNode;
  14.     return first;
  15.   } else {
  16.     // Creates a new node and then checks where to place it.
  17.     Node* randomNode = (Node*) malloc(sizeof(Node));
  18.     randomNode -> x = x;
  19.     randomNode -> y = y;
  20.     double smallestDistance = 99999;
  21.     double currentDistance = 0;
  22.     Node* current = first;
  23.     Node* nearestNeighbor = current;
  24.     // Loops through all the nodes to find the closest node.
  25.     do {
  26.       currentDistance = distance( current, randomNode );
  27.       if ( currentDistance < smallestDistance ) {
  28.     smallestDistance = currentDistance;
  29.     nearestNeighbor = current;
  30.       }
  31.       current = current -> next;
  32.     }
  33.     while ( current != first );
  34.     randomNode -> next = nearestNeighbor -> next;
  35.     nearestNeighbor -> next = randomNode;
  36.     return first;
  37.   }
  38. }
  39.  
  40. // Add a new point after the point where it results in the least increase in tour length.
  41. // If there is a tie, insert it after the first such point you find.
  42. // Passed a pointer to the first node in the tour, NULL if creating a new tour.
  43. // Returns pointer to the first node in the linked list after the addition.
  44. Node* addSmallestIncrease(Node* first, double x, double y)
  45. {
  46.   if ( tourSize(first) == 0 ) {
  47.     Node* randomNode = (Node*) malloc(sizeof(Node));
  48.     randomNode -> x = x;
  49.     randomNode -> y = y;
  50.     randomNode -> next = randomNode;
  51.     first = randomNode;
  52.     return first;
  53.   } else {
  54.     Node* randomNode = (Node*) malloc(sizeof(Node));
  55.     randomNode -> x = x;
  56.     randomNode -> y = y;
  57.     double smallestDistance = 99999;
  58.     double currentDistance = 0;
  59.     Node* current = first;
  60.     Node* next = current -> next;
  61.     Node* weirdNode = current;
  62.     // Loops to see the smallest increase in distance based off the previous distance.
  63.     do {
  64.       double distanceUno = distance ( weirdNode, randomNode );
  65.       double distanceDos = distance ( randomNode, next );
  66.       double distanceTres = distance ( weirdNode, next );
  67.       currentDistance = ( distanceUno + distanceDos - distanceTres );
  68.       if ( currentDistance < smallestDistance ) {
  69.     smallestDistance = currentDistance;
  70.     current = weirdNode;
  71.       }
  72.       weirdNode = weirdNode -> next;
  73.       next = weirdNode -> next;
  74.     }
  75.     while ( weirdNode != first );
  76.     randomNode -> next = current -> next;
  77.     current -> next = randomNode;
  78.     return first;
  79.   }
  80. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top