I have a problem which is basically TSP where is a limit on how far youcan go and every city has a profit.

I need to make algorithm where he could come back with highest profit after a trip. It's not important how many cities he will visit as only profit is important.

I need to the solution in code so it has to be practical and not necasirly the complete best solution, which means some approximations/shortcuts to save calculation time is also good.

  • $\begingroup$ By "solvable" do you mean "solvable in polynomial time"? TSP is solvable (unlike, say, the Halting Problem), it just takes exponential time to do so with all known algorithms. $\endgroup$
    – Draconis
    Jun 21, 2018 at 14:47
  • 1
    $\begingroup$ Can you specify your problem more fully? $\endgroup$ Jun 21, 2018 at 15:16
  • $\begingroup$ Have you tried standard approaches used to solve TSP in practice? $\endgroup$ Jun 21, 2018 at 15:16
  • 1
    $\begingroup$ By "solvable", do you mean theoretically or practically? $\endgroup$ Jun 21, 2018 at 15:16
  • $\begingroup$ What do you mean by "what changes should be made"? That seems too open-ended. I can think of many changes that might make this solvable, but are you going to be happy with them? How can I tell? Please narrow down your question to list the requirements on what kinds of changes are allowable so we will be able to know before we write our answer whether it will meet your requirements -- and so others can evaluate our answers. $\endgroup$
    – D.W.
    Jun 21, 2018 at 15:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.