Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
MathOverflow

Return to Question

deleted 1041 characters in body
Source Link
Zixun Tau
Zixun Tau
  • 21
  • 3

Think of this like a variationTake the traveling salesman problem. You have a bunch of cities which are all connected with roads of unique arbitrary lengths (i.e. uncorrelated to the distance between the cities). Forget about their intersections (pretend that at every intersection one tunnels beneath the other). Is it possible for a nearest neighbor algorithm here to have a shorter total distance travelled than opposite-nearest neighbor algorithm (which always takes the longest path legal road)? Note, you can choose any start city for the two algorithms (i.e. give the opposite nearest neighbor algorithm a better starting city than the nearest neighbor algorithm)but with three slight twists:

  1. You can choose a different start vertex for each of the two algorithms.
  2. Each path from one vertex to another is of unique, arbitrary length (irrespective of the distances between the cities and they don't intersect).
  3. Each algorithm goes to each vertex once and only once (it doesn't return to its starting vertex). With these conditions, is it possible for a furthest neighbor algorithm to beat a nearest neighbor algorithm.

I know that this algorithm can miss the best optimal route by large quantities, so is this possible? Here's some rough work of what I have so farI've tried using induction, but I'm not sure if I'm headed in the right direction: Both algorithms have to travel to every city. Thus, at every city, the nearest neighbor algorithm takes a shorter path than the opposite nearest neighbor algorithm. Thus, in order for the opposite nearest neighbor algorithm to have a shorter total journey, its last move must be much smaller than the last move of the nearest neighbor algorithmcondition 2. However, if this path is so short, then the nearest neighbor algorithm would have already travelledreally throws it. Therefore, a nearest neighbor algorithm will always beat out an opposite nearest neighbor algorithm given the constraints I earlier set up. Remember, by opposite nearest neighbor algorithm, I mean something that always takes the longest possible path. Does this work? It seems to straightforward off.

Think of this like a variation traveling salesman problem. You have a bunch of cities which are all connected with roads of unique arbitrary lengths (i.e. uncorrelated to the distance between the cities). Forget about their intersections (pretend that at every intersection one tunnels beneath the other). Is it possible for a nearest neighbor algorithm here to have a shorter total distance travelled than opposite-nearest neighbor algorithm (which always takes the longest path legal road)? Note, you can choose any start city for the two algorithms (i.e. give the opposite nearest neighbor algorithm a better starting city than the nearest neighbor algorithm)

I know that this algorithm can miss the best optimal route by large quantities, so is this possible? Here's some rough work of what I have so far, but I'm not sure if I'm headed in the right direction: Both algorithms have to travel to every city. Thus, at every city, the nearest neighbor algorithm takes a shorter path than the opposite nearest neighbor algorithm. Thus, in order for the opposite nearest neighbor algorithm to have a shorter total journey, its last move must be much smaller than the last move of the nearest neighbor algorithm. However, if this path is so short, then the nearest neighbor algorithm would have already travelled it. Therefore, a nearest neighbor algorithm will always beat out an opposite nearest neighbor algorithm given the constraints I earlier set up. Remember, by opposite nearest neighbor algorithm, I mean something that always takes the longest possible path. Does this work? It seems to straightforward.

Take the traveling salesman problem, but with three slight twists:

  1. You can choose a different start vertex for each of the two algorithms.
  2. Each path from one vertex to another is of unique, arbitrary length (irrespective of the distances between the cities and they don't intersect).
  3. Each algorithm goes to each vertex once and only once (it doesn't return to its starting vertex). With these conditions, is it possible for a furthest neighbor algorithm to beat a nearest neighbor algorithm.

I've tried using induction, but condition 2. really throws it off.

Source Link
Zixun Tau
Zixun Tau
  • 21
  • 3

Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm

Think of this like a variation traveling salesman problem. You have a bunch of cities which are all connected with roads of unique arbitrary lengths (i.e. uncorrelated to the distance between the cities). Forget about their intersections (pretend that at every intersection one tunnels beneath the other). Is it possible for a nearest neighbor algorithm here to have a shorter total distance travelled than opposite-nearest neighbor algorithm (which always takes the longest path legal road)? Note, you can choose any start city for the two algorithms (i.e. give the opposite nearest neighbor algorithm a better starting city than the nearest neighbor algorithm)

I know that this algorithm can miss the best optimal route by large quantities, so is this possible? Here's some rough work of what I have so far, but I'm not sure if I'm headed in the right direction: Both algorithms have to travel to every city. Thus, at every city, the nearest neighbor algorithm takes a shorter path than the opposite nearest neighbor algorithm. Thus, in order for the opposite nearest neighbor algorithm to have a shorter total journey, its last move must be much smaller than the last move of the nearest neighbor algorithm. However, if this path is so short, then the nearest neighbor algorithm would have already travelled it. Therefore, a nearest neighbor algorithm will always beat out an opposite nearest neighbor algorithm given the constraints I earlier set up. Remember, by opposite nearest neighbor algorithm, I mean something that always takes the longest possible path. Does this work? It seems to straightforward.