即将推出中国旅行商计算项目TSPChina@home
实验地址:http://www.aitech.cn/grid/下面是一篇参考资料，正式程序预计下周推出。
旅行货郎问题
如果我现在有一个图G，而这图的每一条弧上都算上一个数字，我要怎样才能找到这图的哈密顿回路具有所有的弧上数字的和是最小值的性质，这个问题就是数学上大名鼎鼎的难题：“旅行货郎问题”。
这问题在1932年由德国著名数学家K．Menger提出，这29年来是许多人废寝忘食研究的对象。
我们在日常生活中就会遇到这问题，比方说：
（1）你是学校校车的司机，你从学校开车出来，到不同的街道去接孩子，你要怎样安排使走的路程最短，可以接到所有的孩子回到学校去？
（2）春假到了，你想驾车在北美几个城市旅行，可是现在汽油是这么昂贵，你想要尽量省用油，汽油的消耗是和路程成正比，因此你想法子找一个回路具有最短的路程。
（3）你为了商业业务，需要乘飞机飞几个城市，不同的飞机公司提供不同的票价，你要怎样安排行程，使到你能走遍你要去的城市，最后又回来原出发地，而又能省钱？
“旅行货郎问题”是这么容易明白，可是要找出一个行之有效及能迅速提供解答的方法，目前并不存在。在28年前，美国的《管理科学》（ManagementScience 1963）一篇讨论“旅行货郎问题”的文章就说道：“人类由于他的运算能力的限制在解决旅行货郎问题上并不好。”人们现在对于这问题的实际情形都是借助高速的电子计算机来运算。
我在以下会介绍一种直观而又容易明白的树的搜索法来寻找最优解，目前解“旅行货郎问题”有很多种方法，由于大部分要牵涉到较深的数学知识，因此我不在这里介绍。我最后会通过例子说明为什么这个看来小学生都能明白的问题却是数学难题。
德国人很喜欢精确的数学，在1978年，波恩大学有一位数学家想要知道在西德的120个有铁路穿过的城市要安排一个最短路程的回路，应该怎么样跑。他从铁路局找到了准确的城市间铁路的长度，整个问题变成一个有7140个变数，120个方程及96个不等式的线性规划问题，用电子计算机去算得到最短的回路是6942公里。（见图五）。
树的搜索法
我这里举一个例子说明这个方法，假定我现在有四个城市A，B，C，D，它们之间的路程是由下面的表给出（见图六）：
我要找从A出发回到A的最短回路。
我从A出发，我写：（A）0。0是表示最初没有出发路线长是0，然后我列下所有可能的下一个站：B，C，D，然后我得到三个节点（node）：（AB）1，（AC）3，（AD）2。
这时我就把（A）0划掉，然后找节点具有最小的数值，这里是（AB）1。从B我可以走的站是C和D，我就划掉（AB）1，用（ABC）1+4及（ABD）1+7来取代。为什么（ABC）旁的数字是1+4呢？因为它是（AB）加上（BC）的长。（见图七）。
我们把没划掉的节点中有最小长度的找出，这是（AD）2D的下一个可能的站是B和C，因此我们划掉（AD）2补上两个节点（ADB）2+7及（ADC）2+5。
我们继续找具有最小长度的节点，这时看到是（AC）3从C出发可以到达B或D，于是我们划掉（AC）3，补上（ACB）3+4，（ACD）3+5。（见图七（e））
我们再搜索有最小长度的节点，看到是（ABC）5，于是划掉它，补上（ABCD）5+5，得图七（f）。
我们再搜索没有被划的节点，看到有最小长度的是（ACB）7及（ADC）7，我就先划掉（ACB）7补上（ACBD）7+7，得图七（g）。
然后我再划掉（ADC）7补上（ADCB）7+4得图七（h）。
这时候我看剩下没划线的最小长度的节点是：（ABD）8及（ACD）8，我划掉了比方说（ABD）8，补上（ABDC）8+5。
我再寻找最小长度的节点得（ACB）8，划掉之后补上了（ACDB）8+7，得图七（j）。
现在变成（ADB）9是最小长度的节点，我们划掉补上（ADBC）9+4，得图七（k），我们划去（k）的最小长度节点（ABCD）10，补上（ABCDA）10+2。我们已得到一个回路了，这时我们把（1）图中所有长度大过12，节点全划掉，因为这些节点所产生的回路肯定要大过12，我们可以不考虑，我们只剩下（ADCB）11，划掉它之后补上（ADCBA）11+1，我们得（k）。
谢天谢地，到此时我们再没有什么节点可以划了，我们得到两个回路（ABCDA）及（ADCBA），它们的长都是12。这种方法在数学上有一个名称叫 uniformcost Search。为了说明整个搜索的程序，我画了许多像树枝分叉的图，实际上读者只需在一个图上划线及向下发展不必画这么多树。通常哈密尔顿回路找到之后，我们选取最少的长度，那就是我们所要的答案。
为什么数学家和电脑专家对货郎问题发生兴趣
我们前面介绍的方法在城市数目字比方说不超过十个还不显得可怕。如果现在有21个城市用以上的方法去搜索最短的回路，我们最少要找超过九十万个以上的路线，这是多么巨大的数字呀！
现在请想一想，如果我们要处理的是五百个城市，或者一千个城市，或者就拿像中国这么大的国家，这么多的县城，要处理这问题，用目前最快速的电子计算机来协助，也会使电子计算机挂投降的白旗，宣称：“我的记忆不够处理这些问题产生出来的数值，对不起哥哥，我不能替你效劳。”
我前面介绍的树的搜索法是一个比较简单但并不是太好的方法，这20年来，许多人想出一些方法想要改进，希望能找到一个较理想的方法，可以快速的找到结果。目前来说这样理想的方法还没有找到。
什么样的方法算是理想呢？我们这里给一个粗略的解释：比方说我们要用电子计算机来帮我们工作，例如处理n个城市的旅行货郎问题，当我把n个城市的距离表喂给电子计算机之后，它就会一步一步的去找。如果它要得到答案，所要花费的步骤数目是可以用n的函数f（n）来表示。我们说这方法是“理想”，当f（n）是一个n的多项式。
目前我们的方法都不是理想的。如果你真能找到一个理想的方法，你的成果会轰动全世界。你的方法可以转化用来解决许多数学的难题及电子计算机理论的一些著名难题。
旅行货郎问题是许多国家的运筹学研究中心的工作者深入研究的问题。在美国的华籍数学工作者在这方面有很好的结果的有 Lin Shen及Hong Saman等人。在1977年Hong先生和Padberg 合作用电子计算机处理有318个城市的“旅行货郎问题”，这个问题化成线性规划问题就要处理有50403个变数（variables）的方程式，及不等式，如果不借助电子计算机的快速计算，我想就是请一位能笔算及心算很快的数学家，让他穷十年的时间也是不能解决。以上的问题他们用IBM 370-168式的电子计算机，只花28.38分钟就得到一个最优解。
“玩物丧志”，这是以前老一辈的人骂儿童或少年不读书只喜欢游戏所爱用的一句话。其实游戏和玩具可以引导大发现。如果有青少年肯对哈密尔顿图及旅行货郎问题下点苦功研究，我会说他们是“玩物立志”，很可能以后会出一些在这些问题上作出大贡献的中国人。
45个城市不是很多，计算强度不是很大，可能最开始最优答案容易经常出现，但是越往后越难，因为这个项目比较有趣（可以按距离排名），我是来做为启动的实验项目的，最开始我想先用随机法比较有趣（遍历法可以但太枯燥），当过一段时间最优结果不容易出现时再加前20-50位的遗传变异（交换一位）的小程序，这两天其他事务太忙，等周一我能得到球面距离公式，下周一定让它运行起来！
谢谢equn的支持，我暂时有个php环境，将来如有可能希望利用你这儿的windows环境,我的理想是能在这儿开个专版！ 我已经去看过了，针对中国人设计中国旅游线路的最优化解决方案。源于图论思想，构造最小生成数。常用的算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。 呵呵，在数据结构了学过这方面的东西的：用Dijkstra算法求单源最短路径. 用Floyd算法求每对顶点间的最短路径.按照Prim算法构造图的最小支撑树. 按照Kruskal算法构造图的最小支撑树.
但是能实际的对中国的旅游做做分析应该说是很有积极意义的。
下面转一篇用C++实现算法的文章：
-------------------------------------------------------------------------------------------------------------------
数据结构学习（C++）最短路径
最短路径恐怕是图的各种算法中最能吸引初学者眼球的了——在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。
在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响——就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，如果对所有的顶点都求解，那么算法就非常的简单——无非是遍历吗。然而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低——如果不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不容易达到，因此，为了降低算法的规模，使得算法就复杂了。
在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。
准备工作
一路走下来，图类已经很“臃肿”了，为了更清晰的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。
首先要为基本图类添加几个接口。
template
class Network
{
public:
int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }
dist& getE(int m, int n) { return data.getE(m, n); }
const dist& NoEdge() { return data.NoEdge; }
};
template
class AdjMatrix
{
public:
dist& getE(int m, int n) { return edge; }
};
template
class Link
{
public:
dist& getE(int m, int n)
{
for (list::iterator iter = vertices.e->begin();
iter != vertices.e->end() && iter->vID end()) return NoEdge;
if (iter->vID == n) return iter->cost;
return NoEdge;
}
};
然后就是为了最短路径算法“量身定做”的“算法类”。求某个图的最短路径时，将图绑定到算法上，例如这样：
Network > a(100);
//插入点、边……
Weight > b(&a);
#include "Network.h"
template
class Weight
{
public:
Weight(Network* G) : G(G), all(false), N(G->vNum())
{
length = new dist*; path = new int*;
shortest = new bool; int i, j;
for (i = 0; i getE(i, j);
if (length != G->NoEdge()) path = i;
else path = -1;
}
}
}
~Weight()
{
for (int i = 0; i getV(j) getV(path) ";
}
dist** length; int** path; bool* shortest; bool all; int N;
Network* G;
};
发现有了构造函数真好，算法的结果数组的初始化和算法本身分开了，这样一来，算法的基本步骤就很容易看清楚了。
所有顶点之间的最短路径（Floyed算法）
从v1到v2的路径要么是v1->v2，要么中间经过了若干顶点。显然我们要求的是这些路径中最短的一条。这样一来，问题就很好解决了——最初都是源点到目的点，然后依次添加顶点，使得路径逐渐缩短，顶点都添加完了，算法就结束了。
void AllShortestPath()//Folyed
{
if (all) return;
for (int k = 0; k find(vex1); int v2 = G->find(vex2);
if (shortest) { print(v1, v2); return; }
bool* S = new bool; int i, j, k;
for (i = 0; i < N; i++) S = false; S = true;
for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim?
{
for (j = 0, k = v1; j < N; j++)
if (!S && length < length) k = j;
S = true;
for (j = 0; j < N; j++)
if (!S && length + length < length)
{
length = length + length;
path = k;
}
}
shortest = true; print(v1, v2);
}
如果边的权值有负值，那么上面的原则不再适用，连带的，Dijkstra算法也就不再适用了。这时候，没办法，只有接受O(n3) Bellman-Ford算法了，虽然他可以降低为O(n*e)。不过，何必让边的权值为负值呢？还是那句话，合理的并不好用。
特定两个顶点之间的最短路径（A*算法）
其实这才是我们最关心的问题，我们只是想知道从甲地到乙地怎么走最近，并不想知道别的——甲地到丙地怎么走关我什么事？自然的，我们希望这个算法的时间复杂度为O(n)，但是，正像从Floyed算法到Dijkstra算法的变化一样，并不是很容易达到这个目标的。
让我们先来看看Dijkstra算法求特定两个顶点之间的最短路径的时间复杂度究竟是多少。显然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，当S==true时，算法就可以中止了。假设两个顶点之间直接的路径是他们之间的路径最短的（不需要经过其他中间顶点），并且这个路径长度是源点到所有目的点的最短路径中最短的，那么第一次迭代的时候，就可以得到结果了。也就是说是O(n)。然而当两个顶点的最短路径需要经过其他顶点，或者路径长度不是源点到未求出最短路径的目的点的最短路径中最短的，那就要再进行若干次迭代，对应的，时间复杂度就变为O(2n)、O(3n)……到了最后才求出来（迭代了N－1次）的就是O(n2)。
很明显的，迭代次数是有下限的，最短路径上要经过多少个顶点，至少就要迭代多少次，我们只能使得最终的迭代次数接近最少需要的次数。如果再要减低算法的时间复杂度，我们只能想办法把搜索范围的O(n)变为O(1)，这样，即使迭代了N－1次才得到结果，那时间复杂度仍为O(n)。但这个想法实现起来却是困难重重。
仍然看Dijkstra算法，第一步要寻找S中的顶点到S外面顶点中最短的一条路径，这个min运算使用基于比较的方法的时间复杂度下限是O(longN)（使用败者树），然后需要扫描结果数组的每个分量进行修改，这里的时间复杂度就只能是O(n)了。原始的Dijkstra算法达不到预期的目的。
现在让我们给图添加一个附加条件——两点之间直线最短，就是说如果v1和v2之间有直通的路径（不经过其他顶点），那么这条路径就是他们之间的最短路径。这样一来，如果求的是v1能够直接到达的顶点的最短路径，时间复杂度就是O(1)了，显然比原来最好的O(n)（这里实际上是O(logN)）提高了效率。
这个变化的产生，是因为我们添加了“两点之间直线最短”这样的附加条件，实际上就是引入一个判断准则，把原来盲目的O(n)搜索降到了O(1)。这个思想就是A*算法的思想。关于A*算法更深入的介绍，恕本人资料有限，不能满足大家了。有兴趣的可以到网上查查，这方面的中文资料实在太少了，大家做好看E文的准备吧。
总结
不同于现有的教科书，我把求最短路径的算法的介绍顺序改成了上面的样子。我认为这个顺序才真正反映了问题的本质——当减低问题规模时，为了降低算法的时间复杂度，应该想办法缩小搜索范围。而缩小搜索范围，都用到了一个思想——尽可能的向接近最后结果的方向搜索，这就是贪婪算法的应用。
如果反向看一遍算法的演化，我们还能得出新的结论。Dijkstra算法实际上不用做n2次搜索、比较和修改，当求出最短路径的顶点后，搜索范围已经被缩小了，只是限于储存结构，这种范围的缩小并没有体现出来。如果我们使得这种范围缩小直接体现出来，那么，用n次Dijkstra算法代替Floyed算法就能带来效率上的提升。A*算法也是如此，如果用求n点的A*算法来代替Dijkstra算法，也能带来效率的提升。
但是，每一步的进化实际上都伴随着附加条件的引入。从Floyed到Dijkstra是边上的权值非负，如果这个条件不成立，那么就只能退化成Bellman-Ford算法。从Dijkstra到A*是另外的判断准则的引入（本文中是两点之间直线最短），如果这个条件不成立，同样的，只能采用不完整的Dijkstra（求到目的顶点结束算法）。 其实航空公司们已经算了很久很久了。。。
它们的航线安排就是同样的问题，不过它们用mainframe算而已。 照你这么说，难道我们当真找不到一个好的项目，是不是所有的好项目都早以被人家做过了呢？ 曾经一直在想，既然有" ClimatePrediction研究全球气象变化"，我们为什么不可以搞个"研究中国气象变化"的项目呢，气象数据的获得相对于研究蛋白质的原始数据的获得要容易得多，而且也较一些纯粹的计算项目要有意义！ 欢迎实验结果，虽然我不懂。youngfan，如果需要我可以开放一个equn.com下的ftp目录给你用作实验。 TSP和Prim或Dijsktra有本质区别
TSP是求编历每个点（且不重复经过）的最短（回）路
而Prim则是求连通每一个点的边集合中权最小的那一个解
TSP是NP问题，而Prim或Dijkstra则是O(n^2)级
好项目，不过用分布式是不是大才小用？ 但是这种分布式计算项目太局限了，而且实际成果对于个人作用不是很大
而对于一些组织，相信早已计算出来了 以下是引用碧城仙在2004-7-3 0:45:36的发言：
曾经一直在想，既然有" ClimatePrediction研究全球气象变化"，我们为什么不可以搞个"研究中国气象变化"的项目呢，气象数据的获得相对于研究蛋白质的原始数据的获得要容易得多，而且也较一些纯粹的计算项目要有意义！
气象数据并不是很容易弄的
而且怎么计算也是一个专业问题 这个项目感觉挺有趣的~ 要求条件太多了，不是一天两天能做出来的
