旅行商问题（TSP）到底是啥？

类似于：你是一位快递员，要开油车去好几个城市送快递，每个城市必须去一次且只能去一次，最后还要回到出发的城市。

汽油很贵，你想找出一条总距离最短的开车路线。

随着城市数量增加，可能的路线数量会爆炸式增长，让传统计算机“想破头”也算不过来（这就是“NP完全问题”的意思）。

【当然这里只是举一个例子，现实遇到的问题肯定都是有爆炸计算量选择的，比如仓库里，一个订单要拿几百件货，散落在巨大的仓库不同货架上。拣货员开着耗费油量巨大的特种设备车，怎么走才能用最短时间拿完所有货？难的地方不是简单顺路，还要考虑货架之间通道宽窄、人流密度、货物重量（重的先拿）、保质期（先拿快过期的）等等（这些就是规则约束）。CIM优势在于可以把每个货架位置、每条路径、每个约束都变成“萤火虫”和“关系规则”，能对每一次的任务快速算出最优拣货路径，每年能为公司省下巨额的油费和工时。因为堵车的时间，绕路的油耗，耽误的件投诉的单都是巨额的无效成本】

 

一、要理解CIM怎么工作

我们先用一个超级简单的例子来看：假设只有 A, B, C, D 4个城市

1. 变量定义：给每位“城市演员”安排“出场序号”
我们需要为每个城市，在每个可能的访问顺序位置上，安排一个“萤火虫”（开关）

定义变量

μ代表城市（比如A、B、C、D）

j代表顺序（比如1、2、3、4）

=1表示：城市 μ在第 j 个被访问

=0表示：城市 μ不在第 j 个被访问

其实就是一个表格图，每个格子是萤火虫所在的x数值，有可能是0/1

我们接下来要上规则进行约束

2. 约束条件（规则）：必须排出一个“合法”的访问顺序
一个好的访问顺序必须满足两条铁律，我们用公式来保证：

规则一：每个城市必须且只能被访问一次

翻译：对于城市A，在“第1位”、“第2位”、“第3位”、“第4位”这四个位置里，有且只有一只代表它的萤火虫可以亮（=1），其他三只必须暗（=0）

（对每个城市μ，也就是横着看，所有位置 j 的萤火虫x加起来必须等于1）。

规则二：每个访问位置只能放一个城市

翻译：“第1位”这个位置上，城市A、B、C、D里有且只有一只萤火虫可以亮（=1），代表这个位置属于那个城市。

 

（对每个位置j，也就是竖着看，所有城市u的x加起来必须等于1）

用表格很容易理解规则，但是

如何把规则变成CIM可以理解的“打分规则”？
在QUBO里，我们不能直接下命令“表格横竖相加必须等于1”，而是用 “惩罚” 的方式：如果违反规则，就扣一个大分（让总成本H急剧增加），系统为了避免扣分，自然就会去遵守规则。

二、我们来看扣分公式：

先看前面那个：

其中括号里面是我们表格的内容，然后选择一列打竖来看，一竖列的4个格子只有一个城市，那么下面这个括号里面

意味着，城市u的萤火虫，在这一顺序列里面点亮的总数正好等于1

那=0

括号里面是0，那整个前面部分的惩罚公式是0，就没得惩罚

如果括号里面不等于0，那么不管你是大于1还是小于1，只要不等于1，平方后就是正数，就会被乘以一个大系数A，给总成本H加上一大笔惩罚分

系统（CIM）在寻找低分（H小）的过程中，就会拼命避免这种情况发生，从而自动满足“每个城市只出现一次”的规则

 

公式后面另一半的规则同理，另一个约束（每个位置只放一个城市）的公式同理。

那光有规则还不够，最终目标是让我们这个路程总距离最短

 

三、距离计算

：就是两个城市之间的距离

：这个等于1，代表了路线中的一段行程。意味着当且仅当城市u在第j个被访问，并且城市v紧挨着在下一个（第j+1个）被访问

 

