搞了一个下午才基本弄明白了k-opt是怎么一回事。

问题大致可以描述成这个样子：一个人计划去好几个地方旅游，想规划好行程，好使得花在路上的时间尽量少。比方说他家在广州，要去帝都、哈尔滨、深圳、珠海四个地方。那最好不要先去北京游玩，然后深圳，然后哈尔滨，然后珠海，这样规划形成估计能把人折磨个半死。一个相对比较好的方案是先去哈尔滨，然后一路南下，北京、深圳、珠海，最后回家。当然，这样的方案有时并不唯一。

只有4、5个城市的情况还比较容易解决。如果有成千上万的城市要游玩，想要直观地找出一条路线或者手动地计算出一条路线就非常困难了：n个城市有n!种游玩路线，在渐进意义下，这比指数增长还要快。想想那个往8×8棋盘上放米粒的故事，你就知道这个数字有多恐怖了。

k-opt就是解决这个问题的方法之一。其基本思想是不管好坏，先找到一条路线，之后再对这条路线进行优化。如果在截至时间前优化已经结束，那么就得到了一个“还算不错”的行程；如果截至时间到了优化过程还没结束，那就把目前位置找到的最好路线报告出来。需要指出的是，即便优化结束了，得到的行程也未必是最优的，它仅仅是局部最优而已。在很多问题（如longest path）中，局部最优并不意味着全局最优，所以我们只能称之为“还算不错”的行程。

很显然，找到一条路线很容易——大不了从头到尾连一遍——所以关键在于怎么对这条路线进行优化。直观上讲，假如我们的路线中出现了交叉，那一般而言这条路线不会太好。还以游玩全国为例，如果我们的行程中桂林的下一站是北京，西安的下一站是上海，两条路线便在鸡胸脯的位置打了个大大的叉。可是，我们干嘛不先在西边把该玩的一次性都玩够了，然后再飞往东部呢？有了这个想法，我们便可以用南北方向的两条平行线来代替这个叉，一条连通西安和桂林，另一条连通北京和上海。（根据图的具体连通情况，这里需要的也可能是东西方向的两条平行线，即将行程规划为南方和北方两大部分。）

如果我们用抽象一点的图来表示，那么两次规划的行程可以表示为：
广州 ==> ... ==> （桂林 ==> 北京 ==> ... ==> 西安 ==> 上海） ==> ... ==> 广州
广州 ==> ... ==> （桂林 ==> 西安 ==> ... ==> 北京 ==> 上海） ==> ... ==> 广州

上面的思路是对两段路进行优化，所以也被称作2-opt。仔细观察可以发现，具体操作起来其实非常简单，只要将北京到西安之间的路线倒过来走就好了。对这个思路进行推广，就可以得到3-opt、4-opt、k-opt，大体就是同时对多段路进行优化。以3-opt为例，其实就是有三段路a、b、c，反复组合着进行2-opt就行了。“反复组合”听起来似乎很玄乎，不过简单的计算可以得出，对于给定的三条边，3-opt只有8种可能的优化结果（其中一些还可能是更差，而非优化），经过3轮2-opt即可全部产生；对于给定的k条边，k-opt共有(k-1)!×2^(k-1)种可能的结果。

通过若干次的看k-opt，我们或是得到一个局部最优结果，或是timeout，于是记录下截至到当前为止的最优结果即可了。

ps：如果时间无限，2-opt好像是可以找到最优的？