案例-旅行商问题

旅行商问题 (TSP)

旅行商问题旨在寻找访问一系列城市并回到起点的最短路径。

1. 问题表示

对于个城市的问题，我们使用个二进制变量。可以想象成一个的矩阵：

如果城市是旅途中的第个访问的城市，则，否则为 0。

2. 构建哈密顿量

总能量函数由两部分组成：。

距离目标项 ()：计算路径总距离。

其中是城市之间的距离。

约束惩罚项 ()：确保每个城市只去一次，且每个位置只有一个城市。

惩罚系数需要大于任何可能的路径总距离。

3. 求解建议

将该模型转换为 QUBO 形式后，在云平台选择 Binary 模型。由于 TSP 约束较多，建议调大惩罚系数以确保获得有效路径。

修改于 2025-12-22 06:42:10

案例-组合投资优化