Geek asks and answers

Algorithm for finding the "minimum connecting path"?

Inspired by this comic http://xkcd.com/173/

I know that there are many algorithms for finding the smallest spanning tree of a weighted graph, but I try my best to find anyone that can find a minimal connecting "path".

For a comic book, if we weighed every edge based on each pair ratio, then a socially optimal layout would be a minimal spanning “path”, i.e. in a way that spans all the peaks. Can anyone help?

+5
source share
1 answer

Finding the optimal Hamiltonian path (also known as the cover of the optimal path) is a difficult task. (Determining whether any Hamilton path exists is an NP-complete problem.) This scientific article discusses, among other things, the optimal path covering algorithm. You can search the Internet for these terms to find other resources. I do not know any code available.

By the way, this question (which is basically your duplicate) clearly explains why the problem with Traveling Salesman is not a place to start.

+2
source

More articles:


All Articles