4 ms·
>how to solve TSP with dynamic programming. Impressive. (TSP is NP-hard. Not even NP-complete because you can't verify the solution in polynomial time... or at
by virgilp 7y ago
>how to solve TSP with dynamic programming.
Impressive. (TSP is NP-hard. Not even NP-complete because you can't verify the solution in polynomial time... or at least, I don't know how to do it and would love to see a solution with dynamic programming)
- AstralStorm 7y agoIt's an approximate solution with bounded unoptimality, I don't remember the exact bound off the top of my head. Edit: it's 3/2 for Christofides' algorithm. Native dynamic is bad speed but gives accurate solution. It's no good for more than 24 nodes or so. Usually it is good enough, other similar and better attempts try to tighten that bound with more admissible heuristics. E.g. for metric spaces solution is possible to tighten a lot. (Like shortest travel without weights.)
- virgilp 7y agoOh, I see what you mean; I would still be seriously impressed with any bootcamp that teaches approximation algorithms. And not in a good way TBH - it kinda' defeats the purpose of the bootcamp. It's hard enough to go through Knuth in a few months...