I am hoping there is already a straight forward algorithm as a solution to this but not sure what this type of problem is called and therefore where to look for a solution. It is in some ways similar to the traveling salesman problem but I think it should be much simpler. The main difference to the problem is there are limited connections (3 to 6 per city) between cities. The path does not need to return to starting, only that it visits each city just once. Also the connections are all the same length so the full path length will always be the same (NOT A SHORTEST DISTANCE PROBLEM). There are 84 cites and therefore the final path will always be 87 units long. Basically I am looking for any solution that can from a random start, get to all cities just once. I am hoping for a "random" solution that won't look orderly. Any suggestions on what this type of problem is called and where I might find an algorithm. Thanks.
1
- 1This question may be better placed in the Computer Science Stack Exchange rather than Stack Overflow.Matthew Seaman– Matthew Seaman2016-10-24 05:19:30 +00:00Commented Oct 24, 2016 at 5:19
Add a comment |
1 Answer
You are looking for a Hamiltonian Path. Unfortunately, this problem is NP-Complete, although the fact that the vertices in your graph have a limited degree with help its tractability. You can find more information about solving this problem on the linked Wikipedia page or in this answer.
