I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms.

My problem is that I can't find a good first approximation by the usual greedy algorithms, as long as I can't assure an arbitrary edge $(u,v)$ to be in $E$. I tried to add to $E$ new edges (with almost infinity weight) in order to make it complete, bit then it turns to be way more inefficient.

I can't find a good solution on internet. So can anyone help me?

  • 1
    $\begingroup$ Which greedy algorithm are you trying? $\endgroup$ – Raziman T V Feb 11 '17 at 9:38
  • $\begingroup$ I'm looking for a kruskal-similar algorithm. If the graph was complete I would add edges starting with the ones with less cost and always that this edge does not cause a vertex to have grade two or more and does not form a cycle until the full graph is covered. Then I will connect the formed paths in a single one. I'm trying to find something similar for non-complete graphs. $\endgroup$ – Alpp Feb 11 '17 at 16:34

Your Answer

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

Browse other questions tagged or ask your own question.