3 ms·
Although the travelling salesman problem is NP-hard, and it’s possible to construct hard-to-solve instances, there are algorithms that work very well for most i
by robinhouston 10y ago
Although the travelling salesman problem is NP-hard, and it’s possible to construct hard-to-solve instances, there are algorithms that work very well for most instances.
I just tried using LKH[0] to reconstruct these scrambled images, and it does it perfectly in a fraction of a second.
[0] http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/
- nayuki 10y agoInteresting experiment! It took me a minute to understand why you mentioned the TSP, but then I realized that you can model each column as a destination and the pixel difference between two columns as the distance. Once I got that, I can certainly appreciate that a state-of-the-art TSP solver will solve the scrambled images perfectly in no time. =)
- robinhouston 10y agoI just posted my code, in case anyone is interested in playing with it. https://github.com/robinhouston/image-unshredding https://github.com/robinhouston/image-unshredding
- nayuki 10y agoDiscussion: https://news.ycombinator.com/item?id=12670997 https://news.ycombinator.com/item?id=12670997
- contravariant 10y agoInteresting, although I guess I should have expected a TSP solver to do well. FWIW simulated annealing can also be used to solve TSP instances. Although clearly it doesn't do too well in this case. Anyway, I only mentioned it to point out it wasn't a simple matter of calculating the similarities between columns and 'sorting' them, you need a more sophisticated algorithm.
- rurban 10y agoInteresting to see how bad simulated annealing does, by not being able to step over so many hills. LKH is a bit unfair, as this problem cries for a Travelling Salesman, but still SA doing so bad is astonishing. Given how often it is used for optimization problems. Maybe solvers should be used more often.