企业官网建设流程全解析

1. kmeans

K-means 是一种聚类方法：它把一批数据分成K组，让同一组里的点尽量靠近彼此。

在你的项目里，一个城市就是地图上的一个点，例如坐标(x, y)。设定K=32，意思是想把这些城市分成 32 个片区。这里的K是簇的数量，不是算法运行次数。

每个簇都有一个中心点，代表这片区的大致位置。中心通常是簇内所有城市坐标的平均值，因此它不一定对应一座真实城市。K-means 全程只在乎一个数，叫SSE（簇内平方误差）。用人话说：

每个点，量一下它到本组中心的距离，平方，然后全部加起来。

K-means 怎么分组？

可以把它想成在地图上放置 32 个临时服务点：

1. **先放中心。**程序先挑出K个初始中心。项目用的是 K-means++：第一个中心随机选，后面的中心更倾向于选离已有中心较远的城市，让初始中心分布得开一些。
2. **城市找最近中心。**每座城市比较自己到各中心的距离，归到最近的中心所属片区。
3. **片区中心移动。**每个中心移动到自己片区内所有城市坐标的平均位置。
4. **重复分配和移动。**城市可能因为中心移动而改换片区；程序继续重复，直到中心基本不再移动，或达到迭代上限。

最后，K-means 给每座城市一个簇标签，也给出每个簇的中心坐标。

Kmeans本身不直接负责优化路线长度，仅负责聚类，因为 1,577 个城市放在一起直接排访问顺序，问题规模很大，初始路线也不容易构造。先按地理位置分成片区，可以让程序先处理彼此靠近的城市，再把各片区路线连接起来，更容易得到一条合理的起始路线。

2-opt

2-opt 会在环上遍历每条边，用一个双层循环，尝试比较每两条边之间拆了重新组合之后会不会使总长度更短。假设原来有：

a ─ b c ─ d

它会尝试换成：

a ─ c b ─ d

这个变换其实是用反转操作实现的，比如原本的边是a-b-e-f-g-c-d，这里尝试拆的是a-c和b-d并看重新组合后总长度是否减少，其实就是直接将b-e-f-g-c直接反转为了c-g-f-e-b来实现的，因为g-f-e和e-f-g长度是一样的，而我们只关心总长度有没有减少，不关心它的访问顺序是怎样的，所以就直接这样操作了。只有新连接更短，才接受换法。

整个过程

1. 先读地图，计算城市间距离

程序读取fl1577.tsp中每座城市的坐标，并计算城市间的整数距离，算出一个1577*1577的距离矩阵，之后在用到某两点之间的距离时直接查表即可，无需再去计算。矩阵是对称的：从城市 A 到 B 的距离，等于从 B 到 A 的距离。

2. K-means++ 把城市划成片区

由于实验结果在不同的随机种子下取得的效果有所差别，为了获得更好的实验结果与避免实验偶然性，本项目会取5个随机种子（2026到2030），共做5次优化尝试，实验结果取最好的那次。

在某一随机种子的条件下，接下来开始进行分簇，但由于不同的簇数也会对实验结果产生影响，这里同样采取多次取最好的做法，分别取K=16、32、64三种簇数，分簇过程会先选K个初始中心，然后将每个城市归属到距离其最近的初始中心，全部城市归属完毕后，对每个中心所有的城市坐标取平均值，得到这一簇的中心。

由于不同的初始中心也会影响最终实验效果，所以同理，在选初始中心时，也会选择8次，并且这8次都会完整运行 K-means，但程序会根据最终的簇内平方误差（SSE）只保留最好的分簇结果。随后，程序根据该分簇结果构造并优化路线。

所以总的来说，项目最终会进行5*3*8=120次分簇，但只保留15次最好的分簇结果。

3. 确定簇的访问顺序与形成小环

接下来程序先选择0号簇，然后选择距离0号簇最近的那个簇，（用簇中心坐标算），然后依次选距离上一个被选簇最近的簇，依次类推，就能最终得到簇的访问顺序，然后程序按照这个访问顺序依次对每个簇进行处理。

先从0号簇的0号城市开始（0号簇是访问顺序里的第一个簇），然后选距离0号城市最近的城市作为下一个被选择的城市，接着再选离这个城市最近的城市，依次类推得到这个簇的城市访问顺序（如a->c->b->d->e），这个方法也叫做最近邻法，程序将这个城市视作一个首尾相连的环，在使用2-opt算法进行处理时，除了ac、cb、bd、de这些边之外，还会处理ea边。

