旅行售货员问题的回溯算法

‘壹’ 9.2 回溯算法的例子

在4 * 4的方格棋盘上放置4个皇后棋子，使得没有两个皇后在同一行、同一列，也不在同一条45度的斜线上， 问有多少种布局?
回溯算法的解一般是向量，而这个题也不例外，设4维向量的<x1,x2,x3,x4>，Xi中i表示第几个皇后，Xi表示在棋盘第i行的位置，比如其中一个解是<2,4,1,3>，如下图

1.四皇后问题中，叶节点就是一个解。
2.四皇后每一个节点的子树代表着下一个皇后可以放的列数，因为都是n，所以子树都是n叉树，故四皇后是一颗 n叉树
3.四皇后的解至少有两个，因为棋盘可以沿着中心线翻折

有n种物品，每种物品只有1个。第i种物品价值为vi，重量为wi，i=1，2，3...n. 问如何选择放入背包的物品，使得总重量不超过B，而价值达到最大?
同样，此问题的解可用一个向量来表示，该向量就代表了所有的物品，如果对应物品为1，则表示装入背包，反之，没有被装入。
因此，回溯的每层可以表示为对应的物品，分支左右可以表示取或者不取（向量中表示为1或0）
总而言之，每一个节点也就是物品只有0和1两种状态，因此该树一棵二叉树，或者为 子集树

1.选择第一个物品，目前总重量为8，总价值为12。
2.再选择第二个物品，总重量为14 > 13，触发回溯。
3.不选择第二个物品，选择第三个商品，总重量是12，总价值为21。
4.再选择第四个物品，总重量为15 > 13，触发回溯。
5.不选择第四个物品，总重量为12，总价值为21，与目前最优解价值进行比较，如果最优解价值大于21则替换目前的最优解向量和最优解价值。

1.背包问题只有在叶节点才能生成一个满足条件的解，而之后将该解和最优解比较。
2.背包问题必须遍历完所有的分支，才能够获得最终的解。
3.背包问题是一颗子集树。

有n个城市，已知任两个城市之间的距离， 求一条每个城市恰好经过一次的回路，使得总长度最小 。
货郎问题中主要的一点就是每一个点（除了第一个点）其他点必须经过且只能经过1次，这就很像数学中的排列。
因此，我们采用一个向量来表示货郎问题的城市排列

1.货郎问题是一颗分支不断减少的排列数（和数学的排列类似）
2.货郎问题也得遍历完所有的情况，比较后得出最优解。

1.解都是用向量表示
2.搜索空间都是树
3.搜索策略多种，有深度优先、宽度优先和跳跃式遍历搜索树。

‘贰’ 什么是回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。 1.跳棋问题： 33个方格顶点摆放着32枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。 算法实现提示 利用回溯算法，每次找到一个可以走的棋子走动，并吃掉。若走到无子可走还是剩余多颗，则回溯，走下一颗可以走动的棋子。当吃掉31颗时说明只剩一颗，程序结束。 2.中国象棋马行线问题： 中国象棋半张棋盘如图1(a)所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如 图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 算法分析： 如图1(b),马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下 一个到达的顶点； S3:打印路径。 算法设计： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {试遍4个方向} if 新坐标满足条件 then begin 记录新坐标; if 到达目的地 then print {统计方案，输出结果} else try(i+1); {试探下一步} 退回到上一个坐标，即回溯; end; end;

‘叁’ 回溯算法的介绍

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

‘肆’ 什么是旅行售货员

一 问题的重述

售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。设有p个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返回原出发地，问这个售货员应该如何选择路线，能使每个城市都经过一次且仅一次，并且行程最短，这就是着名的旅行售货员问题，也即货郎担问题。
用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路，那么目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解，以求得与最优解最为接近的解。

二问题的求解方法

1枚举法
枚举法就是一一列出问题的所有解，然后进行比较，取权值最小的解为最优解，这种方法虽然可以求取问题的最优解，但是我们知道旅行售货员问题是对完全图而言的，对有N个结点的完全图，存在 个不同的哈密顿回路，如果采用枚举法求解，则要对上述数目的不同的哈密顿回路一一进行运算且需要相互之间比较，当N取值较小时，此种求解方法没有任何问题，但若N值较大时，计算量则以级数级别递增，况且没有有效的算法，所以在计算机中也较难实现，故枚举法在大多数的实际应用中是不可取的。

