注册 登录
编程论坛 数据结构与算法

求最优解

caolini_1 发布于 2011-01-28 10:13, 1173 次点击
旅行售货员问题:某售货员要到若干城去推销商品,已知各城市之间的路程(旅费),要求我们为他选定一条从驻地出发,经过每个城市仅有一次,最后回到驻地的路线,使总路程(或总旅费)最小。(提示:遍历所有可能,然后找一个最小的总旅费)。
3 回复
#2
nwpu0634172011-02-02 17:58
TSP问题嘛,遍历所有可能,在n较大的时候会比较慢吧~~ O(n^2)
#3
草狼2011-02-04 14:18
可以用floyd最小环算法做下 不过时间复杂度是O(n^3)
#4
CCFzeroOH2011-02-13 19:53
以下是引用草狼在2011-2-4 14:18:24的发言:

可以用floyd最小环算法做下 不过时间复杂度是O(n^3)



弗洛伊德算法
1