0号簇的小环形成之后，程序会立即对这个小环进行2-opt处理，优化这个小环的总路线长度，得到一个优化后的小环。这个簇处理完成之后，按照簇的访问顺序开始处理下一个簇，过程是一样的，先按最近邻法排好城市访问顺序，形成小环，然后进行2-opt处理，得到优化后的小环。

接下来程序会将两个环进行合并。每次合并时，程序会遍历当前大环（多个簇小环合并后的环）和新簇小环上的所有边组合，从当前大环选一条边，从新簇小环选一条边，对这两条边分别尝试两种接法，计算每种接法对总长度的影响，选出增加长度最少的一种。

单次选边过程例子：

环 A：城市 P ─ 城市 Q
环 B：城市 R ─ 城市 S

P、Q、R、S是四座不同的城市。程序拆掉这两条旧边，再比较两种连接方式：

接法一：P ─ R，Q ─ S
接法二：P ─ S，Q ─ R

它会选增加距离较少的接法。这样原本两个分开的环就变成一个大环。这就像把两个独立的环形街区道路剪开，再选最省路的一组接口接成一个更大的环。它只保证当前这两个环的这一步合并选了最省的接法，不代表所有片区的整体合并方案都达到了全局最优。

5. 对整个大环做完整 2-opt

所有片区合成一个完整回路（最终大环）后，程序再做一次完整 2-opt，结束后得到一条完整的KMeans+2opt路线；

6. ILS 扰动路线，尝试跳出局部最优

只做 2-opt 有个问题：如果需要先把路线弄长一点，才能最后变得更短，2-opt 通常不会主动走这一步，因为它每次只接受缩短路线的换边。

这里补充两种新的opt方式以及双桥扰动：

• 候选表 2-opt：普通 2-opt 会尝试很多种两边换接法。候选表 2-opt 会优先检查每座城市附近较近的 40 个城市，找到能缩短路线的换法就调整。这样通常更快，但可能漏掉需要连接较远城市的改进。
• Or-opt：从路线中取出连续的 1～3 座城市，整段搬到路线的另一个位置，段内顺序不变；如果新路线更短，就保留这次搬动。
• 双桥扰动是一种故意改变路线结构的操作，目的是让搜索跳出当前卡住的位置。假设把一条闭合路线切成四段：A → B → C → D → 回到 A，双桥扰动会拆开这些段之间的连接，再按另一种顺序接起来。你这个项目里，会把段的顺序改成：A → D → C → B → 回到 A，每一段内部的城市顺序保持不变，变化的是各段之间的连接。所有城市仍然都在路线里、没有重复或遗漏，但新路线可能暂时更长。

因此作为改进，本项目加入了迭代局部搜索（ILS），ILS是Iterated Local Search的缩写，中文通常叫迭代局部搜索。

1. 先用候选表 2-opt 和 Or-opt 把当前路线改善到一个局部最优。
2. 把路线切成四段，用“双桥扰动”改变四段的连接顺序。
3. 扰动可能让路线暂时变长；然后程序再运行局部搜索，把它拉回一个新的局部最优。
4. 如果新路线比历史最好路线短，就更新最好结果；如果长度相同，也允许换成不同路线，增加后续搜索的变化。
5. 如果连续很多轮没找到更短的路线，程序会增加扰动次数，让路线结构改变得更明显。它和普通 2-opt 的主要区别是：2-opt 是小范围换两条边；双桥扰动会重新连接四段路线，跳得更远。
6. 完成 1,500 次扰动后，再用完整 2-opt 收尾。

打个比方：2-opt 是不断修补眼前明显绕远的路；双桥扰动则是把行程中几段调换位置，先走出原来的路线结构（虽然这可能暂时会使总路线变长），再让 2-opt 和 Or-opt 继续打磨。

Or-opt 和 2-opt 的区别是：2-opt 反转一整段路线；Or-opt 则把连续1、2 或 3 座城市作为一个小段，整体搬到另一条边后面，顺序是不变的。它能调整某几个城市在路线中的位置，补充 2-opt 不容易做到的变化。

7. 比较不同参数和随机种子的结果

主程序不只跑一个设置，而是比较：

• 簇数k = 16、32、64。
• 随机种子2026到2030，共 5 个。
• NN+2opt基准：5 次。
• KMeans+2opt：3 种簇数 × 5 个种子，共 15 次。
• KMeans+ILS：同样是 15 次。

所以完整实验一共记录35 条运行结果。对每一条路线，程序都会检查城市是否恰好访问一次，并把路线长度、时间、参数和搜索历史保存下来，去最好的一次为实验结果。