5 ms·
Thanks for your reply ... I need to re-write the section because really I'm dealing with Hamilton Path rather than Traveling Salesman, but even so ... Even if
by ColinWright 15y ago
Thanks for your reply ...
I need to re-write the section because really I'm dealing with Hamilton Path rather than Traveling Salesman, but even so ...
Even if you say that all inter-city routes are of unit length, it's hard to find a route that visits each city exactly once. The key point is that we're not allowed to re-visit a city. Such a path, visiting every node exactly once and returning to the starting point, is called a Hamilton Cycle, and there is no known sub-exponential algorithm to guarantee finding whether a given network (or graph) has one.
Is that clearer?