Warm tip: This article is reproduced from stackoverflow.com, please click
algorithm theory traveling-salesman

Outsmarting a Traveling Salesman Algorithm

发布于 2020-05-27 16:10:28

I am having difficulty constructing a small undirected graph G that has weighted edges that outsmarts the given algorithm, meaning the algorithm will not pick the optimal solution no matter what the start point is. Every node is connected to every other node.

Given a starting point, the algorithm iteratively picks the closest unused point on the graph and visits it until it cycles back to the start point. The algorithm does brute force, running with every point being a start point and selecting the shortest Hamiltonian cycle from all of the outputted cycles.

I for the life of me have been incapable of figuring this out, I've drawn countless graphs, gone through and solved them and still have been unable to come up with a graph that the algorithm will not find an optimal solution for.

This is completely theoretical and has no code. Any guidance or pointers as to how I should approach/think about this is greatly appreciated.

Questioner
Caleb
Viewed
25
分享
♦ 2016-02-11 12:55

Consider the following 4-vertex graph:

enter image description here

We have edges AB and CD of length 2, BC of length 1, AC and BD of length 3 and AD of length infinity (or arbitrarily large).

If you start from A and follow the greedy approach, you go to B (length 2), then C (length 1), then D (length 2), and then are stuck taking DA (length infinity). By the graph's symmetry, you get the same result when starting from D (you go D -> C -> B -> A -> D, length infinity).

If you start from B and follow the greedy approach, you go to C (length 1), then D (length 2), then A (length infinity -- this is the only available move since we've already visited B and C), and finally B (length 2). By the graph's symmetry, you get the same result when starting from C (you go C -> B -> A -> D -> C, length infinity).

In short, no matter where the greedy approach starts, in ends up getting length infinity. Meanwhile the path A -> C -> D -> B -> A has length 10.

Not only is the brute force algorithm non-optimal regardless of the starting point, but it performs unboundedly poorly.

Related issues

1
how many times we should used ford-Fulkerson?
2
Rectangle selection algorithm
3
Find the rectangle with the maximum area, containing a specific point in an occupancy grid
4
Order by sum of digits of number
5
How to find the "center" of a subset of vertices in a graph?
6
Best parse tree given spans using maximum sum
7
How to generate all permutations of a list?
8
How to use infinity in python
9
How to reorder an Array to avoid consecutive duplicates
10
Finding minimum cost to reach the end of array