Our Zoom Poll
Why is the answer not just n factorial?
Copyright By PowCoder代写 加微信 powcoder
Think about the complete undirected graph with 3 vertices
Call vertices a, b, and c.
Are there 3! = 6 tours? If not, then n! is not the correct answer.
All possible tours for these vertices:
a->b->c->a
b->c->a->b
Q: are these two tours actually different? No: they use the same edges.
How about a->c->b->a?
This is the same tour as well.
n! is incorrect because it counts the same tour many times.
It counts each tour twice: once forward and once backward
And it counts each of these n times, one for each starting point of the tour, like this:
a->b->c->a
b->c->a->b
c->a->b->c
Answer is n!/(2*n)
= (n-1)!/2
Exhaustive search will give us something like O(n!) runtime.
———-
Comparing n! to 2^n
n! is approximately (n/e)^n
Compare that to 2^n… a lot smaller
———-
Dynamic Programming Algorithm for TSP
Memory space complexity here is huge: O(2^n)
Good example of space-time tradeoff: huge memory usage for faster runtime
let A be a two-dimensional 2^n by n array
# Base cases (2 vertices)
for j in [2, 3, …, n]:
A[{1, j}][j] = c(1, j)
# General (>= 3 vertices)
for s in [3, 4, …, n]: # s == size == num vertices
for all S such that 1 in S and |S| == s:
for j in S – {1}:
A[S][j] = min_{k in S-{1, j}} A[S-{j}][k] + c(k, j)
Runtime for the above code is: O(2^n*n *n) = O(2^n * n^2)
Postprocessing needed here is O(n); this doesn’t change the overall runtime.
Here we have O(2^n * n^2), which is much faster than O(n!)
n!, you can solve ~15 vertices
O(2^n * n^2), you can solve ~30 vertices
Doubled the problem size that you can solve.
Not a huge increase, but with these NP-complete problems you take what you can get 🙂
———-
Here was our first execution of the contraction algorithm.
Contract edge (a, c):
Contract edge (ac, d):
Just two vertices remaining, so we are done.
What are these two vertices called?
the other is acd
This is what the algorithm claims is the min cut: ({b}, {a, c, d})
a–b <-- crosses b--c <-- crosses How many edges cross that cut? 2 What's the min cut in this graph? 2 The algorithm got it right this time. And here was our second execution of the contraction algorithm. Contract edge (a, b): Contract edge (c, d): Just two vertices remaining, so we are done. The claimed min cut this time is ({a, b}, {c, d}) How many edges cross this cut? b--c <-- crosses d--a <-- crosses a--c <-- crosses 3 edges cross this cut. So the algorithm didn't find the min cut this time... got it wrong. Say that we have a graph with 50 vertices. Do you expect this algorithm to find the min cut? On every iteration, there's a chance for the algorithm to make a mistake. To get the min cut, it has to avoid making a mistake on every iteration. And there are a lot of iterations: n-1 of them. Remember: there are 2^n cuts So if the probability of this algorithm finding the min cut is 1/2^n, then it wouldn't be useful