国外TSP项目介绍
在翻译 http://www.aspenleaf.com/distributed/distrib-recent.html 页面时发现的，原文如下：-------------------------------------------------------------------------------------------------
Genetic TSP used a Java application that ran through a user's web browser and used genetic algorithms to solve a Traveling Salesman Problem (in a TSP, a salesman must find the shortest route in which he/she can visit each a set of cities once and return to his/her starting city). This project attempted to solve a problem of 15,122 cities of Germany. As of December, 2003, the current record-holders of this problem were Princeton University and Rice University.
-------------------------------------------------------------------------------------------------
大意是：
Genetic TSP使用了通过在用户的浏览器中运行Java应用程序并使用遗传算法解决“旅行货郎问题”(在TSP中,推销员必须找到他/她能参观各个城市一次并回到他/她开始的城市的最近路线，即安排一个最短路程的回路)。这个项目试图研究的对象是德国的15,122个城市。截止至2003年12月,项目的记录保持者是普林斯顿大学和早稻田大学。
[ Last edited by 碧城仙 on 2005-1-17 at 05:50 PM ] 又一个，还是在 http://www.aspenleaf.com/distributed/distrib-recent.html 页面发现的：
---------------------------------------------------------------------------------------------------
The fourth challenge was World TSP, a study of the Traveling Salesman Problem （http://www.math.princeton.edu/tsp/ ）. This challenge attempted to find the shortest route which visits all 1,904,711 populated cities and towns on Earth. "The current best lower bound on the length of a tour for the World TSP 7,510,666,782 (Kilometers)." This bound was established on June 18, 2002. The challenge used an evolving artificial intelligence algorithm to attempt to beat that bound. With 97,820 total routes completed, the shortest route discovered was 13,802,932,609 Kilometers.
-------------------------------------------------------------------------------------------------------
其大意是：
第四个挑战是世界TSP，研究Traveling Salesman Problem(旅游推销商问题)。这个挑战试图找出参观地球上所有的近1,904,711个可供居住的城市和城镇的最近路线。“当时世界TSP最短的游览线路长度是7,510,666,782公里。”这个极限值是2002年6月18日得到的,该挑战试图使用一种改进的智能算法突破那个极限值。在完成了97,820条路线测试后, 得到的最近线路长是13,802,932,609公里。
[ Last edited by 碧城仙 on 2005-1-17 at 05:50 PM ] 有意思 值得认真研究！ 遗传算法得到的结果只能是近优的，即不能保证其最优（最短）。
而且遗传算法得到的结果有偶然性，因为其基因序列重组、变异是不确定的
因此即使取得很短的路径也不能过多体现在分布计算方面的成就
以下是引用JUST在2004-7-30 19:05:13的发言：
遗传算法得到的结果只能是近优的，即不能保证其最优（最短）。
而且遗传算法得到的结果有偶然性，因为其基因序列重组、变异是不确定的
因此即使取得很短的路径也不能过多体现在分布计算方面的成就
这个问题本来就没有求最优解的算法（没有穷举以外的判定一个解是否为最优解的算法），因为有偶然性才需要大量的独立的计算来减少它的影响，才需要分布式计算 好帖子!我觉得中国分布式计算从TSP问题起步还是很合适的.不必追求结果是否有意义,开个头,搞点经验是最好的. 以下是引用equn在2004-7-30 21:23:52的发言：
好帖子!我觉得中国分布式计算从TSP问题起步还是很合适的.不必追求结果是否有意义,开个头,搞点经验是最好的.
完全同意此观点！ 以下是引用equn在2004-7-30 21:23:52的发言：
好帖子!我觉得中国分布式计算从TSP问题起步还是很合适的.不必追求结果是否有意义,开个头,搞点经验是最好的.
呵呵，我发的帖子能不好么？此前有些对TSPChina@home提出批评的帖子，说是“不该用JAVA，像浏览器病毒，应该开发客户端，不该取随机路线做测试...”等等，现在看来，老外做的也和TSPChina@home差不多嘛，对于到底该不该用JAVA虚拟机在网页上内嵌分布式项目，等我们正在翻译的页面全部上传后，大家将会看到：绝大部分的项目都是采用的这种形式！！！！！
我认为：TSPChina@home目前唯一欠缺的是“德国人的精确”！
——“德国波恩大学有一位数学家研究西德的120个有铁路穿过的城市，要安排一个最短路程的回路。他从铁路局找到了准确的城市间铁路的长度，整个问题变成一个有7140个变数，120个方程及96个不等式的线性规划问题，用电子计算机去算得到最短的回路是6942公里。”
中国的“准确的城市间铁路的长度”我们哪里能够得到？？？ 以下是引用crazyseti在2004-7-30 20:23:19的发言：
这个问题本来就没有求最优解的算法（没有穷举以外的判定一个解是否为最优解的算法），因为有偶然性才需要大量的独立的计算来减少它的影响，才需要分布式计算
是的，所以我说不能“过多”反应。
不过并不是通过分布式计算来减少偶然性，而是通过分布式计算模拟基因的多样性。
页:
[1]
