TSP与SAT问题的关系
TSP问题示例
A
B
C
D
E
5
7
4
6
3
8
目标：找出访问所有城市并返回起点的最短路径
SAT问题示例
(x1 OR x2 OR NOT x3) AND
(NOT x1 OR NOT x2 OR x4) AND
(x2 OR NOT x3 OR NOT x4) AND
(x1 OR x3 OR x4)
目标：找出使公式为真的变量赋值
多项式时间归约
变量设计:
x[i,j,p]: 城市i在位置p访问城市j
位置唯一性约束
访问唯一性约束
路径连续性约束
路径长度约束
理论意义
证明了TSP和SAT都是NP完全问题
归约建立了问题之间的桥梁
任何一个问题的多项式解法都意味着P=NP
为算法设计提供了不同视角
启发了混合求解策略的开发