TSP Approximation Algorithm
Here’s our full walk of the MST T:
a b a c d c a
Copyright By PowCoder代写 加微信 powcoder
This is not a tour because we visit some vertices more than once.
It would be nice to do this:
a b _delete a_ c d c a
that gives
a b c d c a
Could we have just messed up our cost and increased it?
When the a was there, we went from b to a to c.
Now we’re going b to c directly.
Because we’re assuming the triangle inequality, there’s no way that we increased the cost here.
This is now a tour, and we didn’t make it any greater than the cost of the full walk.
———-
Here are the NP-Complete problem approximation algorithm results that we’ve seen:
1. TSP with triangle inequality: 2 approximation.
There’s a 1.5 approximation as well.
2. TSP without the triangle inequality: no finite approximation ratio
3. Vertex cover: 2 approximation
4. Knapsack: arbitrarily good approximation
These are all NP-Complete problems (equivalently difficult to solve exactly), but with widely varying approximation guarantees.
———-
How would exhaustive search work to solve TSP?
How many tours are there to check? Something like n factorial tours.
Runtime: O(n!)
You can use dynamic programming to improve this to O(2^n).
(More details about this next week.)
2^n: 2*2*2*2*2*2 n times
n!: n * n-1 * n-2 * … all but one of these numbers are >= 2
———-
How can we encode vertex cover?
Let’s focus on the 5 node clique graph.
I propose 5 variables here; again 0-1 binary variables.
0 = excluded, 1 = included
Objective:
minimize a + b + c + d + e
How about the constraints?
Consider edge a–b
what’s the constraint for this edge?
a + b better be >= 1 (have to include at least one of them for this edge to be covered)
a + c >= 1
… do this for each edge.
———-
How can we force the SAT to choose a colour for each vertex and not return to us the no-colouring cheap answer?
Introduce one new constraint for each vertex v:
x_v1 or x_v2 or x_v3 or x_v4 or … or x_vk
Now it has to choose at least one colour for vertex v.
What if it chooses more than one? Just choose one of them that you’ll use to colour the vertex