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.
Asked
Active
Viewed 365 times
-1
-
1This question may be better placed in the Computer Science Stack Exchange rather than Stack Overflow. – Matthew Seaman Oct 24 '16 at 05:19
1 Answers
1
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.
Community
- 1
- 1
Erik Godard
- 5,930
- 6
- 30
- 33