目录

• 1.问题描述
  1.1 问题描述
  1.2 各种方法的总结
   1.2.1 分支限界法的总结
   1.2.2 分支限界法与最小生成树、最短路径之间的联系（都借助了贪心性质）
• 2.最优化模型——整数规划
• 3.基于上下界的分支限界法——求解对称型TSP
  3.1 下界（估算）
  3.2 上界——贪心
  3.3 基于上下界的分支限界法——本质上是一样的
  3.4 一个示例
• 4.基于降阶的分支限界法
  4.1 问题描述
  4.2 分支限界法解决旅行商问题
  4.3 一个示例
• 5.直观的回溯法和分支限界法求解
  5.1 实例
  5.2 回溯法——深度优先遍历解空间树
  5.3 分支限界法——广度优先遍历
  5.4 采用基于归约方式的分支限界法
• 6.动态规划
  6.1 刻画一个最优解的结构特征（最优子结构）
  6.2 递归地定义最优解的值（重叠子问题）
  6.3 计算最优解的值，通常采用自底向上的方法
  6.4 利用计算出的信息构造一个最优解
• 7.近似算法
• 8 遗传算法
• 9.模拟退火
• 10.神经网络

1.问题描述

1.1 问题描述

• 一个售货员必须访问n个城市，恰好访问每个城市一次，并最终回到出发城市。
  售货员从城市i到城市j的旅行费用是一个整数，旅行所需的全部费用是他旅行经过的的各边费用之和，而售货员希望使整个旅行费用最低。
• （等价于求图的最短哈密尔顿回路问题）令G=(V, E)是一个带权重的有向图，顶点集V=(v₀, v₁, ..., v_n-1)。从图中任一顶点v_i出发，经图中所有其他顶点一次且只有一次，最后回到同一顶点v_i的最短路径。

1.2 各种方法的总结

1.2.1 分支限界法的总结

• 对于分支限界法的本质，可以描述如下：
  1）通过贪心思想获得一个上界bound
  2）针对一条边进行分支（左边选择该边、右边不选该边），然后对分支计算出下界，如果下界超过上界则剪去该分支；该分支的计算也是使用贪心思想
• 直观的回溯法和分支限界法给的提示：
  1）Hamilton回路经过所有顶点，因此从直观的回溯法和分支限界法对于选择哪个顶点开始搜索没有本质区别
  2）直观的解法给出了解空间树规模大小：(n-1)!，因为从哪个顶点先开始都无所谓，所以是n-1.
• 直观的回溯法和分支限界法没有本质区别，回溯法也可以借助分支限界法的贪心思想：
  1）回溯法可以借助贪心思想，找出一个在贪心操作下的可行解的界
  2）回溯其他分支时，回溯法可以借助贪心思想预测其他分支的下界
  3）但是如果分支众多，回溯法每次总是找最优、次优等（一个点到其他点最优、次优...），但是实际上费用矩阵并不能在O(1)内找到最优值，因为不是排序的，所以O(lgn)都很难做到，n是顶点的个数；——这个计算分散开了
  分支限界法，一次计算出了所有儿子节点的下界（但是这个下界的估算也需要一次性计算出每一行的最小值）。——这个计算时一起算的
• 直观的分支限界法与降阶的分支限界法、动态规划的区别
  1）直观的分支限界法是直接针对可能的解空间树进行遍历的，按照贪心性质（估算的下界最小）；这个是正常的解空间树
  2）降阶的分支限界法是针对一条边的选择与否，造成左右两个分支界限最大的贪心性质选择的，总是选择这样的边首先加入（估算的下界最小）；这个是经过调整的解空间树
  3）基于降阶的分支限界法，本质上与动态规划类似；
  降阶的分支限界法，通过选择该边，转换为了子问题的求解；动态规划也是通过选择一条边，转换成了子问题的求解；
  不过分支限界法是用贪心性质进行选边，动态规划是是通过选择所有可能性的边计算出最小的边。

1.2.2 分支限界法与最小生成树、最短路径之间的联系（都借助了贪心性质）

2.最优化模型——整数规划

• c_ij表示顶点v_i和v_j之间的费用、距离等。
• x_ij若等于1，则表示边v_iv_j在Hamilton回路上；否则就不在。

• 最优化模型（整数规划）如下：

  
  

3.基于上下界的分支限界法——求解对称型TSP

3.1 下界（估算）

• 针对图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得到一个简单的下界b1
• 改进：考虑一个TSP的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出。那么，如果把矩阵中每一行最小的两个元素相加除以2（不失一般性，可以假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界b2。（为什么？试想一种情况：假设进顶点和出顶点的边都是最小。在这种巧合下，就正好是b2）

