以TSP为代表的NP问题理论上没有突破，也不会有突破。因为它不是真正的数学问题，所以没啥好研究的。研究的论文铺天盖地，但是并没有什么理论价值。这不是数学理论问题，而比较像是应用数学问题，一个工程问题，甚至是一个软件程序问题。理论讨论没有意义，有价值的仅仅是程序运行效果。 其次，我讨论一下TSP及其相关的一类问题，如货郎担问题，哈密顿环，是不是完全图，对称性，有无权，搜索所有点（即不必回原点）等等。 虽然有种种差别，但为了便于讨论，这里仅仅讨论如下情形： 完全图，同时，非直接连接的两个点（中间经过至少其他一个点）的距离，即两个或更多点距离之和，一定大于这两个点的直接距离。而如果约定是几何距离的概念，无论是二维，是三维，也是确定的。即，如果给与每个点坐标，上述距离的关系一定成立。 但点连接的类TSP问题这一点不一定是必须的。另外，正规的TSP问题不允许重新访问一个点，而符合上述几何概念的对称完全图也没有没有必要回到一个点。但原则上，非完全图，非几何距离概念，也可能允许重复访问。也可以对非完全图做出相应的完全图，一种是将不通两点的距离当作无穷大。另外一种可行性比较好的做法是:如果允许重复访问，那可以把两点（或更多点）之间的距离（之和），当作这两个点的直接距离。但根据笔者的实践，如此将非完全图完全化的处理，减少了信息量，对改进某些算法不利。 此外，对称，有权。 TSP的算法琳琅满目，最主要有遗传，蚁群。但结果都不可重复，随机，每次结果不同，显然都是局优解，陷入其中不可自拔，不满意结果只能从头开始。贪心解法可重复，速度快，但是质量低。穷尽法只能用于点数很少的情况，计算量随点数乘介的增加是其NP问题的原因。 但是如果不能穷尽，TSP原则上无法验证最佳解。好坏只能在最后质量，需要时间等方面在各种方法比较中才显出意义来。一个矛盾是在计算时间和质量之间取得平衡，就是说，通常时间长，质量会好一些。这在实践上时间的限制对质量有了限制。就既可能因为每次结果不同而需要多试几次，但有些运行参数可以帮助取这两方面的平衡和取舍。 因为完全图每一个点都有N-1条连线，在最理想情况下，只有最短（权重最低）的两条被用上。如果最后结果和这个和相等，就完美了。但是对于完全随机产生的数据里，这没有可能。毫无疑问，最优解会分布在同这个和略微大于1的一个高斯分布上。根据我的经验，这个比主要区间在1.1到1.2之间，大体是随着点数，比如从30到3000，而慢慢增加。 笔者的方法是最慢加入法：随机割掉一段，然后以最短的一个点加入，直到最后。这个方法有点类似遗传法，因为结果不一定会比原来的结果好，但你一般总可以找到更好的结果，然后重复这个过程，直到你无论你如何切割，都不能得到更好的结果为止（得到局优解）。 这个算法中用到个点之间的距离，有N（N-1）/2条。如果N够大（比如超过1000），这个计算需要一点时间（如果是比较弱的个人计算机）。但笔者办法得到收敛，而且结果不错，需要的时间也没有多多少。几千点也只需要若干小时。如果几百，那就非常快，若干分钟。 当然，贪心算法只需要若干秒，哪怕几千点，但这个结果很差，只能作为笔者方法的起点。 |
