旅行商问题

描述：给定完全图\(G\)，顶点\(j=0,\cdots,m\)，对于每一对顶点\(j,l\)有边权\(w_{jl}\). 求路径\(p\)，使得每个顶点被经过恰好一次，且花费最小

QUBO范式建模：

• 刻画：
  1. 访问：定义二进制变量\(x_{jl}\in\{0,1\},x_{jl}=\left\{\begin{array}{ll}1,&\text{第}l\text{次访问顶点}j,\\0,&\text{其它}.\end{array}\right.\)\(j,l=0,\cdots,m\)
  2. 唯一性：每个顶点访问一次\(\sum\limits_{l=0}^mx_{jl}=1\)；每次访问一个顶点\(\sum\limits_{j=0}^mx_{jl}=1\)
  3. 优化目标：边权\(w_{jk}\)对答案有贡献\(\Leftrightarrow\exists l\ s.t. x_{j,l}=1\text{且}x_{k,l+1}=1\)，故优化目标为\(\sum\limits_{l=0}^{m-1}\sum\limits_{j=0}^m\sum\limits_{k=0}^mw_{jk}x_{jl}x_{kl+1}\)；同时规定\(w_{jj}=0\)
• 有解问题\(\to\)最值问题：惩罚项
  1. 添加惩罚项：将条件作为惩罚项放入优化目标中\(\begin{array}{rl}\text{minimize}&\sum\limits_{l=0}^{m-1}\sum\limits_{j=0}^m\sum\limits_{k=0}^mw_{jk}x_{jl}x_{kl+1}+B\left(\sum\limits_{l=0}^mx_{jl}-1\right)^2+B\left(\sum\limits_{j=0}^mx_{jl}-1\right)^2\\s.t.&x_{jl}\in\{0,1\},\quad j,l=0,\cdots,m\end{array}\)
  2. 确定惩罚系数：当\(B\)大于所有边权之和时，任何不满足约束的取值都将不会取到当前目标式的最小值。故令\(B=1+\sum\limits_{j,k=0}^mw_{jk}\)