I like participating in Marathon-type competitions and in the near future I will participate in a few more. However I feel like my solutions are always not good enough. I've been to a lecture of Psyho where he explained some approaches. I know in theory things like Beam Search, Simulated Annealing, Hill climbing. However when I face a marathon task I really have a hard time to choose which one to use and more importantly, how exactly to construct it.
Take a simple NP-Hard problem as the Travelling Salesman. I have no clue how to solve it using any of the above techniques, and I would probably end up using some randomized short backtracks, which would end up with a horrible score.
I would be very grateful if someone could give me some tips, and perhaps explain some not-too-hard approach for the Travelling Salesman problem, so I can learn from that.
Thanks in advance! :)