• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?