|
|
|
|
|
|
by Derander
4665 days ago
|
|
|
One thing to note about this specific problem: this is an example of the traveling salesman problem with a metric. This makes efficient (good) approximation algorithms a possibility. Many NP-hard approximation algorithms classes teach a 1.5 approx known as the Christofides algorithm. This algorithm is guaranteed to provide an approximate solution that is no worse than 1.5 times the optimal total distance, and often much better. |
|
|