三、练习题： 已知 5 个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5 个城市
的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿 该航线已行的耗油量，并假定从城市 i 到 j 和城市 j 到 i 之间的耗油量是相同的。
分析： 1. 运用贪心思想： 在每一步前进的选择上，选取相对当前城市耗油量最小的航线； 2. 图解：若从 1 出发，有图： 总耗油量=14 1-2-5-3-4-1 但若路线改为：1-5-3-4-2-1，则总耗油量=13 所以，这样的贪心法并不能得出最佳解。 3. 改善方案： 从所有城市出发的信心过程，求最优的。
以深度优先的方式搜索解空间树 T，而分支限界法则以广度优先或以最小耗费优先的方式搜
索解空间树 T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支
），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以 加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函 数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有 最优解的分支推进，以便尽快地找出一个最优解。 二、分支限界法的基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问 题的解空间树是表示问题解空间的一棵有序树，常见的有 子集树和 排列树。在搜索问题 的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界 法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产 生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被 舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展 结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为 止。 三、选择下一扩展结点的不同方式： 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种 方式： 1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的 先进先出原则选取下一个结点为当前扩展结点。 2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 四、习题：
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图 1 6 - 1 用图的 形式给出了一个 3×3 迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了 3×3 迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图 1 6 - 2 用树形结构给出了含三个对象的 0 / 1 背包问题的解空间。从 i 层节点到 i+ 1 层 节点的一条边上的数字给出了向量 x 中第 i 个分量的值 xi ，从根节点到叶节点的每一条路 径定义了解空间中的一个元素。从根节点 A 到叶节点 H 的路径定义了解 x= [ 1 , 1 , 1 ]。 根据 w 和 c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
设置顶点集合 S 并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径
已知时该顶点属于集合 S。初始时 S 中只含源。 设 u 为 G 中一顶点，我们把从源点到 u 且中间仅经过集合 S 中的顶点的路称为从源到 u
特殊 路径，并把这个特殊路径记录下来（例如程序中的 dist[i，j]）。
每次从 V-S 选出具有最短特殊路径长度的顶点 u，将 u 添加到 S 中，同时对特殊路径长 度 进行必要的修改。一旦 V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。
回溯算法 寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完 所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所 有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用 这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用 最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回 溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使 问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可 以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需 要的解。因此，这些方法通常能够用来求解规模很大的问题。
function findmin:integer; var i,len,s1:integer; begin len:=maxint; for i:=1 to n do if (i<>v) and (visit[i]=0) and (c[v,i]
一、分支限界法： 分支限界法类似于回溯法，也是一种在问题的解空间树 T 上搜索问题解的算法。但在一般情
过程结束。
例 4-1 [迷宫老鼠] 考察图 16-3a 的矩阵中给出的 3×3 的“迷宫老鼠”问题。我们将利用 图 1 6 -1 给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图 1 6 - 1 中从( 1 , 1 )到( 3 , 3 )的一条路径相 对应。然而，图 1 6 - 1 中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口 的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个 E-节点。为避免 再次走过这个位置，置 m a z e( 1 , 1 )为 1。从这个位置，能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值 0。假定选 择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为 1 以避免再次经过该点。迷宫当前状态如图 16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为 E-节点。
编程： 1. 数据结构： 城市联系网络图的描述(图的邻接矩阵的描述)： const c=array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3)); 2. 贪心过程： begin 初始化所有城市的算途径标志； 设置出发城市 V； for i:=1 to n-1 do {n-1 个城市} begin s:=从 V 至所有未曾到过的城市的边集中耗油量最少的那个城市； 累加耗油量； V:=s； 设 V 城市的访问标志； end; 最后一个城市返回第一个城市，累加耗油量； end; 3. 主过程：实现改善方案 begin
for i:=1 to n do begin cost1:=maxint; {初始化} 调用贪心过程，返回本次搜索耗油量 cost； if cost<cost1 then 替换； end; 输出； end.
type dim1=array[0..11] of integer;
const c:array[1,
Dijkstra.pas
3、[机器调度]现有 N 项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间
和完成时间有下表：
任务
a
b
c
d
e
f
g
开始(si)
0
3
4
9
7
1
6
完成(fi)
2
7
7
1
1
10
5
8
在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少
的可行分配方案。请就本题给出的条件，求出最优分配。
程序 5 - 1 3 是一个在迷宫中寻找路径的回溯算法。
贪心算法
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当
达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
2、[单源最短路径]一个有向图 G，它的每条边都有一个非负的权值 c[i,j]，“路径长度” 就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短 路径。
E.Dijkstra 发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最 短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如 下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出 T 中满足约束条件的
所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件 的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 由于求解目标不同，导致分支限界法与回溯法在解空间树 T 上的搜索方式也不相同。回溯法
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和 电路板排列问题的求解算法。
1 算法思想
回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首 先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解 （可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径 的解空间；在具有 n 个对象的 0 / 1 背包问题中（见 1 . 4 节和 2 . 2 节），解空间的一个 合 理选择是 2n 个长度为 n 的 0 / 1 向量的集合，这个集合表示了将 0 或 1 分配给 x 的所有可 能方 法。当 n= 3 时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。