：是从最后一个城市回到起点的行程

所以，整个就是在计算：根据当前萤火虫亮灭模式所决定的访问顺序，把每一段路程的距离加起来，得到总路程。

 

四、整理公式

合并总目标

：是个 “警察”，专门开罚单。谁不遵守“一城一位、一位一城”的交通规则，就狠狠罚款（加一大笔分）

：是个 “会计”，老老实实算总账（总路程）

最终目标：让 H 总分最小

也就是说，

系统必须在严格遵守交通规则（罚分尽量为0）的前提下，

拼命去找到让总路程（）最短的那个访问顺序。

CIM的工作：我们把设定好系数的这个巨大QUBO模型（H）输入给它。它让代表的萤火虫开始演化，在物理规则驱动下，快速找到一个让H很小的亮灭模式。这个模式一解读出来，就是一连串的，直接告诉我们：城市C第1个访问，城市A第2个访问……这就是最短（或极短）的路线方案。

 

五、完全图和非完全图

完全图：就像在一马平川的平原上，任意两个城市之间都有笔直的公路直达。我们例子默认都是这种。

非完全图：就像在真实的山地，有些城市之间没有直接的路，必须绕道其他城市。这时，城市间的“距离”就需要先用经典算法（如导航）算出最短路径，这个距离可能不是直线，而是绕路后的最短驾驶距离。

 

六、总结

2.1  TSP实例教学-QUBO建模讲解的内容

其实就是把 “快递员找最短环路” 这个具体问题，演示了一遍如何“翻译”成CIM能解的标准数学题（QUBO模型） 的过程：

定义变量：用“萤火虫”表示“哪个城市在第几个被访问”

设定规则：用“高额罚分”迫使系统遵守基本法（一城一次，一位一城）

定义目标：把总路程公式也变成打分的一部分

交给机器：让CIM这个“物理共识生成器”去快速寻找高分（低总成本）方案

旅行商问题（TSP）到底是啥？

类似于：你是一位快递员，要开油车去好几个城市送快递，每个城市必须去一次且只能去一次，最后还要回到出发的城市。

汽油很贵，你想找出一条总距离最短的开车路线。

随着城市数量增加，可能的路线数量会爆炸式增长，让传统计算机“想破头”也算不过来（这就是“NP完全问题”的意思）。

【当然这里只是举一个例子，现实遇到的问题肯定都是有爆炸计算量选择的，比如仓库里，一个订单要拿几百件货，散落在巨大的仓库不同货架上。拣货员开着耗费油量巨大的特种设备车，怎么走才能用最短时间拿完所有货？难的地方不是简单顺路，还要考虑货架之间通道宽窄、人流密度、货物重量（重的先拿）、保质期（先拿快过期的）等等（这些就是规则约束）。CIM优势在于可以把每个货架位置、每条路径、每个约束都变成“萤火虫”和“关系规则”，能对每一次的任务快速算出最优拣货路径，每年能为公司省下巨额的油费和工时。因为堵车的时间，绕路的油耗，耽误的件投诉的单都是巨额的无效成本】

 

一、要理解CIM怎么工作

我们先用一个超级简单的例子来看：假设只有 A, B, C, D 4个城市

1. 变量定义：给每位“城市演员”安排“出场序号”
我们需要为每个城市，在每个可能的访问顺序位置上，安排一个“萤火虫”（开关）

定义变量

μ代表城市（比如A、B、C、D）

j代表顺序（比如1、2、3、4）

=1表示：城市 μ在第 j 个被访问

=0表示：城市 μ不在第 j 个被访问

其实就是一个表格图，每个格子是萤火虫所在的x数值，有可能是0/1

我们接下来要上规则进行约束

2. 约束条件（规则）：必须排出一个“合法”的访问顺序
一个好的访问顺序必须满足两条铁律，我们用公式来保证：

