迷题：走遍全国各省会的最短路线问题 ？？？

典型的"旅行者"问题.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

这问题都研究2个世纪了,很难找到一个高效的解决办法.

我线性代数老师是专门研究这个问题的 走遍全国最短路线记录保持者 他已经搞了一辈子了

没有大家可以接受的最短路线算法，折中的算法是不求最短，但求较短较快。

应该是比较成熟的数学模型了，好像数学模型引论中有。
这算法前人应该研究过很多遍了。

最基本的优化：缓存距离数据，保证各城市的距离只算一次。

估计应该可以提速个两三个数量级。

关键词：A*  估值函数

不过这问题本来就是一个大难题...

这是一个货郎担问题（N个城市的最短距离），属于典型的NP问题，随着节点增加，算法复杂度上升很快，williamy说的方法只能针对少数节点才可用（算法复杂度为：n的n次方）。作为一般性问题求解方式，很难求得最优解，只能求得次优解。以前读MSE的《算法》时，做过这个题目的课程设计，简单的用“贪心法”，复杂的用“线形规划”，31个城市，用java做，在几分钟内能求解。用C++可能还要更快一下。求得的结果如下：
先列后行31：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-437-西安-521-银川-346-兰州-192-西宁-1440-乌鲁木齐-1592-拉萨-1257-成都-641-昆明-434-贵阳-449-南宁-373-海口-455-广州-563-长沙-299-武汉-270-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-537-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：15404

更正：复杂的用“动态规划”而不是“线形规划”。

我好像听人说过，这类问题用蚁群算法！
具体的蚁群算法是什么，我也不知道！