In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.

My question is what is the advantages or disadvantages of using a constructive heuristic (like Nearest-Neighbour) compared to local search (something like 2-opt from some research?)

Thank you


So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive.

The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a more desirable solution.

As for advantages/disadvantages... well the nearest neighbour heuristic directs the search, but it may make silly mistakes. This in effect allows the search tree to be led "Down a rabbit hole".

The 2-opt solution is computationally more complex. It requires you to consider all quadruples (all pairs of edges if your data structure allows it) and then decide if the cross has occurred. In situations that you are looking for good enough and need an answer quickly, this type of search may be too computationally intensive. Although to the best of my knowledge, in any situation where 2-opt is a reasonable idea, the fitness of your solution should only improve/stay the same... Although I would not be surprised if I were wrong about that.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.