2回溯法
旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1，2，…，n的所有排列的递归算法perm类似。开始时 ，相应的排列树由 的所有排列构成。
在递归算法backtrack中，当i=n时，当前的扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点 到顶点 的边和从顶点 到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时算法还需要判别这条回路的费用是否优于当前已经找到的最优回路的费用bestc。如果是，则必须更新当前的最优值bestc和当前的最优解bestx。
当 时，当前的扩展结点位于排列树的第 层。图G中存在从顶点 到达顶点 的边时， 构成图G中的一条路径，且当 的费用小于当前最优值时算法进入排列树的第i层；否则，则剪去相应的子树。算法中用变量cc记录当前路径 的费用。
3 分枝限界法
分枝限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树时表示问题解空间的一棵有序树，常见的由子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要不同在于它们对当前扩展结点所采用的扩展方式。在分支限界法中，每一个活结点只有一次机会成为扩展检点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点总，导致不可行的解或者非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点，并重复上述扩展过程。这个过程一直持续到找到所需的解或活结点表空为止。
从活结点表中选择下一扩展结点的不同方式将导致不同的分支限界法。最常见的有以下两种方式。
（1）队列式（FIFO）分支限界法
队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出FIFO(first in first out )原则选取下一个结点为当前扩展结点。
（2） 优先队列式分支限界法
优先队列式的分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
优先队列中规定的结点优先级常用一个与该结点相关的数值p表示。结点优先级的高低与p值的大小相关。最大优先队列规定p值较大的结点优先级较高。在算法是现实通常用最大堆来实现最大优先队列，用最大堆的removeMax运算抽取堆中下一个结点成为当前扩展结点，体现最大效益优先的原则。类似的，最小优先队列规定p值较小的结点优先级较高。在算法实现时通常用最小堆来实现最小优先队列，用最小堆的removeMin运算抽取堆中下一个结点成为当前的扩展结点，体现最小费用优先的原则。用优先队列式分支限界法解具体问题式，应该根据具体问题的特点确定选用最大优先队列或者最小优先队列表示解空间的活结点表。
考察4城市旅行售货员的例子，如图3-1所示。该问题的解空间树一棵排列树。解此问题的队列式分支限界法以排列树中结点B作为初始扩展结点。此时，活结点队列为空。由于从图G的顶点1到顶点2，3，4均有边相连，所以结点B的儿子结点C，D，E均为可行结点，它们被加入到活结点队列中，并舍去当前扩展结点B。当前活结点队列中的队首结点C成为下一个扩展结点。由于图G的顶点2到顶点3和4有边相连，故结点C的2个儿子结点F和G均为可行结点，从而被加入到活结点队列中。接下来，结点D和结点E相继成为扩展结点而被扩展。此时，活结点队列中的结点为F，G，H，I，J，K。
结点F成为下一个扩展结点，其儿子结点L是一个叶结点。找到了一条旅行售货员回路，其费用为59。从下一个扩展结点G得到叶结点M，它相应的旅行售货员回路的费用为66。结点H依次成为扩展结点，得到结点N相应的旅行售货员回路，其费用为25。这已经时最好的一条回路。下一个扩展结点时结点I。以结点I为根的子树被剪去。最后，结点J，K被依次扩展，活结点队列成为空，算法终止。算法搜索得到最优值为25，相应的最优解时从根结点到结点N的路径（1，3，2，4，1）。
解同一问题的优先队列式分支限界法用一极小堆来存储活结点表，。其优先级是结点的当前费用。算法还是从排列树的结点B和空优先队列开始。结点B被扩展后，它的3个儿子结点C，D和E被一次插入堆中。此时，由于E是堆中具有最小当前费用的节点，所以处于堆顶位置，它自然成为下一个扩展结点。结点E被扩展后，其儿子结点J和K被插入当前堆中，它们的费用分别为14和24。此时堆顶元素是结点D，它成为下一个结点。如此，它的两个儿子结点H和I被插入堆中。此时，堆中含有结点C，H，I，J，K。在这些结点中，结点H具有最小费用，从而它成为下一个扩展结点。扩展结点H后得到一条旅行售货员回路（1，3，2，4，1），相应的最小费用为25。接下来结点J成为扩展结点，由此得到另外一条旅行售货员回路（1，4，2，3，1），相应的费用为25。此后的扩展结点为K，I。由结点K得到的可行解费用高于当前最优解。结点I本身的费用已高于当前最优解。从而它们都不是最好的解。最后，优先队列为空，算法终止。

图2-1
三 问题的求解结果与算法分析

1问题的求解结果
(1)当结点数为N=4，其各个点之间的边的权矩阵为 时，其最优解为：

图3-1

即其解为(1,4,2,3,1)，最优解值为13。
(2)当结点数为N=5，其各个点之间的边的权矩阵为 时，其最优解为：

图3-2

则其解为（1,5,4,2,3,1），最优解值为18。
(3)当结点数为N=6，其各个点之间的边的权矩阵为 时，其解为：

图3-3

则其解为（1，2，3，4，5，6，1），最优解值为20。
(4)当其结点数为N=7时，其各个点之间的边的权矩阵为 时，其解为：

图3-4

则其解为（1，6，2，7，3，5，4，1）,最优解值为23。

(5)当其结点数为N=8时，其相应的各个点之间的边的权矩阵为 时，
其解为：

图3-5

则其最优解为（1，7，3，5，6，8，2，4，1），最优解值为19。

2算法分析
(1)枚举法
枚举法是最差的一种算法，即将所有可能的结果都排列一次，并比较解与当前最优解的大小，因此其时间复杂度很高，在实际应用中当结点数很多时不可取。
(2)回溯法
如果不考虑更新bestx所需的计算时间，则算法backtrack需要 计算时间。由于算法backtrack在最坏的情况下可能需要更新当前最优解 次，每次更新bestx需 计算时间，从而整个算法的计算时间复杂性为 。
(3)分支限界法
由于是NP问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。此时的时间复杂度也是很高的。

四心得体会

课程设计是对于知识的综合运用，通过学习算法分析也设计了解了一些关于实际问题的解决办法。还有一点就是在学习过程中只停留在书本，只是知道书中某一算法的几个应用的例子。知识面很窄，考虑问题也只会从书本出发。想在例题中是如何解决问题的。其实我们在平常的学习中应该多研究一些实际问题，扩展视野。这样就可以用不同的办法解决同一问题，使用同一方法解决不同问题，也可以使复杂问题简单化。