开发者

Algorithms question on an n*n matrix of distances

开发者 https://www.devze.com 2022-12-16 01:36 出处:网络
Suppose I have an n*n matrix of distances between n use开发者_如何学Pythonrs. I\'d like to know what algorithm to use in order to find a route around the group, beginning at user X and returning to us

Suppose I have an n*n matrix of distances between n use开发者_如何学Pythonrs. I'd like to know what algorithm to use in order to find a route around the group, beginning at user X and returning to user X, with all other nodes visited once but only once, and using the shortest possible distance in each hop.


This problem is called the Travelling Salesman Problem. There is an excellent Wikipedia page on it that should point you in the right direction.


This is Traveling Salesman Problem assuming that you want the total length of the tour to be minimized. NP-Complete, so no poly-time algoritm, but good approximation techniques exist.

0

精彩评论

暂无评论...
验证码 换一张
取 消