- 人民英雄特朗普 [2020/01]
- 中共下届常委会预测 [2015/09]
- 我们一天天烂下去 [2015/09]
- 张春桥被捕后对中国未来惊人预言 [2019/10]
- 江森哲什么人？ [2019/06]
- 加拿大，艰难大！ [2015/06]
- 一个令人震撼的上海骗子 [2011/12]
- 王沪宁吃了一记响亮耳光 [2015/10]
- 俄罗斯面临危机/美国中东崩溃/中尼铁路/乌军自杀性反攻 [2023/06]
- 莫言诺贝尔文颁奖词的本质是为灭绝中国人制造舆论准备 [2015/10]
- 英文重要，那彭麻麻的英语水平到底如何？ [2015/09]
- 为什么美国不出美女 [2017/03]
- 薄熙来,你大胆往前走！ [2012/02]
- 今日欢呼任大炮 [2020/03]
- 隔山，隔纸，和好自为之 [2015/09]
- 否定毛泽东，就是要否定中国文化！ [2017/01]
- 压力山大---中国出生率低的原因 [2018/10]
- 不可理喻的中国外交 [2017/02]
- 董卿姐姐，明珠暗投 [2019/09]
- 谁更民主？为什么中国不要民主比较好？ [2018/01]
- 上山下乡是人生的最大财富 [2018/11]
- 文明板块的大碰撞，和美国的敌人到底在哪里？ [2017/02]
- 荒唐的请愿，荒唐的闹剧 [2013/05]
- 毛泽东思想没有惹到你吧? [2018/02]
- 崔永元：社会主义的改革 却改成了资本主义私有制 [2018/06]
- 什么元培人？不就反革命么？ [2018/03]
- 对毛的评价其实就是对自己的评价 [2018/02]
- 金三应该得和平奖 [2018/05]
- 川猴奋起千钧棒？ [2023/04]
以TSP为代表的NP问题理论上没有突破，也不会有突破。因为它不是真正的数学问题，所以没啥好研究的。研究的论文铺天盖地，但是并没有什么理论价值。这不是数学理论问题，而比较像是应用数学问题，一个工程问题，甚至是一个软件程序问题。理论讨论没有意义，有价值的仅仅是程序运行效果。
其次，我讨论一下TSP及其相关的一类问题，如货郎担问题，哈密顿环，是不是完全图，对称性，有无权，搜索所有点（即不必回原点）等等。
虽然有种种差别，但为了便于讨论，这里仅仅讨论如下情形：
完全图，同时，非直接连接的两个点（中间经过至少其他一个点）的距离，即两个或更多点距离之和，一定大于这两个点的直接距离。而如果约定是几何距离的概念，无论是二维，是三维，也是确定的。即，如果给与每个点坐标，上述距离的关系一定成立。
但点连接的类TSP问题这一点不一定是必须的。另外，正规的TSP问题不允许重新访问一个点，而符合上述几何概念的对称完全图也没有没有必要回到一个点。但原则上，非完全图，非几何距离概念，也可能允许重复访问。也可以对非完全图做出相应的完全图，一种是将不通两点的距离当作无穷大。另外一种可行性比较好的做法是:如果允许重复访问，那可以把两点（或更多点）之间的距离（之和），当作这两个点的直接距离。但根据笔者的实践，如此将非完全图完全化的处理，减少了信息量，对改进某些算法不利。
此外，对称，有权。
TSP的算法琳琅满目，最主要有遗传，蚁群。但结果都不可重复，随机，每次结果不同，显然都是局优解，陷入其中不可自拔，不满意结果只能从头开始。贪心解法可重复，速度快，但是质量低。穷尽法只能用于点数很少的情况，计算量随点数乘介的增加是其NP问题的原因。
但是如果不能穷尽，TSP原则上无法验证最佳解。好坏只能在最后质量，需要时间等方面在各种方法比较中才显出意义来。一个矛盾是在计算时间和质量之间取得平衡，就是说，通常时间长，质量会好一些。这在实践上时间的限制对质量有了限制。就既可能因为每次结果不同而需要多试几次，但有些运行参数可以帮助取这两方面的平衡和取舍。
因为完全图每一个点都有N-1条连线，在最理想情况下，只有最短（权重最低）的两条被用上。如果最后结果和这个和相等，就完美了。但是对于完全随机产生的数据里，这没有可能。毫无疑问，最优解会分布在同这个和略微大于1的一个高斯分布上。根据我的经验，这个比主要区间在1.1到1.2之间，大体是随着点数，比如从30到3000，而慢慢增加。
笔者的方法是最慢加入法：随机割掉一段，然后以最短的一个点加入，直到最后。这个方法有点类似遗传法，因为结果不一定会比原来的结果好，但你一般总可以找到更好的结果，然后重复这个过程，直到你无论你如何切割，都不能得到更好的结果为止（得到局优解）。
这个算法中用到个点之间的距离，有N（N-1）/2条。如果N够大（比如超过1000），这个计算需要一点时间（如果是比较弱的个人计算机）。但笔者办法得到收敛，而且结果不错，需要的时间也没有多多少。几千点也只需要若干小时。如果几百，那就非常快，若干分钟。
当然，贪心算法只需要若干秒，哪怕几千点，但这个结果很差，只能作为笔者方法的起点。