规则一：每个城市必须且只能被访问一次

翻译：对于城市A，在“第1位”、“第2位”、“第3位”、“第4位”这四个位置里，有且只有一只代表它的萤火虫可以亮（=1），其他三只必须暗（=0）

（对每个城市μ，也就是横着看，所有位置 j 的萤火虫x加起来必须等于1）。

规则二：每个访问位置只能放一个城市

翻译：“第1位”这个位置上，城市A、B、C、D里有且只有一只萤火虫可以亮（=1），代表这个位置属于那个城市。

 

（对每个位置j，也就是竖着看，所有城市u的x加起来必须等于1）

用表格很容易理解规则，但是

如何把规则变成CIM可以理解的“打分规则”？
在QUBO里，我们不能直接下命令“表格横竖相加必须等于1”，而是用 “惩罚” 的方式：如果违反规则，就扣一个大分（让总成本H急剧增加），系统为了避免扣分，自然就会去遵守规则。

二、我们来看扣分公式：

先看前面那个：

其中括号里面是我们表格的内容，然后选择一列打竖来看，一竖列的4个格子只有一个城市，那么下面这个括号里面

意味着，城市u的萤火虫，在这一顺序列里面点亮的总数正好等于1

那=0

括号里面是0，那整个前面部分的惩罚公式是0，就没得惩罚

如果括号里面不等于0，那么不管你是大于1还是小于1，只要不等于1，平方后就是正数，就会被乘以一个大系数A，给总成本H加上一大笔惩罚分

系统（CIM）在寻找低分（H小）的过程中，就会拼命避免这种情况发生，从而自动满足“每个城市只出现一次”的规则

 

公式后面另一半的规则同理，另一个约束（每个位置只放一个城市）的公式同理。

那光有规则还不够，最终目标是让我们这个路程总距离最短

 

三、距离计算

：就是两个城市之间的距离

：这个等于1，代表了路线中的一段行程。意味着当且仅当城市u在第j个被访问，并且城市v紧挨着在下一个（第j+1个）被访问

 

：是从最后一个城市回到起点的行程

所以，整个就是在计算：根据当前萤火虫亮灭模式所决定的访问顺序，把每一段路程的距离加起来，得到总路程。

 

四、整理公式

合并总目标

：是个 “警察”，专门开罚单。谁不遵守“一城一位、一位一城”的交通规则，就狠狠罚款（加一大笔分）

：是个 “会计”，老老实实算总账（总路程）

最终目标：让 H 总分最小

也就是说，

系统必须在严格遵守交通规则（罚分尽量为0）的前提下，

拼命去找到让总路程（）最短的那个访问顺序。

CIM的工作：我们把设定好系数的这个巨大QUBO模型（H）输入给它。它让代表的萤火虫开始演化，在物理规则驱动下，快速找到一个让H很小的亮灭模式。这个模式一解读出来，就是一连串的，直接告诉我们：城市C第1个访问，城市A第2个访问……这就是最短（或极短）的路线方案。

 

五、完全图和非完全图

完全图：就像在一马平川的平原上，任意两个城市之间都有笔直的公路直达。我们例子默认都是这种。

非完全图：就像在真实的山地，有些城市之间没有直接的路，必须绕道其他城市。这时，城市间的“距离”就需要先用经典算法（如导航）算出最短路径，这个距离可能不是直线，而是绕路后的最短驾驶距离。

 

六、总结

2.1  TSP实例教学-QUBO建模讲解的内容

其实就是把 “快递员找最短环路” 这个具体问题，演示了一遍如何“翻译”成CIM能解的标准数学题（QUBO模型） 的过程：

定义变量：用“萤火虫”表示“哪个城市在第几个被访问”

设定规则：用“高额罚分”迫使系统遵守基本法（一城一次，一位一城）

定义目标：把总路程公式也变成打分的一部分

交给机器：让CIM这个“物理共识生成器”去快速寻找高分（低总成本）方案