1
$\begingroup$

I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.

How do I generate a valid initial path effectively?

I would use a greedy algorithm, but I can't be sure it will result in a valid path. I could still use it and hope that simulated annealing will find a valid path, but I can't guarantee that it will.

$\endgroup$
1
$\begingroup$

Set the cost on the missing edges to $+\infty$, or some suitably large constant. Then all paths are valid, and you can apply simulated annealing. Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time. That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph. Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path. (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)

$\endgroup$

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.