案例-旅行商问题

旅行商问题 (TSP)

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

1. 问题表示

对于

N

个城市的问题，我们使用

N^{2}

个二进制变量。可以想象成一个

N \times N

的矩阵

q_{i, p}

：

如果城市

i

是旅途中的第

p

个访问的城市，则

q_{i, p} = 1

，否则为 0。

2. 构建哈密顿量

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

H = H_{A} + H_{B}

。

距离目标项 ( $H_{A}$ )：计算路径总距离。

H_{A} = \sum_{u, v = 1}^{N} d_{uv} \sum_{p = 1}^{n} q_{u, p} q_{v, p + 1}

其中

d_{uv}

是城市之间的距离。

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

H_{B} = A (\sum_{u = 1}^{N} (1 - \sum_{p = 1}^{n} q_{u, p})^{2} + \sum_{p = 1}^{N} (1 - \sum_{u = 1}^{n} q_{u, p})^{2})

惩罚系数

A

需要大于任何可能的路径总距离。

3. 求解建议

将该模型转换为 QUBO 形式后，在云平台选择 Binary 模型。由于 TSP 约束较多，建议调大惩罚系数

A

以确保获得有效路径。

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

案例-组合投资优化