3.2 上界——贪心

• TSP的任何可行解都是上界，TSP上界的求法是借助贪心方法思想。
  总是选一条最短的且不形成回路，但是最终会形成回路的路径。

3.3 基于上下界的分支限界法——本质上是一样的

• 通过贪心思想获得一个上界bound
• 针对一条边进行分支（左边选择该边、右边不选该边），然后对分支计算出下界，如果下界超过上界则剪去该分支

3.4 一个示例

• step1.计算出上界 U₁ = 16.
  1->3->5->4->2->1
• step2.假定边(1, 3)不在TSP回路中，即e13 = 0，此时，b2 = ((5+3) + (3+6) + (4+2) + (3+4) + (2+3))/2 = 17.5，由于b2 = 17.5 > U1 = 16，因此边(1, 3)一定在回路中，即e13 = 1；
• step3.在e13 = 1的情况下，假定e12 = 0，此时b2 = ((1+5) + (6+7) + (1+2) + (3+4) + (2+3))/2 = 17，由于b2 = 17 > U1 = 16，因此边(1, 2)一定在回路中，即e12 = 1；
• step4.在e12 = e13 = 1的情况下，由于顶点1已有两条关联边在最优回路中，因此在删去边(1, 4)和(1, 5)，由于边(2, 3)与边(1, 2)、(1, 3)形成圈，因此在中删去边(2, 3)，即此时e14 = e15 = e23 = 0；
• step5.在e12 = e13 = 1，e14 = e15 = e23 = 0的情况下，假定e25 = 1，此时b2 = ((1+3) + (3+9) + (1+2) + (3+4) + (2+9))/2 = 18.5，由于b2 = 18.5 > U1 = 16，因此边(2, 5)一定不在回路中，即e25 = 0；

• step6.在e12 = e13 = 1，e14 = e15 = e23 = e25 = 0的情况下，由于与顶点2关联的边有且只有2条在回路中，因此有e24 = 1，进而有e35 = e54 = 1，e34 = 0。

  
  

4.基于降阶的分支限界法

4.1 问题描述

4.1.1 问题描述

• c——费用矩阵（邻接矩阵），c_ij表示顶点v_i到顶点v_j的关联边的长度。

4.1.2 费用矩阵的特性及规约

• 令G=(V, E)是一个带权重的有向图，l是图G的一条哈密尔顿回路，c是图G的费用矩阵，则回路上的边对应于费用矩阵c中每行每列各一个元素。
  证明：因为l上面的每个顶点v_i有且仅有一条入边和出边，入边表示费用矩阵第i列仅有一个元素对应，出边表示费用矩阵第i行仅有一个元素对应。
• 费用矩阵c的第i行（或第j列）中的每个元素减去一个整数lh_i（或ch_j），得到一个新的费用矩阵c'。使得c'中第i行（或第j列）中的最小元素为0，称为费用矩阵的行归约（或列归约）。称lh_i为行归约常数，ch_j为列归约常数。
  

• 对费用矩阵c的每一行和每一列都进行行归约和列归约，得到一个新的费用矩阵c'，使得c'中每一行和每一列至少都有一个元素0，称为费用矩阵的归约。矩阵c'称为费用矩阵c的归约矩阵，称常数h为矩阵c的归约常数。

  
  
• 令G=(V, E)是一个带权重的有向图，l是图G的一条哈密尔顿回路，c是G的费用矩阵，w(l)是以费用矩阵c计算的这条回来的费用。如果c'是费用矩阵c的归约矩阵，归约常数为h，w'(l)是以费用矩阵c'计算的这条回路的费用。则有：
  w(l) = w'(l) + h
• 令G=(V, E)是一个带权重的有向图，l是图G的一条最短哈密尔顿回路，c是G的费用矩阵，c'是c的归约矩阵，G'是与c'对应的图，c'是G'的费用矩阵，则l是G'的一条最短的哈密尔顿回路。

4.2 分支限界法解决旅行商问题

4.2.1 分支方法（二叉分支）

• （分支1）选取沿着某一条边出发的路径，作为进行搜索的一个分支结点
• （分支2）不沿这条边的其他所有路径集合，作为进行搜索的另一个分支结点

4.2.2 下界确定

• 假定父亲结点为X， w(X)是父亲结点的下界。
  现在，选择沿v_iv_j边向下搜索作为其一个分支结点Y；
  不沿v_iv_j边向下搜索作为另一个分支结点Y'。
• 分支Y：
  费用矩阵被降阶和归约，归约常数为h，则w(Y) = w(X) + h
