给定一系列城市和每对城市之间的距离,求解访问每座城市一次并回到起始城市的最短回路。
集合:
V
V
V:城市集合
常量:
c
i
j
c_{ij}
cij?:城市
i
i
i到城市
j
j
j之间距离,
i
≠
j
i \neq j
i=j;
变量:
x
i
j
x_{ij}
xij?:是否从城市
i
i
i走到城市
j
j
j;
∑ i ∈ S ∑ j ∈ S , j ≠ i c i j x i j s . t . ∑ i ∈ S , i ≠ j x i j = 1 , ? j ∈ S ∑ j ∈ S , j ≠ i x i j = 1 , ? i ∈ S ∑ i , j ∈ S x i j ≤ ∣ S ∣ ? 1 , 2 ≤ ∣ S ∣ ≤ n ? 1 , S ∈ V \sum_{i \in S}\sum_{j \in S,j \neq i} c_{ij}x_{ij} \\ s.t. \sum_{i \in S, i \neq j} x_{ij} = 1, \forall j \in S \\ \sum_{j \in S, j \neq i} x_{ij} = 1, \forall i \in S \\ \sum_{i,j \in S}x_{ij} \leq \vert S\vert - 1, 2 \leq\vert S\vert\leq n-1,S\in V i∈S∑?j∈S,j=i∑?cij?xij?s.t.i∈S,i=j∑?xij?=1,?j∈Sj∈S,j=i∑?xij?=1,?i∈Si,j∈S∑?xij?≤∣S∣?1,2≤∣S∣≤n?1,S∈V