• 分支Y'：
  将c_ij置位∞。
  同时它必然包含费用矩阵中第i行的某个元素和第j列的某个元素，令d_ij为第第i行和第j列中除c_ij之外的最小元素之和。
  如果这两个最小元素不为零，那么也即按照这两个元素进行归约。本质上d_ij也是矩阵进一步的归约常数。
  
  因此有w(Y') = w(X) + d_ij。

4.2.3 分支的选择（贪心）

• 1）沿c_ij 为0的方向选择，使所选择的路线尽可能短。
• 2）在多个c_ij 为0的方向中，沿d_ij最大的方向选择，使w(Y')尽可能大
  令S是费用矩阵中c_ij 为0的元素集合，D_kl是S中使d_ij达到最大的元素，即：
  
  即v_kl就是所要选择的分支方向。

4.2.4 分支限界法的求解步骤

每个结点包含如下信息：
  c——归约过后的费用矩阵
  k——费用矩阵的阶数
  w——下界
  ad——顶点邻接表
bound——一个可行解的取值，当做剪枝的标准

• step1.bound = ∞
• step2.建立父亲结点X
  X.c 为费用矩阵，并进行归约，归约常数为h
  X.k = n
  X.w = h（下界）
  X.ad顶点邻接表
• step3.由X.c中所有为0的c_ij，计算d_ij
• step4.选择使d_ij最大的元素d_kl，选择边v_kl作为分支方向。
  step5是分支Y'的处理
• step5.（分支1）建立儿子结点Y'
  Y'.c = X.c，将Y'.c中元素c_kl置为∞，归约Y'.c
  Y'.ad = X.ad
  Y'.k = X.k
  计算下界Y'.w，并与bound进行比较，根据比较决定是否插入优先队列。
  step6-step9是分支Y的处理
• step6.（分支2）建立儿子结点Y
  Y.c = X.c，根据下图将相应的边置为∞
  Y.ad = X.ad
  Y.k = X.k
  
  
• step7.删除Y.c的第k行与第l列元素
  Y.k = Y.k -1
  归约Y.c
  计算Y.w
• step8.Y.k为2，直接判断最短回路的两条边，并登记Y.ad，使Y.k = 0
• step9. Y.w与bound进行比较，处理是否插入优先队列和更新bound
• step10.取下优先队列元素作为结点X，若X.k为0，算法结束；否则转向step3.

如果选择kl边，置边lk为∞是不行的

4.3 一个示例

5.直观的回溯法和分支限界法求解

• 1）Hamilton回路经过所有顶点，因此从直观的回溯法和分支限界法对于选择哪个顶点开始搜索没有本质区别
• 2）直观的解法给出了解空间树规模大小：(n-1)!，因为从哪个顶点先开始都无所谓，所以是n-1.

5.1 实例

5.2 回溯法——深度优先遍历解空间树

• 回溯法的一个可能改进：从某点开始按照贪心思想进行深度优先
• 贪心思想：如果是从顶点1开始，则选择与顶点1最近的4，然后根据4开始，选择可以组成环路的最近点，直至找到一个可行解。一直在某点以最优->次优->再次等的方式进行搜索。前提条件是能够形成Halmilton回路。
• 界的预测：可以提前预估其下界，按照分支限界法的那种方式

5.3 分支限界法——广度优先遍历

5.4 采用基于归约方式的分支限界法

6.动态规划

6.1 刻画一个最优解的结构特征（最优子结构）

• 假设s₀s₁s₂...s_n，其中s₀=s_n，是一条从s₀出发的最短简单回路。
  那么有s_is_i+1...s_n也是从s_i出发，回到起点s_n的一条最短回路。（cut-and-paste证明）

6.2 递归地定义最优解的值（重叠子问题）

• 设TSP顶点编号为0,1,2,...,n-1.
  假设从顶点0出发
• d(i, V')定义为从顶点i出发经过V'中各顶点有且仅有一次，最后回到顶点0的最短路径长度
• c_ij定义为顶点i到顶点j的距离
  

一个示例：

费用矩阵
递归求解子问题（重叠子问题）

6.3 计算最优解的值，通常采用自底向上的方法

• 假设顶点总数为n
  则6.2中表的i范围是0 ≤ i ≤ n-1，j的范围是0 ≤ j ≤ 2^n-1 - 1

• 一个特别的规律：k表示第k-1位上是否为1，如下图所示

  
  

因此将一个集合转变成了一个数与之对应，数中对应的为位1，表示该数包含在集合中，否则，该数不在集合中。

按程序计算的表格

6.4 利用计算出的信息构造一个最优解

第一个打印0

7.近似算法

8 遗传算法

9.模拟退火

10.神经网络