Six Feelings: 2007-05-06

2007年5月10日星期四

面向上帝的编程语言

转自天涯http://www.tianya.cn/new/publicforum/content.asp?idarticle=64623&stritem=itinfo&idwriter
=0&key=0&flag=1
我们在使用面向对象（OO）的编程语言时，时常感到有些挚肘的地方，可又无法言表，这说明OO技术有不足，网上都有很多这方面的讨论。这里谨是个人粗浅的看法。
　　
　　我和很多人的看法一样，认为软件表达了编程人对客观世界的认识，在软件中我们设计了或表达了现实世界中的对应物。那么就Java而言，她的万物之本Object如何与现实世界对应？
　　
　　可以想象，Object对应于物理学中的基本粒子，我们的万事万物皆来源于此。可是我们知道的基本粒子并不只有一种，什么质子、中子、介子等等。但是有些物理学家在冥冥之中笃信有一种最最基本的粒子，由它构造了我们的世界，因此前赴后继、越钻越深，据说现在已经穷追到了夸克、胶子，也许伟大的终极发现指日可待。那就假设Object对应这个最最最基本粒子吧。我们知道基本粒子都有一种能级跳跃的本事，如果我们万事万物都继承于它们的话，那你我显然也能这么干（不知一人得道鸡犬升天算不算？）。你有没有试过？所以，我们万事万物不是继承于基本粒子，而是由基本粒子所组成，组成后就发生了质变，不是原来的东东了。因此Object不能对应基本粒子。
　　
　　让我们来到精神世界，将Object对应于上帝。世界各国都有将灵性或物品当作神的化身的传说，而神显然又是上帝的化身。在中国有道生一、一生二、二生三、三生万物之说，道就是中国的上帝。而我们软件中的所有东东均来源于Object，显然Object可以对应于上帝。上帝的特点不仅大慈大悲，而且法力无边。可是我们的Object却相对弱智的多。在西方，有天赋人权之说。在中国，上天还赋予我们生存权、发展权，据说最近还多给了我们一种：和谐权。Object有此能耐么？Object仅有8种法力（方法），而且这8种法力还经常无用武之地。不仅如此，在我们的软件中，任何一个家伙，其法力都会大于他，至少也不亚于他。Object是我们软件中最笨拙、最愚蠢的家伙。如果将Object对应于上帝真是OO的本质的话，那这个愚笨的Object是否就是挚肘我们施展拳脚的根源？
　　
　　也许以上都不对，再换一种视角： Object只是我们对万事万物的一种最基本的抽象。这回总算说到点子上了。可是我们的世界总是先有万事万物，然后才能对其中的事物进行抽象。所谓：横看成岭侧成峰。总是先有山在那里，从一个角度去看，我们抽象出“岭”，从另一个角度去看，我们抽象出“峰”，最后我们又进行更高级的抽象：有岭有峰谓之 “山”。在软件世界中，则恰恰相反，我们必须先有抽象，然后再有具体实现。我们先期已经构造了“岭”和“峰”，有一天忽然发现其实更应该构造的是“山”，你说这“山”是继承“岭”还是继承“峰”？于是前功尽废，重新来过。OO的死穴昭然若揭。
　　
　　困难压不倒英雄汉，死穴岂可点大师？大师谆谆教诲我们：要尽量针对接口编程，而非针对实现。也有称之为面向接口。接口这位类的表兄天生就是来化解死穴的。相对类而言，接口才是真正代表了抽象。你说“山”有岭之魂，那就实现一个“岭”的接口；你说“山”有峰之魄，那就再实现一个“峰”的接口。接口在OO家族中虽非直系宗亲，却是我最为敬仰的。看看接口在软件世界中所受到的顶礼膜拜，其程度远远甚于类。任意打开一个中间件的API说明，其中最为扎眼的就是接口。OMG的规范文本开口闭口皆为接口，类则黯然失色。作为类的最高领导，Object的地位显然受到严峻挑战。可他还坐在那至高无上的皇位之上。名不正言不顺啊，怎一个愁字了得。
　　
　　沉舟侧畔千帆过，死穴前头却萦愁。我能化解这千古愁吗？不才汗颜，我哪有这本事？除非我继承了基本粒子，来个能级跳跃。不过冥冥之中我可以有一个梦想，幻想在不久的将来，有一个小子，他实现了能级跳跃（没有继承基本粒子，大概接了口）。他创立了一种语言，不再面向对象，也不面向方面，而是面向上帝（饶恕我的不敬，阿门！）。所有的东东均为上帝的化身，所有的东东从它创立的那一刻起，便有了无限灵性的可能。我们在软件中编写的一切法术，均是属于上帝的，编得愈多，上帝的法力愈大。那位说了，这样的话，你的软件中就不需要其他东东了，所有事情均由上帝代劳可以了。此言差矣，让上帝一人干活，你怎能忍心？没有其他东东，岂不回到混沌世界？在那个世界，无须干任何活。为了抽象，为了表达现实世界的需要，我们和上帝都需要东东。上帝根据某个抽象概念，将必要的法力赋予他所看中的东东，这个东东于是就变成了那个概念所表达的东西了。一旦龙颜不悦，可以随时废了他的功力，他就又变成什么也不是的东东了。打一个现实一点的比方，有一部手机，仅能打电话和接电话。一日，上帝兴起，赋予了它拍照的法力，于是，它就变成了数码相机，同时也还是手机。还需要接口吗？问一问上帝，或查一查它的法力表，就知道它能代表什么概念了。

2007年5月9日星期三

浅谈组策略在系统安全方面的精彩应用

主角闪亮登场
单击“开始”菜单，选择“运行”命令，输入gpedit.msc后按回车键，看！主角组策略粉墨登场了，如图1。
小知识：什么是组策略？
它是Win2000/XP/2003下的一个工具，前身是98下的系统策略编辑器。组策略是系统策略的更高级扩展，它具有更多的管理模板和更灵活的设置对象以及更多的功能，目前主要应用于员Win2000/XP/2003系统。无论是系统策略还是组策略，它们的基本原理都是修改注册表中相应的配置项目，从而达到配置计算机的目的，只是它们的一些运行机制发生了变化和扩展而已。

演出已经开始

1.偷用机器者，一个也跑不了
【位置】计算机配置→Windows设置→安全设置→本地策略→安全选项。
【设置】双击“交互式登录：不显示上次的用户名”，在弹出的属性窗口中选择“已启用”，如图1。

图1

小提示
●在Windows 2000系统下，系统启动时会自动显示出上次登录时的用户名。启用该项策略后，将不再出现上次登录的用户名。这下，小白不怕了，小菜也不担心不知道本机合法登录用户名的黑客入侵了。
● 在Windows XP系统中，默认启动方式下会出现欢迎屏幕，所有用户一览无余。应该先更改用户登录方式。方法是：打开“控制面板”，选择“用户帐户”，在“用户帐户”窗口单击“更改用户登录或注销的方式”，如图2。取消“使用欢迎屏幕”复选框，单击“应用选项”按钮。以后用户登录的界面就和Windows 2000一样了。

图2

2.入侵者戒
【位置】计算机配置→Windows设置→安全设置→帐户策略→帐户锁定策略。
【设置】双击“帐户锁定阈值”策略，设置“3次无效登录”。然后可以把“帐户锁定时间”策略设置为“30”分钟或更长时间。
【功能】当非法用户在3次输入错误密码后，封锁其帐户，禁止登录。

3.谁动了我的奶酪
【位置】计算机配置→Windows设置→安全设置→本地策略→审核策略
【设置】把“审核帐户登录事件”策略设置为“成功、失败”后，打开“事件查看器”，就能查看近期有哪些用户登录过你的电脑了；把“审核过程追踪”策略设置为“成功、失败”，可以察看用户运行过哪些程序。如图3所示，通过事件查看器可以发现用户“罗艳军”运行过QQ.exe程序。

图3

小提示
打开“事件查看器”的方法：单击“开始→运行”，输入“eventvwr.msc”后回车。

4.我的机器你别关
【位置】计算机配置→Windows设置→安全设置→本地策略→用户权利指派
【设置】在“拒绝从网络访问此计算机”策略的属性窗口中添加某一用户，则该用户就没有权利从网络访问这台计算机；在“关闭系统”策略的属性窗口中删除某一群组，如图4所示，则该群组的用户就没有权利关闭系统（该用户的“开始”菜单中没有“关闭计算机”这一菜单项）。

图4

5.访问“控制面板”遭拒
【位置】用户配置→管理模板→控制面板
【设置】双击该策略，在弹出的属性窗口中把该策略设置为“已启用”。
【功能】启用该策略后，当我们双击控制面板时出现一“限制”窗口，内容为“本次操作由于这台计算机的限制而被取消。请与您的系统管理员联系。”

6.“我的电脑”无硬盘？
【位置】用户配置→管理模板→Windows 组件→Windows资源管理器
【设置】双击“隐藏我的电脑中的这些指定的驱动器”策略，选择需要隐藏的驱动器。
【功能】这些被隐藏的驱动器将不会出现在“我的电脑”和“资源管理器”中，在Word的新建或打开窗口中也不会出现。
小提示
还是可以直接在地址栏中输入隐藏的盘符（如D:\）来访问。

7.我的驱动器不对你开放
【位置】用户配置→管理模板→Windows 组件→Windows资源管理器
【设置】双击“防止从我的电脑访问驱动器”策略，弹出属性窗口如图5所示，根据需要选择适当的选项即可。

图5

【功能】上一功能只是隐藏驱动器，但直接输入地址还可以访问，就白了还是捉迷藏而已。要想真正禁止用户使用，就得用这个功能。启用后，就算你看到有这个磁盘，也会提示“本次操作由于这台计算机的限制而被取消。请与您的系统管理员联系”。放心了吧？
小提示
此时在命令提示符状态仍能进入被限制的驱动器，使用DIR命令可查看文件系统，并能运行程序。为了更有效地保护你的系统，请参考下一条措施。

8.DOS高手也傻了眼
【位置】用户配置→管理模板→系统
【设置】双击“阻止访问命令提示符”策略，选择“已启用”，并在“也停用命令提示符脚本处理吗？”下拉列表框中选择“是”。
【功能】当我们使用命令提示符窗口时，将会出现一提示“命令提示符已被系统管理员停用。按任意键继续...”。

9.别乱动注册表编辑器
【位置】用户配置→管理模板→系统
【设置】双击“阻止访问注册表编辑工具”策略，选择“已启用”。同时在“禁止后台运行regedit”后选择“是”。
【功能】运行regedit启动“注册表编辑器”时，会弹出一错误提示“注册编辑已被管理员停用”，从而禁止用户通过注册表编辑器访问注册表。

10.我的程序你别用
【位置】用户配置→管理模板→系统
【设置】双击“不要运行指定的Windows应用程序”策略，选择“已启用”单选按钮，然后单击“显示”按钮，这时将出现一“显示内容”窗口，该窗口中显示的是禁止运行的程序列表。单击“添加”按钮，在文本框中输入禁止运行的程序名称即可，如图6所示。
【功能】当你运行这些被禁止的程序时，将出现提示窗口“本次操作由于这台计算机的限制而被取消。请与您的系统管理员联系。”
小提示
只需输入禁止运行的程序名，不需在程序名前加路径。

怎么样？经过这重重防线的设置，电脑安全多了吧？不过，最后提醒一句：不要自己给自己添乱！因为这些设置是一把双刃剑。不仅可以限制别人，同时，也限制了自己！如果担心熟悉组策略的用户再运行组策略编辑器将相关选项改回来，在图6中填入gpedit.msc吧，这样连组策略编辑器也甭想进来了，呵呵。还是得给自己留下一条后路哟。

图6

常用算法---第 5 章分枝定界【Part3】

5.2.5 电路板排列

电路板排列问题（ 1 6 . 2 . 5节）的解空间是一棵排列树，可以在此树中进行最小耗费分枝定界搜索来找到一个最小密度的电路板排列。我们使用一个最小优先队列，其中元素的类型为B o a r d N o d e，代表活节点。B o a r d N o d e类型的对象包含如下域： x（电路板的排列），s（电路板x[1:s]) 依次放置在位置1 到s 上），c d（电路板排列x [ 1 : s ]的密度，其中包括了到达x[s] 右边的连线），n o w（now[j] 是排列x[1:s] 中包含j 的电路板的数目）。当一个BoardNode 类型的对象转换为整型时，其结果即为对象的cd 值。代码见程序1 7 - 1 0。

程序17-10 电路板排列问题的最小耗费分枝定界算法

int BBArrangeBoards(int **B, int n, int m, int* &bestx)

{// 最小耗费分枝定界算法, m个插槽, n块板

MinHeap H(1000); // 容纳活节点

// 初始化第一个E节点、t o t a l和b e s t d

BoardNode E;

E.x = new int [n+1];

E.s = 0; // 局部排列为E . x [ 1 : s ]

E.cd = 0; // E.x[1:s]的密度

E.now = new int [m+1];

int *total = new int [m+1];

// now[i] = x[1:s]中含插槽i的板的数目

// total[i] = 含插槽i的板的总数目

for (int i = 1; i <= m; i++) { total[i] = 0; E.now[i] = 0; } for (i = 1; i <= n; i++) { E.x[i] = i; // 排列为1 2 3 4 5 . . . n for (int j = 1; j <= m; j++) total[j] += B[i][j]; // 含插槽j的板 } int bestd = m + 1; / /目前的最优密度 bestx = 0; // 空指针 do {// 扩展E节点 if (E.s == n - 1) {// 仅有一个孩子 int ld = 0; // 最后一块板的局部密度 for (int j = 1; j <= m; j++) ld += B[E.x[n]][j]; if (ld < bestx =" E.x;" bestd =" max(ld," i =" E.s" now =" new" j =" 1;" ld =" 0;" j =" 1;"> 0 &&amp; total[j] != N.now[j]) ld++;
N.cd = max(ld, E.cd);

if (N.cd < bestd) {// 可能会引向更好的叶子

N.x = new int [n+1];

N.s = E.s + 1;

for (int j = 1; j <= n; j++)

N.x[j] = E.x[j];

N.x[N.s] = E.x[i];

N.x[i] = E.x[N.s];

H . I n s e r t ( N ) ; }

else delete [] N.now;}

delete [] E.x;} // 处理完当前E-节点

try {H.DeleteMin(E);} // 下一个E-节点

catch (OutOfBounds) {return bestd;} //没有E-节点

} while (E.cd < bestd);

// 释放最小堆中的所有节点

do {delete [] E.x;

delete [] E.now;

try {H.DeleteMin(E);}

catch (...) {break;}

} while (true);

return bestd;

}

程序1 7 - 1 0首先初始化E-节点为排列树的根，此节点中没有任何电路板，因此有s=0, cd=0,n o w [ i ] = 0（1≤i≤n），x是整数1到n 的任意排列。接着，程序生成一个整型数组t o t a l，其中total[i] 的值为包含i 的电路板的数目。目前能找到的最优的电路板排列记录在数组bestx 中，对应的密度存储在bestd 中。程序中使用一个do-while 循环来检查每一个E-节点，在每次循环的尾部，将从最小堆中选出具有最小cd 值的节点作为下一个E-节点。如果某个E-节点的cd 值大于等于bestd，则任何剩余的活节点都不能使我们找到密度小于bestd的电路板排列，因此算法终止。

d o - w h i l e循环分两种情况处理E-节点，第一种是处理s = n - 1时的情况，此种情况下，有n - 1个电路板被放置好， E-节点即解空间树中的某个叶节点的父节点。节点对应的密度会被计算出来，如果需要，bested 和bestx 将被更新。在第二种情况中，E-节点有两个或更多的孩子。每当一个孩子节点N生成时，它对应的部分排列( x [ 1 : s + 1 ] )的密度N . c d就会被计算出来，如果N . c d < b e s t d ,则N被存放在最小优先队列中；如果N . c d≥b e s t d，则它的子树中的所有叶节点对应的密度都满足d e n s i t y≥b e s t d，这就意味着不会有优于b e s t x的排列。

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 5 章分枝定界【Part2】

5.2.2 0/1背包问题

0 / 1背包问题的最大收益分枝定界算法可以由程序1 6 - 6发展而来。可以使用程序1 6 - 6的B o u n d函数来计算活节点N的收益上限u p ,使得以N为根的子树中的任一节点的收益值都不可能超过u p r o f i t。活节点的最大堆使用u p r o f i t作为关键值域，最大堆的每个入口都以H e a p N o d e作为其类型，H e a p N o d e有如下私有成员：uprofit, profit, weight，l e v e l，p t r，其中l e v e l和p t r的定义与装箱问题（见程序1 7 - 5）中的含义相同。对任一节点N，N . p r o f i t是N的收益值，N uprofit是它的收益上限， N. weight 是它对应的重量。b b n o d e类型如程序1 7 - 5中的定义，各节点按其u p r o f i t值从最大堆中取出。

程序1 7 - 7使用了类Knap, 它类似于回溯法中的类K n a p（见程序1 6 - 5）。两个K n a p版本中数据成员之间的区别见程序1 7 - 7：1) bestp 不再是一个成员； 2) bestx 是一个指向int 的新成员。新增成员的作用是：当且仅当物品j 包含在最优解中时， b e s t x [ j ] = 1。函数A d d L i v e N o d e用于将新的b b n o d e类型的活节点插入子集树中，同时将H e a p N o d e类型的活节点插入到最大堆中。这个函数与装箱问题（见程序1 7 - 6）中的对应函数非常类似，因此相应的代码被省略。

程序17-7 0/1背包问题的最大收益分枝定界算法

template

Tp Knap::MaxProfitKnapsack()

{// 返回背包最优装载的收益

// bestx[i] = 1 当且仅当物品i 属于最优装载

// 使用最大收益分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最大堆

H = new MaxHeap > (1000);

// 为b e s t x分配空间

bestx = new int [n+1];

// 初始化层1

int i = 1;

E = 0;

cw = cp = 0;

Tp bestp = 0; // 目前的最优收益

Tp up = Bound(1); // 在根为E的子树中最大可能的收益

// 搜索子集空间树

while (i != n+1) { // 不是叶子

// 检查左孩子

Tw wt = cw + w[i];

if (wt <= c) {// 可行的左孩子 if (cp+p[i] > bestp) bestp = cp+p[i];

AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}

up = Bound(i+1);

// 检查右孩子

if (up >= bestp) // 右孩子有希望

AddLiveNode(up, cp, cw, false, i+1);

// 取下一个E-节点

HeapNode N;

H->DeleteMax(N); // 不能为空

E = N.ptr;

cw = N.weight;

cp = N.profit;

up = N.uprofit;

i = N.level;

}

// 沿着从E-节点E到根的路径构造bestx[]

for (int j = n; j > 0; j--) {

bestx[j] = E-> L C h i l d ;

E = E-> p a r e n t ;

}

return cp;

}

函数M a x P r o f i t K n a p s a c k在子集树中执行最大收益分枝定界搜索。函数假定所有的物品都是按收益密度值的顺序排列，可以使用类似于程序1 6 - 9中回溯算法所使用的预处理代码来完成这种排序。函数M a x P r o f i t K n a p s a c k首先初始化活节点的最大堆，并使用一个数组b e s t x来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将M a x P r o f i t K n a p s a c k所生成的结果映射回初始时的物品索引。可以用Q的I D域来实现上述映射（见程序1 6 - 9）。

在函数M a x P r o f i t K n a p S a c k中，E是当前E-节点，c w是节点对应的重量， c p是收益值，u p是以E为根的子树中任一节点的收益值上限。w h i l e循环一直执行到一个叶节点成为E-节点为止。由于最大堆中的任何剩余节点都不可能具有超过当前叶节点的收益值，因此当前叶即对应了一个最优解。可以从叶返回到根来确定这个最优解。

M a x P r o f i t K n a p s a c k中w h i l e循环的结构很类似于程序1 7 - 6的w h i l e循环。首先，检验E-节点左孩子的可行性，如它是可行的，则将它加入子集树及活节点队列（即最大堆）；仅当节点右孩子的B o u n d值指明有可能找到一个最优解时才将右孩子加入子集树和队列中。

5.2.3 最大完备子图

4 . 2 . 3节完备子图问题的解空间树也是一个子集树，故可以使用与装箱问题、背包问题相同的最大收益分枝定界方法来求解这种问题。解空间树中的节点类型为b b n o d e，而最大优先队列中元素的类型则是C l i q u e N o d e。C l i q u e N o d e有如下域：c n（该节点对应的完备子图中的顶点数目），u n（该节点的子树中任意叶节点所对应的完备子图的最大尺寸），l e v e l（节点在解空间树中的层），c n（当且仅当该节点是其父节点的左孩子时， c n为1），p t r（指向节点在解空间树中的位置）。u n的值等于c n + n - l e v e + 1。因为根据un 和c n（或l e v e l）可以求出l e v e l（或c n），所以可以去掉c n或l e v e l域。当从最大优先队列中选取元素时，选取的是具有最大u n值的元素。在程序1 7 - 8中，C l i q u e N o d e包含了所有的三个域：c n，un 和l e v e l，这样便于尝试为u n赋予不同的含义。函数A d d C l i q u e N o d e用于向生成的子树和最大堆中加入节点，由于其代码非常类似于装箱和背包问题中的对应函数，故将它略去。

函数B B M a x C l i q u e在解空间树中执行最大收益分枝定界搜索，树的根作为初始的E-节点，该节点并没有在所构造的树中明确存储。对于这个节点来说，其cn 值（E-节点对应的完备子图的大小）为0，因为还没有任何顶点被加入完备子图中。E-节点的层由变量i 指示，它的初值为1，对应于树的根节点。当前所找到的最大完备子图的大小保存在b e s t n中。

在while 循环中，不断展开E-节点直到一个叶节点变成E-节点。对于叶节点，u n＝c n。由于所有其他节点的un 值都小于等于当前叶节点对应的un 值，所以它们不可能产生更大的完备子图，因此最大完备子图已经找到。沿着生成的树中从叶节点到根的路径，即可构造出这个最大完备子图。

为了展开一个非叶E-节点，应首先检查它的左孩子，如果左孩子对应的顶点i与当前E-节点所包含的所有顶点之间都有一条边，则i 被加入当前的完备子图之中。为了检查左孩子的可行性，可以沿着从E-节点到根的路径，判断哪些顶点包含在E-节点之中，同时检查这些顶点中每个顶点是否都存在一条到i 的边。如果左孩子是可行的，则把它加入到最大优先队列和正在构造的树中。下一步，如果右孩子的子树中包含最大完备子图对应的叶节点，则把右孩子也加入。
由于每个图都有一个最大完备子图，因此从堆中删除节点时，不需要检验堆是否为空。仅当到达一个可行的叶节点时，w h i l e循环终止。

程序17-8 最大完备子图问题的分枝定界算法

int AdjacencyGraph::BBMaxClique(int bestx[])

{// 寻找一个最大完备子图的最大收益分枝定界程序

// 定义一个最多可容纳1 0 0 0个活节点的最大堆

MaxHeap H(1000);

// 初始化层1

bbnode *E = 0; // 当前的E-节点为根

int i = 1, // E-节点的层

cn = 0, // 完备子图的大小

bestn = 0; // 目前最大完备子图的大小

// 搜索子集空间树

while (i != n+1) {// 不是叶子

// 在当前完备子图中检查顶点i 是否与其它顶点相连

bool OK = true;

bbnode *B = E;

for (int j = i - 1; j > 0; B = B->parent, j--)

if (B->LChild && a[i][j] == NoEdge) {

OK = false;

b r e a k ; }

if (OK) {// 左孩子可行

if (cn + 1 > bestn) bestn = cn + 1;

AddCliqueNode(H, cn+1, cn+n-i+1, i+1, E, true);}

if (cn + n - i >= bestn)

// 右孩子有希望

AddCliqueNode(H, cn, cn+n-i, i+1, E, false);

// 取下一个E-节点

CliqueNode N;

H.DeleteMax(N); // 不能为空

E = N.ptr;

cn = N.cn;

i = N.level;

}

// 沿着从E到根的路径构造bestx[]

for (int j = n; j > 0; j--) {

bestx[j] = E-> L C h i l d ;

E = E-> p a r e n t ;

}

return bestn;

}

5.2.4 旅行商问题

旅行商问题的介绍见4 . 2 . 4节，它的解空间是一个排列树。与在子集树中进行最大收益和最小耗费分枝定界搜索类似，该问题有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。本节只实现前一种方法。

由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为M i n H e a p N o d e。每个节点包括如下区域： x（从1到n的整数排列，其中x [ 0 ] = 1 )，s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [ s + 1 : n - 1 ]），c c（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），l c o s t（该节点子树中任意叶节点中的最小耗费）， r c o s t（从顶点x [ s : n - 1 ]出发的所有边的最小耗费之和）。当类型为M i n H e a p N o d e ( T )的数据被转换成为类型T时，其结果即为l c o s t的值。分枝定界算法的代码见程序1 7 - 9。

程序1 7 - 9首先生成一个容量为1 0 0 0的最小堆，用来表示活节点的最小优先队列。活节点按其l c o s t值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费M i n O u t。如果某些顶点没有出边，则有向图中没有旅行路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子（图1 6 - 5的节点B）作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0, x[0]=1, x[1:n-1]是剩余的顶点（即顶点2 ， 3 ，.， n ）。旅行路径前缀1 的开销为0 ，即c c = 0 ，并且，r c o st=n ?i=1M i n O u t [i]。在程序中，bestc 给出了当前能找到的最少的耗费值。初始时，由于没有找到任何旅行路径，因此b e s t c的值被设为N o E d g e。

程序17-9 旅行商问题的最小耗费分枝定界算法
template

T AdjacencyWDigraph::BBTSP(int v[])

{// 旅行商问题的最小耗费分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最小堆

MinHeap > H(1000);

T *MinOut = new T [n+1];

// 计算MinOut[i] = 离开顶点i的最小耗费边的耗费

T MinSum = 0; // 离开顶点i的最小耗费边的数目

for (int i = 1; i <= n; i++) { T Min = NoEdge; for (int j = 1; j <= n; j++) if (a[i][j] != NoEdge && (a[i][j] < min ="="" min =" a[i][j];" min ="=""> E;

E.x = new int [n];

for (i = 0; i < s =" 0;" cc =" 0;" rcost =" MinSum;" bestc =" NoEdge;" s ="="" bestc ="="" bestc =" E.cc" cc =" bestc;" lcost =" bestc;" i =" E.s" cc =" E.cc" rcost =" E.rcost" b =" cc" bestc ="=""> N;

N.x = new int [n];

for (int j = 0; j < cc =" cc;" s =" E.s" lcost =" b;" rcost =" rcost;" bestc ="="" i =" 0;" s =" n" s =" n" s =" n"> 是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时，它的子节点可行。对于每个可行的孩子节点，将边的耗费加上E.cc 即可得到此孩子节点的路径前缀( x [ 0 : s ]，x[i]) 的耗费c c。由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边，因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和，因而可以把这个下限值作为E-节点所生成孩子的lcost 值。如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c，则把新生成的孩子加入活节点队列（即最小堆）中。

如果有向图没有旅行路径，程序1 7 - 9返回N o E d g e；否则，返回最优旅行路径的耗费，而最优旅行路径的顶点序列存储在数组v 中。

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 5 章分枝定界【Part1】

第 5 章分枝定界

任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是，本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

5.1 算法思想

分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为 E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。

有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：

1) 先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。

2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。

例5-1 [迷宫老鼠] 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（ 1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（ 1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（ 1，2）和（2，1）置为1。此时迷宫如图1 7 - 1 a所示，E-节点（1，1）被删除。

节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（3，1）成为新的E-节点，将队列清空。节点（ 3，1）展开，（3，2）被加入队列中，而（3，1）被删除。（3，2）变为新的E-节点，展开此节点后，到达节点（3，3），即迷宫的出口。

使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的（1，1）位置到（n，n）位置的最短路径的代码。

例5-2 [0/1背包问题] 下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3, w=[20,15,15], p=[40,25,25], c= 3 0。F I F O分枝定界利用一个队列来记录活节点，节点将按照F I F O顺序从队列中取出；而最大收益分枝定界使用一个最大堆，其中的E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例1 6 . 2相同，并且有相同的解空间树。

使用F I F O分枝定界法搜索，初始时以根节点A作为E-节点，此时活节点队列为空。当节点

A 展开时，生成了节点B和C，由于这两个节点都是可行的，因此都被加入活节点队列中，节点A被删除。下一个E-节点是B，展开它并产生了节点D和E，D是不可行的，被删除，而E被加入队列中。下一步节点C成为E-节点，它展开后生成节点F和G，两者都是可行节点，加入队列中。下一个E-节点E生成节点J和 K，J不可行而被删除，K是一个可行的叶节点，并产生一个到目前为止可行的解，它的收益值为4 0。

下一个E-节点是F，它产生两个孩子L、M，L代表一个可行的解且其收益值为5 0，M代表另一个收益值为1 5的可行解。G是最后一个E-节点，它的孩子N和O都是可行的。由于活节点队列变为空，因此搜索过程终止，最佳解的收益值为5 0。

可以看到，工作在解空间树上的F I F O分枝定界方法非常象从根节点出发的宽度优先搜索。它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索。最大收益分枝定界算法以解空间树中的节点A作为初始节点。展开初始节点得到节点B和C，两者都是可行的并被插入堆中，节点B获得的收益值是4 0（设x1 = 1），而节点C得到的收益值为0。A被删除，B成为下一个E-节点，因为它的收益值比C的大。当展开B时得到了节点D和E，D是不可行的而被删除，E加入堆中。由于E具有收益值4 0，而C为0，因为E成为下一个E-节点。

展开E时生成节点J和K，J不可行而被删除，K是一个可行的解，因此K为作为目前能找到的最优解而记录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被展开，生成F、G两个节点插入堆中。F的收益值为2 5，因此成为下一个E-节点，展开后得到节点L和M，但L、M都被删除，因为它们是叶节点，同时L所对应的解被作为当前最优解记录下来。最终，G成为E- 节点，生成的节点为N和O，两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个E-节点产生，搜索过程终止。终止于J的搜索即为最优解。

犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程。定界函数为最大收益设置了一个上限，通过展开一个特殊的节点可能获得这个最大收益。如果一个节点的定界函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点出发，而不是从目前具有较大收益值的节点出发。

例5-3 [旅行商问题] 对于图1 6 - 4的四城市旅行商问题，其对应的解空间为图1 6 - 5所示的排列树。F I F O分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。当B展开时，生成节点C、D和E。由于从顶点1到顶点2，3，4都有边相连，所以C、D、 E三个节点都是可行的并加入队列中。当前的E-节点B被删除，新的E-节点是队列中的第一个节点，即节点C。因为在图1 6 - 4中存在从顶点2到顶点3和4的边，因此展开C，生成节点F和G，两者都被加入队列。下一步，D成为E-节点，接着又是E，到目前为止活节点队列中包含节点F到K。下一个E-节点是F，展开它得到了叶节点L。至此找到了一个旅行路径，它的开销是5 9。展开下一个E-节点G，得到叶节点M，它对应于一个开销为6 6的旅行路径。接着H成为E-节点，从而找到叶节点N，对应开销为2 5的旅行路径。下一个E-节点是I，它对应的部分旅行1 - 3 - 4的开销已经为2 6，超过了目前最优的旅行路径，因此， I不会被展开。最后，节点J，K成为E-节点并被展开。经过这些展开过程，队列变为空，算法结束。找到的最优方案是节点N所对应的旅行路径。

如果不使用F I F O方法，还可以使用最小耗费方法来搜索解空间树，即用一个最小堆来存储活节点。这种方法同样从节点B开始搜索，并使用一个空的活节点列表。当节点B展开时，生成节点C、D和E并将它们加入最小堆中。在最小堆的节点中， E具有最小耗费（因为1 - 4的局部旅行的耗费是4），因此成为E-节点。展开E生成节点J和K并将它们加入最小堆，这两个节点的耗费分别为1 4和2 4。此时，在所有最小堆的节点中，D具有最小耗费，因而成为E-节点，并生成节点H和I。至此，最小堆中包含节点C、H、I、J和K，H具有最小耗费，因此H成为下一个E-节点。展开节点E，得到一个完整的旅行路径1 - 3 - 2 - 4 - 1，它的开销是2 5。节点J是下一个E-节点，展开它得到节点P，它对应于一个耗费为2 5的旅行路径。节点K和I是下两个E-节点。由于I的开销超过了当前最优的旅行路径，因此搜索结束，而剩下的所有活节点都不能使我们找到更优的解。

对于例5 - 2的背包问题，可以使用一个定界函数来减少生成和展开的节点数量。这种函数将确定旅行的最小耗费的下限，这个下限可通过展开某个特定的节点而得到。如果一个节点的定界函数值不能比当前的最优旅行更小，则它将被删除而不被展开。另外，对于最小耗费分枝定界，节点按照它在最小堆中的非降序取出。

在以上几个例子中，可以利用定界函数来降低所产生的树型解空间的节点数目。当设计定界函数时，必须记住主要目的是利用最少的时间，在内存允许的范围内去解决问题。而通过产生具有最少节点的树来解决问题并不是根本的目标。因此，我们需要的是一个能够有效地减少计算时间并因此而使产生的节点数目也减少的定界函数。

回溯法比分枝定界在占用内存方面具有优势。回溯法占用的内存是O（解空间的最大路径长度），而分枝定界所占用的内存为O（解空间大小）。对于一个子集空间，回溯法需要(n)的内存空间，而分枝定界则需要O ( 2n ) 的空间。对于排列空间，回溯需要(n) 的内存空间，分枝定界需要O (n!) 的空间。虽然最大收益（或最小耗费）分枝定界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的节点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。

练习

1. 假定在一个L I F O分枝定界搜索中，活节点列表的行为与堆栈相同，请使用这种方法来解决例5 - 2的背包问题。L I F O分枝定界与回溯有何区别？

2. 对于如下0 / 1背包问题：n=4, p=[4,3,2,1], w=[1,2,3,4], c =6。

1) 画出有四个对象的背包问题的解空间树。

2) 像例1 7 - 2那样，描述用F I F O分枝定界法解决上述问题的过程。

3) 使用程序1 6 - 6的B o u n d函数来计算子树上任一叶节点可能获得的最大收益值，并根据每一步所能得到的最优解对应的定界函数值来判断是否将节点加入活节点列表中。解空间中哪些节点是使用以上机制的F I F O分枝定界方法产生的？

4) 像例1 7 - 2那样，描述用最大收益分枝定界法解决上述问题的过程。

5) 在最大收益分枝定界中，若使用3）中的定界函数，将产生解空间树中的哪些节点？
5.2 应用

5.2.1 货箱装船

1. FIFO分枝定界

4 . 2 . 1节的货箱装船问题主要是寻找第一条船的最大装载方案。这个问题是一个子集选择

问题，它的解空间被组织成一个子集树。对程序1 6 - 1进行改造，即得到程序1 7 - 1中的F I F O分枝定界代码。程序1 7 - 1只是寻找最大装载的重量。

程序17-1 货箱装船问题的F I F O分枝定界算法

template

void AddLiveNode(LinkedQueue &Q, T wt,

T& bestw, int i, int n)

{// 如果不是叶节点，则将节点权值w t加入队列Q

if (i == n) {// 叶子

if (wt > bestw) bestw = wt;}

else Q.Add(wt); // 不是叶子

}

template

T MaxLoading(T w[], T c, int n)

{// 返回最优装载值

// 使用F I F O分枝定界算法

// 为层次1 初始化

LinkedQueue Q; // 活节点队列

Q.Add(-1); //标记本层的尾部

int i = 1; // E-节点的层

T Ew = 0, // E-节点的权值

bestw = 0; // 目前的最优值

// 搜索子集空间树

while (true) {

// 检查E-节点的左孩子

if (Ew + w[i] <= c) // x[i] = 1 AddLiveNode(Q, Ew + w[i], bestw, i, n); // 右孩子总是可行的 AddLiveNode(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一个E-节点 if (Ew == -1) { // 到达层的尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); //添加尾部标记 Q.Delete(Ew); // 取下一个E-节点 i++;} // Ew的层 } } 其中函数MaxLoading 在解空间树中进行分枝定界搜索。链表队列Q用于保存活节点，其中记录着各活节点对应的权值。队列还记录了权值- 1，以标识每一层的活节点的结尾。函数AddLiveNode 用于增加节点（即把节点对应的权值加入活节点队列），该函数首先检验i（当前E-节点在解空间树中的层）是否等于n，如果相等，则已到达了叶节点。叶节点不被加入队列中，因为它们不被展开。搜索中所到达的每个叶节点都对应着一个可行的解，而每个解都会与目前的最优解来比较，以确定最优解。如果i＜n，则节点i 就会被加入队列中。 M a x L o a d i n g函数首先初始化i = 1（因为当前E-节点是根节点），b e s t w = 0（目前最优解的对应值），此时，活节点队列为空。下一步， A - 1被加入队列以说明正处在第一层的末尾。当前E-节点对应的权值为Ew。在while 循环中，首先检查节点的左孩子是否可行。如果可行，则调用A d d L i v e N o d e，然后将右孩子加入队列（此节点必定是可行的），注意到A d d l i v e N o d e可能会失败，因为可能没有足够的内存来给队列增加节点。A d d L i v e N o d e并没有去捕获Q . A d d中的N o M e m异常，这项工作留给用户完成。如果E-节点的两个孩子都已经被生成，则删除该E-节点。从队列中取出下一个E-节点，此时队列必不为空，因为队列中至少含有本层末尾的标识- 1。如果到达了某一层的结尾，则从下一层寻找活节点，当且仅当队列不为空时这些节点存在。当下一层存在活节点时，向队列中加入下一层的结尾标志并开始处理下一层的活节点。 M a x L o a d i n g函数的时间和空间复杂性都是O ( 2n )。 2. 改进我们可以尝试使用程序1 6 - 2的优化方法改进上述问题的求解过程。在程序1 6 - 2中，只有当右孩子对应的重量加上剩余货箱的重量超出b e s t w时，才选择右孩子。而在程序1 7 - 1中，在i变为n之前，b e s t w的值一直保持不变，因此在i等于n之前对右孩子的测试总能成功，因为b e s t w = 0且r > 0。当i等于n时，不会再有节点加入队列中，因此这时对右孩子的测试不再有效。

如想要使右孩子的测试仍然有效，应当提早改变b e s t w的值。我们知道，最优装载的重量是子集树中可行节点的重量的最大值。由于仅在向左子树移动时这些重量才会增大，因此可以在每次进行这种移动时改变b e s t w的值。根据以上思想，我们设计了程序1 7 - 2。当活节点加入队列时，w t不会超过b e s t w，故b e s t w不用更新。因此用一条直接插入M a x L o a d i n g的简单语句取代了函数A d d L i v e N o d e。

程序17-2 对程序1 7 - 1改进之后
template

T MaxLoading(T w[], T c, int n)

{// 返回最优装载值

// 使用F I F O分枝定界算法

// 为层1初始化

LinkedQueue Q; // 活节点队列

Q . A d d ( - 1 ) ; / /标记本层的尾部

int i = 1; // E-节点的层

T Ew = 0, // E-节点的重量

bestw = 0; // 目前的最优值

r = 0; // E-节点中余下的重量

for (int j = 2; j <= n; j++) r += w[i]; // 搜索子集空间树 while (true) { // 检查E-节点的左孩子 T wt = Ew + w[i]; // 左孩子的权值 if (wt <= c) { // 可行的左孩子 if (wt > bestw) bestw = wt;

// 若不是叶子，则添加到队列中

if (i <> bestw && i < ew ="=" t="">

class QNode {

p r i v a t e :

QNode *parent; // 父节点指针

bool LChild; // 当且仅当是父节点的左孩子时，取值为t r u e

T weight; // 由到达本节点的路径所定义的部分解的值

} ;

程序1 7 - 4是新的分枝定界方法的代码。为了避免使用大量的参数来调用A d d L i v e N o d e，可以把该函数定义为一个内部函数。使用内部函数会使空间需求稍有增加。此外，还可以把A d d L i v e N o d e和M a x L o a d i n g定义成类成员函数，这样，它们就可以共享诸如Q , i , n , b e s t w, E , b e s t E和bestw 等类成员。

程序1 7 - 4并未删除类型为Q N o d e的节点。为了删除这些节点，可以保存由A d d L i v e N o d e创建的所有节点的指针，以便在程序结束时删除这些节点。

程序17-4 计算最优子集的分枝定界算法

template

void AddLiveNode(LinkedQueue*> &Q, T wt, int i, int n, T bestw, QNode *E,

QNode *&bestE, int bestx[], bool ch)

{// 如果不是叶节点，则向队列Q中添加一个i 层、重量为w t的活节点

// 新节点是E的一个孩子。当且仅当新节点是左孩子时， c h为t r u e。

// 若是叶子，则c h取值为b e s t x [ n ]

if (i == n) {// 叶子

if (wt == bestw) {

// 目前的最优解

bestE = E;

bestx[n] = ch;}

r e t u r n ; }

// 不是叶子, 添加到队列中

QNode *b;
b = new QNode;

b->weight = wt;

b->parent = E;

b->LChild = ch;

Q . A d d ( b ) ;

}

template

T MaxLoading(T w[], T c, int n, int bestx[])

{// 返回最优装载值，并在b e s t x中返回最优装载

// 使用F I F O分枝定界算法

// 初始化层1

LinkedQueue*> Q; // 活节点队列

Q . A d d ( 0 ) ; // 0 代表本层的尾部

int i = 1; // E-节点的层

T Ew = 0, // E-节点的重量

bestw = 0; // 迄今得到的最优值

r = 0; // E-节点中余下的重量

for (int j = 2; j <= n; j++) r += w[i]; QNode *E = 0, // 当前的E-节点

* b e s t E ; // 目前最优的E-节点

// 搜索子集空间树

while (true) {

// 检查E-节点的左孩子

T wt = Ew + w[i];

if (wt <= c) {// 可行的左孩子 if (wt > bestw) bestw = wt;

AddLiveNode(Q, wt, i, n, bestw, E, bestE, bestx, true);}

// 检查右孩子

if (Ew + r > bestw) AddLiveNode(Q, Ew, i, n, bestw, E, bestE, bestx, false);

Q . D e l e t e ( E ) ; // 下一个E-节点

if (!E) { // 层的尾部

if (Q.IsEmpty()) break;

Q . A d d ( 0 ) ; // 层尾指针

Q . D e l e t e ( E ) ; // 下一个E-节点

i + + ; // E-节点的层次

r -= w[i];} // E-节点中余下的重量

Ew = E-> w e i g h t ; // 新的E-节点的重量

}

// 沿着从b e s t E到根的路径构造x[ ] ， x [ n ]由A d d L i v e N o d e来设置

for (j = n - 1; j > 0; j--) {

bestx[j] = bestE->LChild; // 从b o o l转换为i n t

bestE = bestE-> p a r e n t ;

}

return bestw;

}

4. 最大收益分枝定界

在对子集树进行最大收益分枝定界搜索时，活节点列表是一个最大优先级队列，其中每个活节点x都有一个相应的重量上限（最大收益）。这个重量上限是节点x 相应的重量加上剩余货箱的总重量，所有的活节点按其重量上限的递减顺序变为E-节点。需要注意的是，如果节点x的重量上限是x . u w e i g h t，则在子树中不可能存在重量超过x.uweight 的节点。另外，当叶节点对应的重量等于它的重量上限时，可以得出结论：在最大收益分枝定界算法中，当某个叶节点成为E-节点并且其他任何活节点都不会帮助我们找到具有更大重量的叶节点时，最优装载的搜索终止。

上述策略可以用两种方法来实现。在第一种方法中，最大优先级队列中的活节点都是互相独立的，因此每个活节点内部必须记录从子集树的根到此节点的路径。一旦找到了最优装载所对应的叶节点，就利用这些路径信息来计算x 值。在第二种方法中，除了把节点加入最大优先队列之外，节点还必须放在另一个独立的树结构中，这个树结构用来表示所生成的子集树的一部分。当找到最大装载之后，就可以沿着路径从叶节点一步一步返回到根，从而计算出x 值。

最大优先队列可用HeapNode 类型的最大堆来表示（见程序1 7 - 5）。uweight 是活节点的重量上限，level 是活节点所在子集树的层， ptr 是指向活节点在子集树中位置的指针。子集树中节点的类型是b b n o d e（见程序1 7 - 5）。节点按u w e i g h t值从最大堆中取出。

程序17-5 bbnode 和HeapNode 类

class bbnode {

p r i v a t e :

bbnode *parent; // 父节点指针

bool LChild; // 当且仅当是父节点的左孩子时，取值为t r u e

} ;

template

class HeapNode {

p u b l i c :

operator T () const {return uweight;}

p r i v a t e :

bbnode *ptr; // 活节点指针

T uweight; // 活节点的重量上限

int level; // 活节点所在层

} ;

程序1 7 - 6中的函数A d d L i v e N o d e用于把b b n o d e类型的活节点加到子树中，并把H e a p N o d e类型的活节点插入最大堆。A d d L i v e N o d e必须被定义为b b n o d e和H e a p N o d e的友元。

程序17-6

template

void AddLiveNode(MaxHeap > &H, bbnode *E, T wt, bool ch, int lev)

{// 向最大堆H中增添一个层为l e v上限重量为w t的活节点

// 新节点是E的一个孩子
// 当且仅当新节点是左孩子ch 为t r u e

bbnode *b = new bbnode;

b->parent = E;

b->LChild = ch;

HeapNode N;

N.uweight = wt;

N.level = lev;

N.ptr = b;

H . I n s e r t ( N ) ;

}

template

T MaxLoading(T w[], T c, int n, int bestx[])

{// 返回最优装载值，最优装载方案保存于b e s t x

// 使用最大收益分枝定界算法

// 定义一个最多有1 0 0 0个活节点的最大堆

MaxHeap > H(1000);

// 第一剩余重量的数组

// r[j] 为w [ j + 1 : n ]的重量之和

T *r = new T [n+1];

r[n] = 0;

for (int j = n-1; j > 0; j--)

r[j] = r[j+1] + w[j+1];

// 初始化层1

int i = 1; // E-节点的层

bbnode *E = 0; // 当前E-节点

T Ew = 0; // E-节点的重量

// 搜索子集空间树

while (i != n+1) {// 不在叶子上

// 检查E-节点的孩子

if (Ew + w[i] <= c) {// 可行的左孩子 AddLiveNode(H, E, Ew+w[i]+r[i], true, i+1);} // 右孩子 AddLiveNode(H, E, Ew+r[i], false, i+1); // 取下一个E-节点 HeapNode N;

H.DeleteMax(N); // 不能为空

i = N.level;

E = N.ptr;

Ew = N.uweight - r[i-1];

}

// 沿着从E-节点E到根的路径构造b e s t x [ ]

for (int j = n; j > 0; j--) {

bestx[j] = E->LChild; // 从b o o l转换为i n t

E = E-> p a r e n t ;

}

return Ew;

}

函数M a x L o a d i n g（见程序1 7 - 6）首先定义了一个容量为1 0 0 0的最大堆，因此，可以用它来解决优先队列中活节点数在任何时候都不超过1 0 0 0的装箱问题。对于更大型的问题，需要一个容量更大的最大堆。接着，函数M a x L o a d i n g初始化剩余重量数组r。第i + 1层的节点（即x [ 1 : i ]的值都已确定）对应的剩余容器总重量可以用如下公式求出：

r [i]=n ?j=i + 1w[ j ]。

变量E指向子集树中的当前E-节点，Ew 是该节点对应的重量， i 是它所在的层。初始时，根节点是E-节点，因此取i=1, Ew=0。由于没有明确地存储根节点，因此E的初始值取为0。while 循环用于产生当前E-节点的左、右孩子。如果左孩子是可行的（即它的重量没有超出容量），则将它加入到子集树中并作为一个第i + 1层节点加入最大堆中。一个可行的节点的右孩子也被认为是可行的，它总被加入子树及最大堆中。在完成添加操作后，接着从最大堆中取出下一个E-节点。如果没有下一个E-节点，则不存在可行的解。如果下一个E-节点是叶节点（即是一个层为n + 1的节点），则它代表着一个最优的装载，可以沿着从叶到根的路径来确定装载方案。

5. 说明

1) 使用最大堆来表示活节点的最大优先队列时，需要预测这个队列的最大长度（程序1 7 - 6

中是1 0 0 0）。为了避免这种预测，可以使用一个基于指针的最大优先队列来取代基于数组的队列，这种表示方法见9 . 4节的左高树。

2) bestw表示当前所有可行节点的重量的最大值，而优先队列中可能有许多其u w e i g h t不超过b e s t w的活节点，因此这些节点不可能帮助我们找到最优的叶节点，这些节点浪费了珍贵的队列空间，并且它们的插入/删除动作也浪费了时间，所以可以将这些节点删除。有一种策略可以减少这种浪费，即在插入某个节点之前检查是否有u w e i g h t <>

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 4 章回溯【Part3】

4.2.4 旅行商问题

旅行商问题（例4 . 3）的解空间是一个排列树。这样的树可用函数P e r m (见程序1 - 1 0 )搜索，并可生成元素表的所有排列。如果以x=[1, 2, ., n] 开始，那么通过产生从x2 到xn 的所

有排列，可生成n 顶点旅行商问题的解空间。由于P e r m产生具有相同前缀的所有排列，因此可以容易地改造P e r m，使其不能产生具有不可行前缀（即该前缀没有定义路径）或不可能比当前最优旅行还优的前缀的排列。注意在一个排列空间树中，由任意子树中的叶节点定

义的排列有相同的前缀（如图1 6 - 5所示）。因此，考察时删除特定的前缀等价于搜索期间不

进入相应的子树。旅行商问题的回溯算法可作为类A d j a c e n c y W D i g r a p h（见程序1 2 - 1）的一个成员。在其他例子中，有两个成员函数： t S P和T S P。前者是一个保护或私有成员，后者是一个共享成员。函数G . T S P ( v )返回最少耗费旅行的花费，旅行自身由整型数组v 返回。若网络中无旅行，则返回N o E d g e。t S P在排列空间树中进行递归回溯搜索， T S P是其一个必要的预处理过程。T S P假定x（用来保存到当前节点的路径的整型数组），b e s t x（保存目前发现的最优旅行的整型数组），

c c（类型为T的变量，保存当前节点的局部旅行的耗费），b e s t c（类型为T的变量，保存目前最优解的耗费）已被定义为A d j a c e n c y W D i g r a p h中的静态数据成员。T S P见程序1 6 - 11。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的树。

程序1 6 - 11 旅行商回溯算法的预处理程序

template

T AdjacencyWDigraph::TSP(int v[])

{// 用回溯算法解决旅行商问题

// 返回最优旅游路径的耗费，最优路径存入v [ 1 : n ]

/ /初始化

x = new int [n+1];

// x 是排列

for (int i = 1; i <= n; i++) x[i] = i; bestc = NoEdge; bestx = v; // 使用数组v来存储最优路径 cc = 0; // 搜索x [ 2 : n ]的各种排列 t S P ( 2 ) ; delete [] x; return bestc; } 函数t S P见程序1 6 - 1 2。它的结构与函数P e r m相同。当i=n 时，处在排列树的叶节点的父节点上，并且需要验证从x[n-1] 到x[n] 有一条边，从x[n] 到起点x[1] 也有一条边。若两条边都存在，则发现了一个新旅行。在本例中，需要验证是否该旅行是目前发现的最优旅行。若是，则将旅行和它的耗费分别存入b e s t x与b e s t c中。当i＜n 时，检查当前i-1 层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：1) 有从x[i-1] 到x[i] 的一条边（如果是这样的话， x [ 1 : i ]定义了网络中的一条路径）；2 )路径x[1:i] 的耗费小于当前最优解的耗费。变量cc 保存目前所构造的路径的耗费。每次找到一个更好的旅行时，除了更新bestx 的耗费外， tS P需耗时O ( (n- 1 ) ! )。因为需发生O ( (n-1)!) 次更新且每一次更新的耗费为(n) 时间，因此更新所需时间为O (n* (n- 1 ) ! )。通过使用加强的条件（练习1 6），能减少由tS P搜索的树节点的数量。程序16-12 旅行商问题的迭代回溯算法 void AdjacencyWDigraph::tSP(int i)

{// 旅行商问题的回溯算法

if (i == n) {// 位于一个叶子的父节点

// 通过增加两条边来完成旅行

if (a[x[n-1]][x[n]] != NoEdge &&

a[x[n]][1] != NoEdge &&

(cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc ="="" j =" 1;" bestc =" cc" j =" i;" bestc ="="">

4.2.5 电路板排列

在大规模电子系统的设计中存在着电路板排列问题。这个问题的经典形式为将

n个电路板放置到一个机箱的许多插槽中，（如图1 6 - 8所示）。n个电路板的每一种排

列定义了一种放置方法。令B= {b1 , ., bn }表示这n个电路板。m个网组集合L= {N1,

., Nm }由电路板定义，Ni 是B的子集，子集中的元素需要连接起来。实际中用电线

将插有这些电路板的插槽连接起来。

例4 - 11 令n=8, m= 5。集合B和L如下：

B= {b1, b2, b3, b4, b5, b6, b7, b8 }

L= {N1, N2, N3, N4, N5 }

N1 = {b4, b5, b6 }

N2 = {b2, b3 }

N3 = {b1, b3 }

N4 = {b3, b6 }

N5 = {b7, b8 }

令x 为电路板的一个排列。电路板xi 被放置到机箱的插槽i 中。d e n s i t y(x) 为机箱中任意一对相邻插槽间所连电线数目中的最大值。对于图1 6 - 9中的排列，d e n s i t y为2。有两根电线连接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之间无电线，余下的相邻插槽都只有一根电线。板式机箱被设计成具有相同的相邻插槽间距，因此这个间距决定了机箱的大小。该间距必须保证足够大以便容纳相邻插槽间的连线。因此这个距离（继而机箱的大小）由d e n s i t y(x)决定。

电路板排列问题的目标是找到一种电路板的排列方式，使其有最小的d e n s i t y。既然该问题是一个N P-复杂问题，故它不可能由一个多项式时间的算法来解决，而象回溯这样的搜索方法则是解决该问题的一种较好方法。回溯算法为了找到最优的电路板排列方式，将搜索一个排列空间。

用一个n×m 的整型数组B表示输入，当且仅当Nj 中包含电路板bi 时，B [ i ] [ j ] = 1。令t o t a l [ j ]为Nj 中电路板的数量。对于任意部分的电路板排列x [ 1 : i ]，令n o w [ j ]为既在x [ 1 : i ]中又被包含在Nj 中的电路板的数量。当且仅当n o w [ j ] > 0且n o w [ j ]≠t o t a l [ j ]时，Nj 在插槽i 和i + 1之间有连线。插槽i 和i + 1间的线密度可利用该测试方法计算出来。在插槽k和k + 1 ( 1≤k≤i ) 间的线密度的最大值给出了局部排列的密度。

为了实现电路板排列问题的回溯算法，使用了类B o a r d（见程序1 6 - 1 3）。程序1 6 - 1 4给出了私有方法B e s t O r d e r，程序1 6 - 1 5给出了函数A r r a n g e B o a r d s。ArrangeBoards 返回最优的电路板排列密度，最优的排列由数组bestx 返回。ArrangeBoards 创建类Board 的一个成员x 并初始化与之相关的变量。尤其是total 被初始化以使total[j] 等于Nj 中电路板的数量。now[1:n] 被置为0，与一个空的局部排列相对应。调用x .BestOrder(1,0) 搜索x[1:n] 的排列树，以从密度为0的空排列中找到一个最优的排列。通常，x.BestOrder(i,cd) 寻找最优的局部排列x [ 1 : i - 1 ]，该局部排列密度为c d。函数B e s t O r d e r（见程序1 6 - 1 4）和程序1 6 - 1 2有同样的结构，它也搜索一个排列空间。当i=n 时，表示所有的电路板已被放置且cd 为排列的密度。既然这个算法只寻找那些比当前最优排列还优的排列，所以不必验证cd 是否比beste 要小。当i<= n; j++) bestx[j] = x[j]; bestd = cd;} else // 尝试子树 for (int j = i; j <= n; j++) { // 用x[j] 作为下一块电路板对孩子进行尝试 // 在最后一个插槽更新并计算密度 int ld = 0; for (int k = 1; k <= m; k++) { now[k] += B[x[j]][k]; if (now[k] > 0 && total[k] != now[k])

l d + + ;

}

// 更新ld 为局部排列的总密度

if (cd > ld) ld = cd;

// 仅当子树中包含一个更优的排列时，搜索该子树

if (ld < k =" 1;" x =" new" total =" new" now =" new" b =" B;" n =" n;" m =" m;" bestx =" bestx;" bestd =" m" i =" 1;" i =" 1;" j =" 1;">

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 4 章回溯【Part2】

4.2.2 0/1背包问题

0 / 1背包问题是一个N P-复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 . 2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的形状（如图1 6 - 2所示）。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。

与程序1 6 - 2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是令r 为还未遍历的对象的收益之和，将r 加到c p（当前节点所获收益）之上，若（ r + c p）≤b e s t p（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度pi / wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。

例4-7 考察一个背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3 , 2 , 3 . 5 , 4 ]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可容纳对象2的0 . 2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为x= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2 2。尽管该解不可行（x2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 / 1背包问题没有收益值多于2 2的解。

解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，x1= 1，目前获益为c p= 9。该节点所用容量为c w= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量c l e f t=ccw= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 . 2倍的重量。因此，子树A的最优解的收益值至多为2 2。当位于节点C时，c p=c w= 0，c l e f t= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1 9。在子树C中没有节点可产生出比1 9还大的收益值。

在节点E，c p= 9，c w= 3，c l e f t= 4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树E中无节点有多于c p+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索E子树。

一种实现限界函数的好方法是首先将对象按密度排序。假定已经做了这样的排序。定义类K n a p（见程序1 6 - 5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 - 7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 - 2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。

程序16-5 Knap类

template

class Knap {

friend Tp Knapsack(Tp *, Tw *, Tw, int);

p r i v a t e :

Tp Bound(int i);

void Knapsack(int i);

Tw c; / /背包容量

int n; // 对象数目

Tw *w; // 对象重量的数组

Tp *p; // 对象收益的数组

Tw cw; // 当前背包的重量

Tp cp; // 当前背包的收益

Tp bestp; // 迄今最大的收益

} ;

程序16-6 限界函数

template

Tp Knap::Bound(int i)

{// 返回子树中最优叶子的上限值Return upper bound on value of

// best leaf in subtree.

Tw cleft = c - cw; // 剩余容量

Tp b = cp; // 收益的界限

// 按照收益密度的次序装填剩余容量

while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i + + ; } // 取下一个对象的一部分 if (i <= n) b += p[i]/w[i] * cleft; return b; } 程序16-7 0/1背包问题的迭代函数 template

void Knap::Knapsack(int i)

{// 从第i 层节点搜索

if (i > n) {// 在叶节点上

bestp = cp;

r e t u r n ; }

// 检查子树

if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; cp += p[i]; K n a p s a c k ( i + 1 ) ; cw -= w[i]; cp -= p[i];} if (Bound(i+1) > bestp) // 尝试x[i] = 0

K n a p s a c k ( i + 1 ) ;

}

在执行程序1 6 - 7的函数Kn a p s a c k之前，需要按密度对对象排序，也要确保对象的重量总和超出背包的容量。为了完成排序，定义了类O b j e c t（见程序1 6 - 8）。注意定义操作符< =是为了使归并排序程序（见程序1 4 - 3）能按密度递减的顺序排序。程序16-8 Object类 class Object { friend int Knapsack(int *, int *, int, int); p u b l i c : int operator<=(Object a) const {return (d >= a.d);}

p r i v a t e :

int ID; // 对象号

float d; // 收益密度

} ;

程序1 6 - 9首先验证重量之和超出背包容量，然后排序对象，在执行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的复杂性是O (n2n )，因为限界函数的复杂性为O (n)，且该函数在O ( 2n )个右孩子处被计算。

程序16-9 程序1 6 - 7的预处理代码

template

Tp Knapsack(Tp p[], Tw w[], Tw c, int n)

{// 返回最优装包的值

// 初始化

Tw W = 0; // 记录重量之和

Tp P = 0; // 记录收益之和

// 定义一个按收益密度排序的对象数组

Object *Q = new Object [n];

for (int i = 1; i <= n; i++) { // 收益密度的数组 Q[i-1].ID = i; Q[i-1].d = 1.0*p[i]/w[i]; P += p[i]; W += w[i]; } if (W <= c) return P; // 可容纳所有对象 MergeSort(Q,n); // 按密度排序 // 创建K n a p的成员 K n a p <> K;

K.p = new Tp [n+1];

K.w = new Tw [n+1];

for (i = 1; i <= n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; // 寻找最优收益 K . K n a p s a c k ( 1 ) ; delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; }

4.2.3 最大完备子图

令U为无向图G的顶点的子集，当且仅当对于U中的任意点u 和v，(u , v)是图G的一条边时，U定义了一个完全子图（complete subgraph）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时，它是图G的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。

例4-8 在图16-7a 中，子集{ 1 , 2 }定义了一个尺寸为2的完全子图。这个子图不是一个完备子图，因为它被包含在一个更大的完全子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定义了该图的一个最大的完备子图。点集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定义了其他的最大的完备子图。

当且仅当对于U中任意点u 和v，(u , v) 不是G的一条边时，U定义了一个空子图。当且仅当一个子集不被包含在一个更大的点集中时，该点集是图G的一个独立集（independent set），同时它也定义了图G的空子图。最大独立集是具有最大尺寸的独立集。对于任意图G，它的补图（c o m p l e m e n t）是有同样点集的图，且当且仅当（ u,v）不是G的一条边时，它是的一条边。

例4-9 图16-7b 是图16-7a 的补图，反之亦然。{ 2 , 4 }定义了16-7a 的一个空子图，它也是该图的一个最大独立集。虽然{ 1 , 2 }定义了图16-7b 的一个空子图，它不是一个独立集，因为它被包含在空子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }是图16-7b 中的一个最大独立集。

如果U定义了G的一个完全子图，则它也定义了的一个空子图，反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的， G的一个最大完备子图定义了的一个最大独立集。

最大完备子图问题是指寻找图G的一个最大完备子图。类似地，最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是N P-复杂问题。当用算法解决其中一个问题时，也就解决了另一个问题。例如，如果有一个求解最大完备子图问题的算法，则也能解决最大独立集问题，方法是首先计算所给图的补图，然后寻找补图的最大完备子图。

例4-10 假定有一个n 个动物构成的集合。可以定义一个有n 个顶点的相容图（c o m p a t i b i l i t yg r a p h）G。当且仅当动物u 和v 相容时，（u,v）是G的一条边。G的一个最大完备子图定义了相互间相容的动物构成的最大子集。

3 . 2节考察了如何找到一个具有最大尺寸的互不交叉的网组的集合问题。可以把这个问题看作是一个最大独立集问题。定义一个图，图中每个顶点表示一个网组。当且仅当两个顶点对应的网组交叉时，它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端，而另一个在底端时，非交叉网组的最大尺寸的子集能在多项式时间（实际上是(n2 )）内用动态规划算法得到。当一个网组的端点可能在平面中的任意地方时，不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。最大完备子图问题和最大独立集问题可由回溯算法在O (n2n )时间内解决。两个问题都可使用子集解空间树（如图1 6 - 2所示）。考察最大完备子图问题，该递归回溯算法与程序1 6 - 3非常类似。当试图移动到空间树的i 层节点Z的左孩子时，需要证明从顶点i 到每一个其他的顶点j（xj = 1且j 在从根到Z的路径上）有一条边。当试图移动到Z的右孩子时，需要证明还有足够多的顶点未被搜索，以便在右子树有可能找到一个较大的完备子图。

回溯算法可作为类A d j a c e n c y G r a p h（见程序1 2 - 4）的一个成员来实现，为此首先要在该类

中加入私有静态成员x（整型数组，用于存储到当前节点的路径），b e s t x（整型数组，保存目

前的最优解），b e s t n（b e s t x中点的数量），c n（x 中点的数量）。所以类A d j a c e c y G r a p h的所有实

例都能共享这些变量。

函数m a x C l i q u e（见程序1 6 - 1 0）是类A d j a c e n c y G r a p h的一个私有成员，而M a x C l i q u e是一个

共享成员。函数m a x C l i q u e对解空间树进行搜索，而M a x C i q u e初始化必要的变量。M a x c l i q u e ( v )

的执行返回最大完备子图的尺寸，同时它也设置整型数组v，当且仅当顶点i 不是所找到的最大

完备子图的一个成员时，v [ i ] = 0。

程序16-10 最大完备子图

void AdjacencyGraph::maxClique(int i)

{// 计算最大完备子图的回溯代码

if (i > n) {// 在叶子上

// 找到一个更大的完备子图，更新

for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; r e t u r n ; } // 在当前完备子图中检查顶点i是否与其它顶点相连 int OK = 1; for (int j = 1; j < ok =" 0;"> bestn) {// 尝试x[i] = 0

x[i] = 0;

m a x C l i q u e ( i + 1 ) ; }

}

int AdjacencyGraph::MaxClique(int v[])

{// 返回最大完备子图的大小

// 完备子图的顶点放入v [ 1 : n ]

// 初始化

x = new int [n+1];

cn = 0;

bestn = 0;

bestx = v;

// 寻找最大完备子图

m a x C l i q u e ( 1 ) ;

delete [] x;

return bestn;

}

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 4 章回溯【Part1】

第 4 章回溯

寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。

本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。

4.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 ) }。

下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图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 的值，从根到叶的路径中的一些解或全部解可能是不可行的。

一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。

例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 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3 )为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。

程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。

例4-2 [0/1背包问题] 考察如下背包问题：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。从根节点开始搜索图1 6 - 2中的树。根节点是当前唯一的活节点，也是E-节点，从这里能够移动到B或C点。假设移动到B，则活节点为A和B。B是当前E-节点。在节点B，剩下的容量r 为1 0，而收益c p 为4 0。从B点，能移动到D或E。移到D是不可行的，因为移到D所需的容量w2 为1 5。到E的移动是可行的，因为在这个移动中没有占用任何容量。E变成新的E-节点。这时活节点为A , B , E。在节点E，r= 1 0，c p= 4 0。从E，有两种可能移动（到J 和K），到J 的移动是不可行的，而到K的移动是可行的。节点K变成了新的E-节点。因为K是一个叶子，所以得到一个可行的解。这个解的收益为c p= 4 0。x 的值由从根到K的路径来决定。这个路径（ A , B , E , K）也是此时的活节点序列。既然不能进一步扩充K，K节点死亡，回溯到E，而E也不能进一步扩充，它也死亡了。接着，回溯到B，它也死亡了，A再次变为E -节点。它可被进一步扩充，到达节点C。此时r= 3 0，c p= 0。从C点能够移动到F或G。假定移动到F。F变为新的E-节点并且活节点为A, C,F。在F，r= 1 5，c p= 2 5。从F点，能移动到L或M。假定移动到L。此时r= 0，c p= 5 0。既然L是一个叶节点，它表示了一个比目前找到的最优解（即节点K）更好的可行解，我们把这个解作为最优解。节点L死亡，回溯到节点F。继续下去，搜索整棵树。在搜索期间发现的最优解即为最后的解。

例4-3 [旅行商问题] 在这个问题中，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。

图1 6 - 4给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一样。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；1 , 4 , 3 , 2 , 1为5 9。故1 , 3 , 2 , 4 , 1是该网络中最小耗费的旅行。

顾名思义，旅行商问题可被用来模拟现实生活中旅行商所要旅行的地区问题。顶点表示旅行

商所要旅行的城市（包括起点）。边的耗费给出了在两个城市旅行所需的时间（或花费）。旅行表示当旅行商游览了所有城市再回到出发点时所走的路线。

旅行商问题还可用来模拟其他问题。假定要在一个金属薄片或印刷电路板上钻许多孔。孔的位置已知。这些孔由一个机器钻头来钻，它从起始位置开始，移动到每一个钻孔位置钻孔，然后回到起始位置。总共花的时间是钻所有孔的时间与钻头移动的时间。钻所有孔所需的时间独立于钻孔顺序。然而，钻头移动时间是钻头移动距离的函数。因此，希望找到最短的移动路径。

另有一个例子，考察一个批量生产的环境，其中有一个特殊的机器可用来生产n 个不同的产品。利用一个生产循环不断地生产这些产品。在一个循环中，所有n 个产品被顺序生产出来，然后再开始下一个循环。在下一个循环中，又采用了同样的生产顺序。例如，如果这台机器被用来顺序为小汽车喷红、白、蓝漆，那么在为蓝色小汽车喷漆之后，我们又开始了新一轮循环，为红色小汽车喷漆，然后是白色小汽车、蓝色小汽车、红色小汽车，..，如此下去。一个循环的花费包括生产一个循环中的产品所需的花费以及循环中从一个产品转变到另一个产品的花费。虽然生产产品的花费独立于产品生产顺序，但循环中从生产一个产品转变到生产另一个产品的花费却与顺序有关。为了使耗费最小化，可以定义一个有向图，图中的顶点表示产品，边＜(i , j)＞上的耗费值为生产过程中从产品i 转变到产品j 所需的耗费。一个最小耗费的旅行定义了一个最小耗费的生产循环。

既然旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。

针对图1 6 - 4，任意选取点1作为起点和终点，则每一个旅行可用顶点序列1, v2 ,., vn , 1来描述，

v2 , ., vn 是(2, 3, ., n) 的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路

径定义了一个旅行。图1 6 - 5给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加1作为终点）。例如，到节点L的路径表示了旅行1 , 2 , 3 , 4 , 1，而到节点O的路径表示了旅行1 , 3 , 4 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为(n- 1 )！。

回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对图1 6 - 4的网络，利用图1 6 - 5的解空间树，一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活节点F。由于F没有未被检查的孩子，所以它成为死节点，回溯到C点。C变为E-节点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。

当要求解的问题需要根据n 个元素的一个子集来优化某些函数时，解空间树被称作子集树（subset tree）。所以对有n 个对象的0 / 1背包问题来说，它的解空间树就是一个子集树。这样一棵树有2n 个叶节点，全部节点有2n+ 1－1个。因此，每一个对树中所有节点进行遍历的算法都必须耗时W ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时，解空间树被称作排列树（permutation tree）。这样的树有n! 个叶节点，所以每一个遍历树中所有节点的算法都必须耗时W (n! )。图1 6 - 5中的树是顶点{ 2 , 3 , 4 }的最佳排列的解空间树，顶点1是旅行的起点和终点。

通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死，用来杀死活节点的策略称为限界函数（ bounding function）。在例1 6 - 2中，可使用如下限界函数：杀死代表不可行解决方案的节点；对于旅行商问题，可使用如下限界函数：如果目前建立的部分旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在图1 6 - 4的例子中使用该限界函数，那么当到达节点I时，已经找到了具有耗费2 5的1 , 3 , 2 , 4 , 1的旅行。在节点I，部分旅行1 , 3 , 4的耗费为2 6，若旅行通过该节点，那么不能找到一个耗费小于2 5的旅行，故搜索以I为根节点的子树毫无意义。

小结

回溯方法的步骤如下：

1) 定义一个解空间，它包含问题的解。

2) 用适于搜索的方式组织该空间。

3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。

回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。

练习

1. 考察如下0 / 1背包问题：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。

1) 画出该0 / 1背包问题的解空间树。

2) 对该树运用回溯算法（利用给出的p s , w s , c值），依回溯算法遍历节点的顺序标记节点。确定回溯算法未遍历的节点。

2. 1) 当n= 5时，画出旅行商问题的解空间树。

2) 在该树上，运用回溯算法（使用图1 6 - 6的例子）。依回溯算法遍历节点的顺序标记节点。确定未被遍历的节点。

3. 每周六， Mary 和Joe 都在一起打乒乓球。她们每人都有一个装有1 2 0个球的篮子。

这样一直打下去，直到两个篮子为空。然后她们需要从球桌周围拾起2 4 0个球，放入各自

的篮子。Mary 只拾她这边的球，而Joe 拾剩下的球。描述如何用旅行商问题帮助Mary 和

Joe 决定她们拾球的顺序以便她们能走最少的路径。
4.2 应用

4.2.1 货箱装船

1. 问题

在1 . 3节中，考察了用最大数量的货箱装船的问题。现在对该问题做一些改动。在新问题中，有两艘船， n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量且

n ?i = 1wi≤c1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。

例4-4 当n= 3，c1 =c2 = 5 0，w=[10,40,40] 时，可将货箱1 , 2装到第一艘船上，货箱3装到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，则无法将货箱全部装船。当n ?i = 1wi＝c1+c2 时，两艘船的装载问题等价于子集之和（ s u m - o f - s u b s e t）问题，即有n 个数字，要求找到一个子集（如果存在的话）使它的和为c1。当c1=c2 且n ?i = 1wi＝2c1 时，两艘船的装载问题等价于分割问题（ partition problem），即有n个数字ai , ( 1≤i≤n)，要求找到一个子集（若存在的话），使得子集之和为( n ?i = 1ai)/ 2。分割问题和子集之和问题都是N P-复杂问题。而且即使问题被限制为整型数字，它们仍是N P-复杂问题。所以不能期望在多项式时间内解决两艘船的装载问题。当存在一种方法能够装载所有n 个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限； 2) 将剩余货箱装到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c1。这个选择可通过求解0 / 1背包问题来实现，即寻找m ax (n ?i = 1wi xi )，其中n ?i = 1wi xi≤c1，xi ?{ 0 , 1 }，1≤i≤n。当重量是整数时，可用1 5 . 2节的动态规划方法确定第一艘船的最佳装载。用元组方法所需时间为O ( m i n {c1 , 2 n }）。可以使用回溯方法设计一个复杂性为O ( 2n ) 的算法，在有些实例中，该方法比动态规划算法要好。

2. 第一种回溯算法

既然想要找到一个重量的子集，使子集之和尽量接近c1，那么可以使用一个子集空间，并将其组织成如图1 6 - 2那样的二叉树。可用深度优先的方法搜索该解空间以求得最优解。使用限界函数去阻止不可能获得解答的节点的扩张。如果Z是树的j+ 1层的一个节点，那么从根到O的路径定义了xi（1≤i≤j）的值。使用这些值，定义c w（当前重量）为n ?i = 1wi xi 。若c w>c1，则以O为根的子树不能产生一个可行的解答。可将这个测试作为限界函数。当且仅当一个节点的c w值大于c1 时，定义它是不可行的。

例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空间树为图1 6 - 2的树再加上一层节点。搜索从根A开始且c w= 0。若移动到左孩子B则c w= 8，c w≤c1 = 1 2。以B为根的子树包含一个可行的节点，故移动到节点B。从节点B不能移动到节点D，因为c w+w2 >c1。移动到节点E，这个移动未改变c w。下一步为节点J，c w= 1 0。J的左孩子的c w值为1 3，超出了c1，故搜索不能移动到J的左孩子。

可移动到J的右孩子，它是一个叶节点。至此，已找到了一个子集，它的c w= 1 0。xi 的值由从A到J的右孩子的路径获得，其值为[ 1 , 0 , 1 , 0 ]。

回溯算法接着回溯到J，然后是E。从E，再次沿着树向下移动到节点K，此时c w= 8。移动到它的左子树，有c w= 11。既然已到达了一个叶节点，就看是否c w的值大于当前的最优c w 值。结果确实大于最优值，所以这个叶节点表示了一个比[ 1 , 0 , 1 , 0 ]更好的解决方案。到该节点的路径决定了x 的值[ 1 , 0 , 0 , 1 ]。从该叶节点，回溯到节点K，现在移动到K的右孩子，一个具有c w= 8的叶节点。这个叶节点中没有比当前最优cw 值还好的cw 值，所以回溯到K , E , B直到A。从根节点开始，沿树继续向下移动。算法将移动到C并搜索它的子树。

当使用前述的限界函数时，便产生了程序1 6 - 1所示的回溯算法。函数M a x L o a d i n g返回≤c的最大子集之和，但它不能找到产生该和的子集。后面将改进代码以便找到这个子集。

M a x L o a d i n g调用了一个递归函数m a x L o a d i n g，它是类L o a d i n g的一个成员，定义L o a d i n g类是为了减少M a x L o a d i n g中的参数个数。maxLoading(1) 实际执行解空间的搜索。MaxLoading(i) 搜索以i层节点（该节点已被隐式确定）为根的子树。从根到该节点的路径定义的子解答有一个重量值c w，目前最优解答的重量为b e s t w，这些变量以及与类L o a d i n g的一个成员相关联的其他变量，均由M a x L o a d i n g初始化。

程序16-1 第一种回溯算法

template

class Loading {

friend MaxLoading(T [], T, int);

p r i v a t e :

void maxLoading(int i);

int n; // 货箱数目

T *w, // 货箱重量数组

c, // 第一艘船的容量

c w, // 当前装载的重量

bestw; // 目前最优装载的重量

} ;

template

void Loading::maxLoading(int i)

{// 从第i 层节点搜索

if (i > n) {// 位于叶节点

if (cw > bestw) bestw = cw;

r e t u r n ; }

// 检查子树

if (cw + w[i] <= c) {// 尝试x[i] = 1 cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} maxLoading(i+1);// 尝试x[i] = 0 } template

T MaxLoading(T w[], T c, int n)

{// 返回最优装载的重量

Loading X;

// 初始化X

X.w = w;

X.c = c;

X.n = n;

X.bestw = 0;

X.cw = 0;

// 计算最优装载的重量

X . m a x L o a d i n g ( 1 ) ;

return X.bestw;

}

如果i＞n，则到达了叶节点。被叶节点定义的解答有重量c w，它一定≤c，因为搜索不会移动到不可行的节点。若c w > b e s t w，则目前最优解答的值被更新。当i≤n 时，我们处在有两个孩子的节点Z上。左孩子表示x [ i ] = 1的情况，只有c w + w [ i ]≤c 时，才能移到这里。当移动到左孩子时， cw 被置为c w + w [ i ]，且到达一个i + 1层的节点。以该节点为根的子树被递归搜索。当搜索完成时，回到节点Z。为了得到Z的cw 值，需用当前的cw 值减去w [ i ]，Z的右子树还未搜索。既然这个子树表示x [ i ] = 0的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。

注意：解空间树未被m a x L o a d i n g显示构造。函数m a x L o a d i n g在它到达的每一个节点上花费( 1 )时间。到达的节点数量为O ( 2n )，所以复杂性为O ( 2n )。这个函数使用的递归栈空间为(n)。

3. 第二种回溯方法

通过不移动到不可能包含比当前最优解还要好的解的右子树，能提高函数m a x L o a d i n g的性能。令b e s t w为目前最优解的重量， Z为解空间树的第i 层的一个节点， c w的定义如前。以Z为根的子树中没有叶节点的重量会超过c w + r，其中r=n ?j = i + 1w[ j ] 为剩余货箱的重量。因此，当c w + r≤b e s t w时，没有必要去搜索Z的右子树。

例4-6 令n, w, c1 的值与例4 - 5中相同。用新的限界函数，搜索将像原来那样向前进行直至到达第一个叶节点J（它是J的右孩子）。bestw 被置为1 0。回溯到E，然后向下移动到K的左孩子，此时b e s t w被更新为11。我们没有移动到K的右孩子，因为在右孩子节点c w = 8，r = 0，c w + r≤b e s t w。回溯到节点A。同样，不必移动到右孩子C，因为在C点c w = 0，r = 11且c w + r≤b e s t w。加强了条件的限界函数避免了对A的右子树及K的右子树的搜索。

当使用加强了条件的限界函数时，可得到程序1 6 - 2的代码。这个代码将类型为T的私有变量r 加到了类L o a d i n g的定义中。新的代码不必检查是否一个到达的叶节点有比当前最优解还优的重量值。这样的检查是不必要的，因为加强的限界函数不允许移动到不能产生较好解的节点。因此，每到达一个新的叶节点就意味着找到了比当前最优解还优的解。虽然新代码的复杂性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些节点。
程序16-2 程序1 6 - 1的优化

template

void Loading::maxLoading(int i)

{// // 从第i 层节点搜索

if (i > n) {// 在叶节点上

bestw = cw;

r e t u r n ; }

// 检查子树

r -= w[i];

if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} if (cw + r > bestw) //尝试x[i] = 0

m a x L o a d i n g ( i + 1 ) ;

r += w[i];

}

template

T MaxLoading(T w[], T c, int n)

{// 返回最优装载的重量

Loading X;

// 初始化X

X.w = w;

X.c = c;

X.n = n;

X.bestw = 0;

X.cw = 0;

// r的初始值为所有重量之和

X.r = 0;

for (int i = 1; i <= n; i++) X.r += w[i]; // 计算最优装载的重量 X . m a x L o a d i n g ( 1 ) ; return X.bestw; } 4. 寻找最优子集为了确定具有最接近c 的重量的货箱子集，有必要增加一些代码来记录当前找到的最优子集。为了记录这个子集，将参数bestx 添加到Maxloading 中。bestx 是一个整数数组，其中元素可为0或1，当且仅当b e s t x [ i ] = 1时，货箱i 在最优子集中。新的代码见程序1 6 - 3。程序16-3 给出最优装载的代码 template

void Loading::maxLoading(int i)

{ / /从第i 层节点搜索

if (i > n) {// 在叶节点上

for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestw = cw; return;} // 检查子树 r -= w[i]; if (cw + w[i] <= c) {//尝试x[i] = 1 x[i] = 1; cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} if (cw + r > bestw) {//尝试x[i] = 0

x[i] = 0;

m a x L o a d i n g ( i + 1 ) ; }

r += w[i];

}

template

T MaxLoading(T w[], T c, int n, int bestx[])

{// 返回最优装载及其值

Loading X;

// 初始化X

X.x = new int [n+1];

X.w = w;

X.c = c;

X.n = n;

X.bestx = bestx;

X.bestw = 0;

X.cw = 0;
// r的初始值为所有重量之和

X.r = 0;

for (int i = 1; i <= n; i++) X.r += w[i]; X . m a x L o a d i n g ( 1 ) ; delete [] X.x; return X.bestw; } 这段代码在L o a d i n g中增加了两个私有数据成员： x 和b e s t x。这两个私有数据成员都是整型的一维数组。数组x 用来记录从搜索树的根到当前节点的路径（即它保留了路径上的xi 值），b e s t x记录当前最优解。无论何时到达了一个具有较优解的叶节点， bestx 被更新以表示从根到叶的路径。为1的xi 值确定了要被装载的货箱。数据x 的空间由MaxLoading 分配。因为bestx 可以被更新O ( 2n )次，故maxLoading 的复杂性为O (n2n )。使用下列方法之一，复杂性可降为O ( 2n )： 1) 首先运行程序1 6 - 2的代码，以决定最优装载重量，令其为W。然后运行程序1 6 - 3的一个修改版本。该版本以b e s t w = W开始运行，当c w + r≥b e s t w时搜索右子树，第一次到达一个叶节点时便终止（即i > n）。

2) 修改程序1 6 - 3的代码以不断保留从根到当前最优叶的路径。尤其当位于i 层节点时，则到最优叶的路径由x [ j ]（1≤j

T MaxLoading(T w[], T c, int n, int bestx[])

{// 返回最佳装载及其值

// 迭代回溯程序

// 初始化根节点

int i = 1; // 当前节点的层次

// x[1:i-1] 是到达当前节点的路径

int *x = new int [n+1];

T bestw = 0, // 迄今最优装载的重量

cw = 0, // 当前装载的重量

r = 0; // 剩余货箱重量的和

for (int j = 1; j <= n; j++) r += w[j]; // 在树中搜索 while (true) { // 下移，尽可能向左 while (i <= n && cw + w[i] <= c) { // 移向左孩子 r -= w[i]; cw += w[i]; x[i] = 1; i + + ; } if (i > n) {// 到达叶子

for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestw = cw;} else {// 移向右孩子 r -= w[i]; x[i] = 0; i + + ; } // 必要时返回 while (cw + r <= bestw) { // 本子树没有更好的叶子，返回 i - - ; while (i > 0 && !x[i]) {

// 从一个右孩子返回

r += w[i];

i - - ;

}

if (i == 0) {delete [] x;

return bestw;}

// 移向右子树

x[i] = 0;

cw -= w[i];

i + + ;

}

}

}

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 3 章动态规划【Part3】

3.2.4 最短路径

假设G为有向图，其中每条边都有一个长度（或耗费），图中每条有向路径的长度等于该路径中各边的长度之和。对于每对顶点(i, j)，在顶点i 与j 之间可能有多条路径，各路径的长度可能各不相同。我们定义从i 到j 的所有路径中，具有最小长度的路径为从i 到j 的最短路径。

例3-15 如图1 5 - 4所示。从顶点1到顶点3的路径有

1) 1,2,5,3

2) 1,4,3

3) 1,2,5,8,6,3

4) 1,4,6,3

由该图可知,各路径相应的长度为1 0、2 8、9、2 7，因而路径3) 是该图中顶点1到顶点3的最短路径。

在所有点对最短路径问题（ a l l - p a i r sshorest-paths problem）中，要寻找有向图G中每对顶点之间的最短路径。也就是说，对于每对顶点(i, j)，需要寻找从i到j 的最短路径及从j 到i 的最短路径。因此对于一个n 个顶点的图来说，需寻找p =n(n-1) 条最短路径。假定图G中不含有长度为负数的环路，只有在这种假设下才可保证G中每对顶点(i, j) 之间总有一条不含环路的最短路径。当有向图中存在长度小于0的环路时，可能得到长度为－∞的更短路径，因为包含该环路的最短路径往往可无限多次地加上此负长度的环路。

设图G中n 个顶点的编号为1到n。令c (i, j, k)表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点。因此，如果G中包含边，则c(i, j, 0) =边的长度；若i= j ，则c(i,j, 0)=0；如果G中不包含边，则c (i, j, 0)= +∞。c(i, j, n) 则是从i 到j 的最短路径的长度。

例3-16 考察图1 5 - 4。若k=0, 1, 2, 3，则c (1, 3, k)= ∞；c (1, 3, 4)= 2 8；若k = 5, 6, 7，则c (1, 3,k) = 1 0；若k=8, 9, 10，则c (1, 3, k) = 9。因此1到3的最短路径长度为9。对于任意k＞0，如何确定c (i, j, k) 呢？中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c(i, j, k- 1 )，否则长度为c(i, k, k- 1) +c (k, j, k- 1 )。c(i, j, k) 可取两者中的最小值。因此可得到如下递归式：

c( i, j, k)= m i n {c(i, j, k-1), c (i, k, k- 1) +c (k, j, k- 1 ) }，k＞0

以上的递归公式将一个k 级运算转化为多个k-1 级运算，而多个k-1 级运算应比一个k 级运算简单。如果用递归方法求解上式，则计算最终结果的复杂性将无法估量。令t (k) 为递归求解c (i, j, k) 的时间。根据递归式可以看出t(k) = 2t(k- 1 ) +c。利用替代方法可得t(n) = ( 2n )。因此得到所有c (i, j, n) 的时间为(n2 2n )。

当注意到某些c (i, j, k-1) 值可能被使用多次时，可以更高效地求解c (i, j, n)。利用避免重复计算c(i, j, k) 的方法，可将计算c 值的时间减少到(n3 )。这可通过递归方式（见程序1 5 - 7矩阵链问题）或迭代方式来实现。出迭代算法的伪代码如图1 5 - 5所示。

/ /寻找最短路径的长度

/ /初始化c（i，j，1）

for （int i=1； i < = n ; i + +） for (int j=1; j<=n; j+ + ) c ( i ,j, 0 ) = a ( i ,j); // a 是长度邻接矩阵 / /计算c ( i ,j, k ) ( 0 < k="1;k<="n;k++)" i="1;i<="n;i++)" j=" 1" t="">

void AdjacencyWDigraph::Allpairs(T **c, int **kay)

{ / /所有点对的最短路径

/ /对于所有i和j，计算c [ i ] [ j ]和k a y [ i ] [ j ]

/ /初始化c [ i ] [ j ] = c（i，j，0）

for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = a[i][j]; kay[i][j] = 0; } for (i = 1; i <= n; i++) c[i][i] = 0; // 计算c[i][j] = c(i,j,k) for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { T t1 = c[i][k]; T t2 = c[k][j]; T t3 = c[i][j]; if (t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1 + t2 < i ="="" t="">

void OutputPath(T **c, int **kay, T NoEdge, int i, int j)

{// 输出从i 到j的最短路径

if (c[i][j] == NoEdge) {

cout << "There is no path from " << i=" 1时，(" cu="" a="" x="" ci="" 20="" ns="" 6="" 8="" 3="" 7="" 9="" ze="" traceback="" 0="" n="" m="" n2="" 5="" 11="" void="" s="" i="2," z="" e="" 1="" for="" int="" j="">< j =" C[1];" i =" 2;" j =" 0;" j =" C[i];" j =" n;" m =" 0;" i =" n;"> 1; i--)

// i 号n e t在M N S中?

if (size[i][j] != size[i-1][j]){// 在M N S中

Net[m++] = i;

j = C[i] - 1;}

// 1号网组在M N S中?

if (j >= C[1])

Net[m++] = 1; // 在M N S中

}

3.2.6 元件折叠

在设计电路的过程中，工程师们会采取多种不同的设计风格。其中的两种为位－片设计（bit-slice design）和标准单元设计（standard-cell design）。在前一种方法中，电路首先被设计为一个元件栈（如图15-10a 所示）。每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。图15-10a 给出了一个四片的设计。线路是按片来连接各元件的，即连线可能连接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。当图1 5 -10a 的位－片设计作为某一大系统的一部分时，则在V L SI ( Very Large Scale Integrated) 芯片上为它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。现在的问题便是如何将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度（如，若高度限制为H时，必须折叠栈以尽量减小宽度W）。由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。在图15-10b 的例子中，一个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需的片数。在图15-10b 中，栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的最大值。在图15-10b 中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。

实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如，在图1 5 -10b 中C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为5 ?i =1hi +r6，栈2所需高度为8 ?i=6hi +r6+r9。

在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设此线性顺序中的元件为 C1，.，Cn，下一步元件被折叠成如图1 5 - 11所示的相同宽度的行。在此图中， 1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时所需的通道高度。在图1 5 - 11的例子中，布线通道1的高度为l4，通道2的高度为l6，通道3的高度为l11。位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。
1. 等宽位－片元件折叠

定义r1 = rn+1 =0。由元件Ci 至Cj 构成的栈的高度要求为j ?k= ilk+ ri+ rj + 1。设一个位－片设计中所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi

为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H时），取Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。

当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知时，可得到以下公式：

Wi =w+ Wk + 1 （1 5 - 9）

由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折叠点。令h s u m(i,k)=k ?j = ihj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。

根据上述分析，可得到以下动态规划递归式：

这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式（1 5 - 1 0），可通过递归计算Wn , Wn- 1., W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的时间为O (n2 )。通过保留式（1 5 - 1 0）每次所得的k 值，可回溯地计算出各个最优的折叠点，其时间耗费为O (n)。

现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ., Cn 折叠成一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任何折叠，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n

另外，当i=n 时，仅有一个元件，也不可能折叠，因此：Hn ,j=hn+rn , 1≤j≤s

在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为

h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件也需以最小高度进行折叠.

因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）的右侧取最小值的点，该点成为第一个折叠点。

可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，.，以此类推。对应每个j 的Hi, j 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过保存由（ 1 5 - 1 2）式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的折叠点。

2. 变宽位－片元件的折叠

首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。令Wi 如式（1 5 - 1 0）所示，按照与（1 5 - 1 0）式相同的推导过程，可得：

Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）

其中Wn+1=0且w m i n(i,k)= m ini≤j≤k{wj }。可用与（1 5 - 1 0）式一样的方法求解（1 5 - 1 3）式，所需时间为O(n2 )。

当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用（ 1 5 - 1 3）式来确定该折叠的宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。

3. 标准单元折叠

用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。

令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令w s u m(i, s)=s ?j = iwj。可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一个元件，不存在连线问题，因此Hn, n =h。对于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的高度为ls+ 1（定义ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）

当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的.

为了寻找最小高度折叠，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）来确定Hi, s （1≤i≤s≤n）。最小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 3 章动态规划【Part2】

3.2.3 矩阵乘法链

m×n矩阵A与n×p矩阵B相乘需耗费(m n p)的时间（见第2章练习1 6）。我们把m n p作为两个矩阵相乘所需时间的测量值。现假定要计算三个矩阵A、B和C的乘积，有两种方式计算此乘积。在第一种方式中，先用A乘以B得到矩阵D，然后D乘以C得到最终结果，这种乘法的顺序可写为(A*B) *C。第二种方式写为A* (B*C) ,道理同上。尽管这两种不同的计算顺序所得的结果相同，但时间消耗会有很大的差距。

例3-12 假定A为1 0 0×1矩阵，B为1×1 0 0矩阵，C为1 0 0×1矩阵，则A*B的时间耗费为10 0 0 0，得到的结果D为1 0 0×1 0 0矩阵，再与C相乘所需的时间耗费为1 000 000，因此计算(A*B) *C的总时间为1 010 000。B*C的时间耗费为10 000，得到的中间矩阵为1×1矩阵，再与A相乘的时间消耗为1 0 0，因而计算A*（B*C）的时间耗费竟只有10 100！而且，计算（ A*B）*C时，还需10 000个单元来存储A*B，而A*（B*C）计算过程中，只需用1个单元来存储B*C。

下面举一个得益于选择合适秩序计算A*B*C矩阵的实例：考虑两个3维图像的匹配。图像匹配问题的要求是，确定一个图像需旋转、平移和缩放多少次才能逼近另一个图像。实现匹配的方法之一便是执行约1 0 0次迭代计算，每次迭代需计算1 2×1个向量T：

T=?A(x, y, z) *B(x, y, z)*C(x, y, z )

其中A，B和C分别为1 2×3，3×3和3×1矩阵。(x , y, z) 为矩阵中向量的坐标。设t 表示计算A(x , y, z) *B(x , y, z) *C(x , y, z)的计算量。假定此图像含2 5 6×2 5 6×2 5 6个向量，在此条件中，这1 0 0个迭代所需的总计算量近似为1 0 0 * 2 5 63 * t≈1 . 7 * 1 09 t。若三个矩阵是按由左向右的顺序相乘的，则t = 1 2 * 3 * 3 + 1 2 * 3 *1= 1 4 4；但如果从右向左相乘， t = 3 * 3 * 1 + 1 2 * 3 * 1 = 4 5。由左至右计算约需2 . 4 * 1 011个操作，而由右至左计算大概只需7 . 5 * 1 01 0个操作。假如使用一个每秒可执行1亿次操作的计算机，由左至右需4 0分钟，而由右至左只需1 2 . 5分钟。

在计算矩阵运算 A*B*C时，仅有两种乘法顺序（由左至右或由右至左），所以可以很容易算出每种顺序所需要的操作数，并选择操作数比较少的那种乘法顺序。但对于更多矩阵相乘来说，情况要复杂得多。如计算矩阵乘积M1×M2×.×Mq，其中Mi 是一个ri×ri + 1 矩阵( 1≤i≤q)。不妨考虑q=4 的情况，此时矩阵运算A*B*C*D可按以下方式（顺序）计算：

A* ( (B*C) *D) A* (B* (C*D)) (A*B) * (C*D) (A* (B*C) ) *D

不难看出计算的方法数会随q 以指数级增加。因此，对于很大的q 来说，考虑每一种计算顺序并选择最优者已是不切实际的。

现在要介绍一种采用动态规划方法获得矩阵乘法次序的最优策略。这种方法可将算法的时间消耗降为(q3 )。用Mi j 表示链Mi×.×Mj （i≤j）的乘积。设c(i,j) 为用最优法计算Mi j 的消耗，k a y(i, j) 为用最优法计算Mi j 的最后一步Mi k×Mk+1, j 的消耗。因此Mij 的最优算法包括如何用最优算法计算Mik 和Mkj 以及计算Mik×Mkj 。根据最优原理，可得到如下的动态规划递归式：k a y(i,i+s)= 获得上述最小值的k. 以上求c 的递归式可用递归或迭代的方法来求解。c( 1，q) 为用最优法计算矩阵链的消耗，k a y( 1 ,q) 为最后一步的消耗。其余的乘积可由k a y值来确定。

1. 递归方法

与求解0 / 1背包及图像压缩问题一样，本递归方法也须避免重复计算c (i, j) 和k a y(i, j)，否则算法的复杂性将会非常高。

例3-13 设q= 5和r =（1 0 , 5 , 1 , 1 0 , 2 , 1 0），式中待求的c 中有四个c的s= 0或1，因此用动态规划方法可立即求得它们的值： c( 1 , 1 ) =c( 5 , 5 ) = 0 ;c(1,2)=50; c( 4 , 5 ) = 2 0 0。现计算C( 2，5 )：c( 2 , 5 ) = m i n {c( 2 , 2 ) +c(3,5)+50, c( 2 , 3 ) +c(4,5)+500, c( 2 , 4 ) +c( 5 , 5 ) + 1 0 0 } （1 5 - 5）其中c( 2 , 2 ) =c( 5 , 5 ) = 0；c( 2 , 3 ) = 5 0；c(4,5)=200 。再用递归式计算c( 3 , 5 )及c( 2 , 4 ) :c( 3 , 5 ) = m i n {c( 3 , 3 ) +c(4,5)+100, c( 3 , 4 ) +c( 5 , 5 ) + 2 0 } = m i n { 0 + 2 0 0 + 1 0 0 , 2 0 + 0 + 2 0 } = 4 0c( 2 , 4 ) = m i n {c( 2 , 2 ) +c( 3 , 4 ) + 1 0 ,c( 2 , 3 ) +c( 4 , 4 ) + 1 0 0 } = m i n { 0 + 2 0 + 1 0 , 5 0 + 1 0 + 2 0 } = 3 0由以上计算还可得k a y( 3 , 5 ) = 4，k ay( 2 , 4 ) = 2。现在,计算c(2,5) 所需的所有中间值都已求得，将它们代入式（1 5 - 5）得：

c(2,5)=min{0+40+50, 50+200+500, 30+0+100}=90且k a y( 2 , 5 ) = 2

再用式（1 5 - 4）计算c( 1 , 5 )，在此之前必须算出c( 3 , 5 )、c(1,3) 和c( 1 , 4 )。同上述过程，亦可计算出它们的值分别为4 0、1 5 0和9 0，相应的k a y 值分别为4、2和2。代入式（1 5 - 4）得：

c(1,5)=min{0+90+500, 50+40+100, 150+200+1000, 90+0+200}=190且k a y( 1 , 5 ) = 2

此最优乘法算法的消耗为1 9 0，由k a y(1,5) 值可推出该算法的最后一步， k a y(1,5) 等于2，因此最后一步为M1 2×M3 5，而M12 和M35 都是用最优法计算而来。由k a y( 1 , 2 ) = 1知M12 等于M11×M2 2，同理由k a y( 3 , 5) = 4得知M35 由M3 4×M55 算出。依此类推，M34 由M3 3×M44 得出。因而此最优乘法算法的步骤为：

M11×M2 2 = M1 2

M3 3×M4 4 = M3 4

M3 4×M5 5 = M3 5

M1 2×M3 5 = M1 5

计算c(i, j) 和k a y (i, j) 的递归代码见程序1 5 - 6。在函数C中，r 为全局一维数组变量， k a y是全局二维数组变量，函数C返回c(i j) 之值且置k a y [a] [b] =k ay (a , b) (对于任何a , b)，其中c(a , b)在计算c(i,j) 时皆已算出。函数Traceback 利用函数C中已算出的k a y值来推导出最优乘法算法的步骤。

设t (q)为函数C的复杂性，其中q=j-i+ 1（即Mij 是q个矩阵运算的结果）。当q为1或2时，t(q) =d，其中d 为一常数；而q> 2时，t (q)=2q-1?k = 1t (k ) +e q，其中e 是一个常量。因此当q＞2时，t(q)＞2t (q- 1 ) +e，所以t (q)= W ( 2q)。函数Traceback 的复杂性为(q)。

程序15-6 递归计算c (i, j) 和kay (i, j)

int C(int i, int j)

{ / /返回c(i,j) 且计算k(i,j) = kay[i][j]

if (i==j) return 0; //一个矩阵的情形

if (i == j-1) { //两个矩阵的情形

kay[i][i+1] = i;

return r[i]*r[i+1]*r[r+2];}

/ /多于两个矩阵的情形

/ /设u为k = i 时的最小值

int u = C(i,i) + C(i+1,j) + r[i]*r[i+1]*r[j+1];

kay[i][j] = i;

/ /计算其余的最小值并更新u

for (int k = i+1; k < t =" C(i,k)" u =" t;" i ="="">） return c[i][j];

/ /若未计算,则进行计算

if(i==j) return 0; //一个矩阵的情形

i f ( i = = j - 1 ) { / /两个矩阵的情形

kay[i][i+1]=i;

c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;

return c[i][j];}

/ /多于两个矩阵的情形

/ /设u为k = i 时的最小值

int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];

k a y [ i ] [ j ] = i ;

/ /计算其余的最小值并更新u

for (int k==i+1; k

int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];

if (t

u = t ;

k a y [ i ] [ j ] = k ; }

}

c [ i ] [ j ] = u ;

return u;

}

为分析改进后函数C 的复杂性，再次使用分期计算方法。注意到调用C(1, q) 时每个c (i, j)（1≤i≤j≤q）仅被计算一次。要计算尚未计算过的c(a,b)，需附加的工作量s =j-i＞1。将s 计入第一次计算c (a, b) 时的工作量中。在依次计算c(a, b) 时，这个s 会转计到每个c (a, b) 的第一次计算时间c 中，因此每个c (i, i) 均被计入s。对于每个s，有q-s+ 1个c(i, j) 需要计算，因此总的工作消耗为q-1 ?s=1(q-s+ 1) = (q3 )。

3. 迭代方法

c 的动态规划递归式可用迭代的方法来求解。若按s = 2，3，.，q-1 的顺序计算c (i, i+s)，每个c 和kay 仅需计算一次。

例3-14 考察例3 - 1 3中五个矩阵的情况。先初始化c (i, i) (0≤i≤5) 为0，然后对于i=1, ., 4分别计算c (i, i+ 1 )。c (1, 2)= r1 r2 r3 = 5 0，c (2, 3)= 5 0，c ( 3,4)=20 和c (4, 5) = 2 0 0。相应的k ay 值分别为1，2，3和4。

当s= 2时，可得：

c( 1 , 3 ) = m i n {c( 1 , 1 ) +c(2,3)+ r1 r2 r4 , c( 1 , 2 ) +c( 3 ,3 )+r1r3r4 }=min{0+50+500,50+0+100}

=150

且k a y( 1 , 3 ) = 2。用相同方法可求得c( 2 , 4 )和c( 3 , 5 )分别为3 0和4 0，相应k a y值分别为2和3。

当s= 3时，需计算c(1,4) 和c( 2 , 5 )。计算c(2,5) 所需要的所有中间值均已知(见( 1 5 - 5 )式)，代入计算公式后可得c( 2 , 5 ) = 9 0，k a y( 2 , 5 ) = 2。c( 1 , 4 )可用同样的公式计算。最后，当s= 4时，可直接用（1 5 - 4）式来计算c( 1 , 5 )，因为该式右边所有项都已知。

计算c 和kay 的迭代程序见函数M a t r i x C h a i n（见程序1 5 - 8），该函数的复杂性为(q3 )。计算出kay 后同样可用程序1 5 - 6中的Traceback 函数推算出相应的最优乘法计算过程。

程序15-8 c 和kay 的迭代计算

void MatrixChain(int r[], int q, int **c, int **kay)

{// 为所有的Mij 计算耗费和k a y

// 初始化c[i][i], c[i][i+1]和k a y [ i ] [ i + 1 ]

for (int i = 1; i < q; i++) {

c[i][i] = 0;

c[i][i+1] = r[i]*r[i+1]*r[i+2];

kay[i][i+1] = i;

}

c[q][q] = 0;

/ /计算余下的c和k a y

for (int s = 2; s < q; s++)

for (int i = 1; i <= q - s; i++) {

// k = i时的最小项

c[i][i+s] = c[i][i] + c[i+1][i+s] + r[i]*r[i+1]*r[i+s+1];

kay[i][i+s] = i;

// 余下的最小项

for (int k = i+1; k < i + s; k++) {

int t = c[i][k] + c[k+1][i+s] + r[i]*r[k+1]*r[i+s+1];

if (t < c[i][i+s]) {// 更小的最小项

c[i][i+s] = t;

kay[i][i+s] = k;}

}

}

}

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 3 章动态规划【Part1】

第 3 章动态规划

动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。

3.1 算法思想

和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径，即选择此路径所经过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所要求解的问题变成：选择一条从3到5的最短路径。如果3到5的路径不是最短的，则从1开始经过3和5的路径也不会是最短的。例如，若选择的子路径（非最短路径）是3，2，5 (耗费为9 )，则1到5的路径为1，3，2，5 (耗费为11 )，这比选择最短子路径3，4，5而得到的1到5的路径1，3，4，5 (耗费为9) 耗费更大。

所以在最短路径问题中，假如在的第一次决策时到达了某个节点v，那么不管v 是怎样确定的，此后选择从v 到d 的路径时，都必须采用最优策略。

例3-2 [0/1背包问题] 考察1 3 . 4节的0 / 1背包问题。如前所述，在该问题中需要决定x1 .. xn的值。假设按i = 1，2，.，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。

在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一个更好的方案。

假设n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。

例3-3 [航费] 某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$ 1 0 0；从芝加哥到纽约票价$ 2 0；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$ 2 0。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$ 1 0 0。而使用直飞方式时，从洛杉矶到纽约的花费为$ 2 0 0。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$ 1 4 0（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：亚特兰大-芝加哥-纽约）。

如果用三维数组（t a g，起点，终点）表示问题状态，其中t a g为0表示转飞， t a g为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（ 0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。

当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（ d y n a m i c -programming recurrence equation），它可以帮助我们高效地解决问题。

例3-4 [0/1背包] 在例3 - 2的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y，剩余物品为i，i + 1，.，n 时的最优解的值，即：和利用最优序列由最优子序列构成的结论，可得到f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用（ 1 5 - 2）式通过递归或迭代来求解f ( 1 ,c)。从f (n, * )开始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式递归计算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。

对于例1 5 - 2，若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用递归式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最优解f ( 1 , 11 6 ) = m a x {f（2，11 6），f（2，11 6 - w1）+ p1} = m a x {f（2，11 6），f（2，1 6）+ 2 0 } = m a x { 3 3，3 8 } = 3 8。

现在计算xi 值，步骤如下：若f ( 1 ,c) =f ( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用f (2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1.n) 值。

在该例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2 及x3，此时r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此时r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

动态规划方法采用最优原则（ principle of optimality）来建立用于计算最优解的递归式。所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（t r a c e b a c k）以构造最优解。

编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。

3.2 应用

3.2.1 0/1背包问题

1. 递归策略

在例3 - 4中已建立了背包问题的动态规划递归方程，求解递归式（ 1 5 - 2）的一个很自然的方法便是使用程序1 5 - 1中的递归算法。该模块假设p、w 和n 为输入，且p 为整型，F(1,c) 返回f ( 1 ,c) 值。

程序15-1 背包问题的递归函数

int F(int i, int y)

{// 返回f ( i , y ) .

if (i == n) return (y < n=" 5，p="" w="[2,2,6,5,4]" c=" 1" i="j，因此根节点表示F" t="">

void Knapsack(T p[], int w[], int c, int n, T** f)

{// 对于所有i和y计算f [ i ] [ y ]

// 初始化f [ n ] [ ]

for (int y = 0; y <= yMax; y++) f[n][y] = 0; for (int y = w[n]; y <= c; y++) f[n][y] = p[n]; // 计算剩下的f for (int i = n - 1; i > 1; i--) {

for (int y = 0; y <= yMax; y++) f[i][y] = f[i+1][y]; for (int y = w[i]; y <= c; y++) f[i][y] = max(f[i+1][y], f[i+1][y-w[i]] + p[i]); } f[1][c] = f[2][c]; if (c >= w[1])

f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);

}

template

void Traceback(T **f, int w[], int c, int n, int x[])

{// 计算x

for (int i = 1; i < i=" 5时，f" x1 =" 1；由f" p2 ="f" x2 =" 1；由f" x3="x4" x5=" 1。" xi =" 1时的数对集，而P(i+" xi =" 0的数对集。接下来，合并Q和P(i+" q=" [" q="[(6,5)," q=" [" i="2|P(i" 6 =" 1" i =" 1li" s0 =" 0。考虑第i" j ="a" si =" si-r" s1 ="s0" 11 =" 1" y1 =" 1s2" s2 =" m" 11 =" m" 11 =" 2" y2 =" 2" s5 =" [" y5 =" [" s5 =" 8" y5 =" 4，所以s5" k="4" i ="="" k =" 1时," lsum =" l[i],bmax" s =" S(i-1)" k =" 2;" bmax =" b[i-k+1];" t =" S(i-k);"> t + lsum * bmax) {

s = t + lsum * bmax;

kay[i] = k;}

}

return s + header;

}

void Traceback(int kay[], int n)

{// 合并段

if (n == 0) return;

Tr a c e b a c k ( k a y, n-kay[n]);

cout << "New segment begins at " << (n - kay[n] + 1) << i ="=""> 0) return s[i]; //已计算完

/ /计算s [ i ]

/ /首先根据公式（1 5 - 3）计算k = 1时最小值

int lsum = l[i], bmax = b[i];

s[i] =S(i-1) + lsum * bmax;

kay[i] = 1;

/ /对其余的k计算最小值并更新

for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) { lsum += l[i-k+1]; if (bmax < bmax =" b[i-k+1];" t =" S(i-k);"> t + lsum * bmax) {

s[i] = t + lsum * bmax;

kay[i] = k;}

}

s[i] += header;

return s[i];

}

为了确定程序1 5 - 4的时间复杂性，我们将使用分期计算模式（ amortization scheme）。在该模式中，总时间被分解为若干个不同项，通过计算各项的时间然后求和来获得总时间。当计算si 时，若sj 还未算出，则把调用S(j) 的消耗计入sj ；若sj 已算出，则把S(j) 的消耗计入si (这里sj依次把计算新sq 的消耗转移至每个sq )。程序1 5 - 4的其他消耗也被计入si。因为L是2 5 6之内的常数且每个li 至少为1，所以程序1 5 - 4的其他消耗为( 1 )，即计入每个si 的量是一个常数，且si 数目为n，因而总工作量为(n)。

3. 迭代方法

倘若用式（1 5 - 3）依序计算s1 , ., sn，便可得到一个复杂性为(n)的迭代方法。在该方法中，在si 计算之前， sj 必须已计算好。该方法的代码见程序1 5 - 5，其中仍利用函数Tr a c e b a c k（见程序1 5 - 3）来获得最优合并。

程序15-5 迭代计算s和k a y

void Vbits (int l[], int b[], int n, int s[], int kay[])

{ / /计算s [ i ]和k a y [ i ]

int L = 256, header = 11 ;

s[0] = 0;

/ /根据式（1 5 - 3）计算s [ i ]

for (int i = 1; i <= n; i++) { // k = 1时,计算最小值 int lsum = l{i}, bmax = b[i]; s[i] = s[i-1] + lsum * bmax; kay[i] = 1; / /对其余的k计算最小值并更新 for (int k=2; k<= i && lsum+l[i-k+1]<= L; k++) { lsum += l[i-k+1]; if (bmax < bmax =" b[i-k+1];"> s[i-k] + lsum * bmax){

s[i] = s[i-k] + lsum * bmax;

kay[i] = k; }

}

s[i] += header;

}

}

常用算法---第 1 章贪婪算法【Part1】

常用算法---第 1 章贪婪算法【Part2】

常用算法---第 1 章贪婪算法【Part3】

常用算法---第 2 章分而治之算法【Part1】

常用算法---第 2 章分而治之算法【Part2】

常用算法---第 2 章分而治之算法【Part3】

常用算法---第 2 章分而治之算法【Part4】

常用算法---第 3 章动态规划【Part1】

常用算法---第 3 章动态规划【Part2】

常用算法---第 3 章动态规划【Part3】

常用算法---第 4 章回溯【Part1】

常用算法---第 4 章回溯【Part2】

常用算法---第 4 章回溯【Part3】

常用算法---第 5 章分枝定界【Part1】

常用算法---第 5 章分枝定界【Part2】

常用算法---第 5 章分枝定界【Part3】

常用算法---第 2 章分而治之算法【Part4】

2.2.5 距离最近的点对

给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。

例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。

通过检查所有的n(n- 1 ) / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解，而对于大的问题则首先把它划分为两个较小的问题，其中一个问题（称为A）的大小为「n /2ù，另一个问题（称为B）的大小为「n /2ù。初始时，最近的点对可能属于如下三种情形之一： 1) 两点都在A中（即最近的点对落在A中）；2) 两点都在B中；3) 一点在A，一点在B。假定根据这三种情况来确定最近点对，则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解，而在第二种情况下可对B进行递归求解。

if (n较小) {用直接法寻找最近点对

R e t u r n ; }

// n较大

将点集分成大致相等的两个部分A和B

确定A和B中的最近点对

确定一点在A中、另一点在B中的最近点对

从上面得到的三对点中，找出距离最小的一对点

图14-13 寻找最近的点对

为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。

例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1，垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A，右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上，可将其中两个加入A, 另一个加入B，以便A、B中包含相同的点数。假设d ,m加入A，g加入B。

设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于，这样，就可以淘汰那些距垂线距离≥ 的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线，宽为2 。边界线及其以外的点均被淘汰掉，只有阴影中的点被保留下来，以便确定是否存在第三类点对（对应于第三种情况）其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q)，p?A, q?B且p, q 的距离小于，则p?RA，q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点，p的y 坐标为p.y，那么只需检查RB 中满足p.y- ＜q.y＜p.y+ 的q 点，看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此，只需将RB 中位于×2 阴影内的点逐个与p 配对，以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p 的比较区（comparing region）。

例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h)，其距离约为0 . 3 1 6。B中最近点对为(f, j)，其距离为0 . 3，因此= 0 . 3。当考察是否存在第三类点时，除d, g, i, l, m 以外的点均被淘汰，因为它们距分割线x= 1的距离≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比较区中没有点，只需考察i即可。i 的比较区中仅含点l。计算i 和l的距离，发现它小于，因此(i, l) 是最近的点对。

为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。

1. 选择数据结构

为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。

每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。

程序14-8 点类

class Point1 {

friend float dist(const Point1&, const Point1&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&,float&);

friend void main();

p u b l i c :

int operator<=(Point1 a) const {return (x <= a.x);} p r i v a t e : int ID; // 点的编号 float x, y; // 点坐标 } ; class Point2 { friend float dist(const Point2&, const Point2&); friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&); friend bool closest(Point1 *, int, Point1&, Point1&, float&); friend void main(); p u b l i c : int operator<=(Point2 a) const {return (y <= a.y);} p r i v a t e : int p; // 数组X中相同点的索引 float x, y; // 点坐标 } ; 所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序，在分割过程中如果当前考察的点是X [l :r]，那么首先计算m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计算出A和B中的最近点对之后，还需要计算RA 和RB，然后确定是否存在更近的点对，其中一点属于RA，另一点属于RB。如果点已按y 坐标排序，那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操作符＜＝。成员p 用于指向X中的对应点。确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数d i s t (见程序1 4 - 9 )来计算点a, b 之间的距离。T可能是P o i n t 1或P o i n t 2，因此d i s t必须是P o i n t 1和P o i n t 2类的友元。程序14-9 计算两点距离 template

inline float dist(const T& u, const T& v)

{ / /计算点u 和v之间的距离

float dx = u.x-v. x ;

float dy = u.y-v. y ;

return sqrt(dx * dx + dy * dy);

}

如果点的数目少于两个，则函数c l o s e s t (见程序1 4 - 1 0 )返回f a l s e，如果成功时函数返回t r u e。当函数成功时，在参数a 和b 中返回距离最近的两个点，在参数d 中返回距离。代码首先验证至少存在两点，然后使用M e rg e S o r t函数(见程序14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标进行排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p给出了点i 在X中的位置。上述准备工作做完以后，调用函数close (见程序1 4 - 11 )，该函数实际求解最近点对。

程序14-10 预处理及调用c l o s e

bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)

{// 在n >= 2 个点中寻找最近点对

// 如果少于2个点，则返回f a l s e

// 否则，在a 和b中返回距离最近的两个点

if (n < y =" new" i =" 0;" p =" i;" x =" X[i].x;" y =" X[i].y;" z =" new" l ="=" a =" X[l];" b =" X[r];" d =" dist(X[l]," l ="=" d1 =" dist(X[l]," d2 =" dist(X[l+1]," d3 =" dist(X[l]," a =" X[l];" b =" X[l+1];" d =" d1;" a =" X[l+1];" b =" X[r];" d =" d2;}" a =" X[l];" b =" X[r];" d =" d3;}" m =" (l+r)/2;" f =" l," g =" m+1;" i =" l;"> m) Z[g++] = Y[i];

else Z[f++] = Y[i];

// 对以上两个部分进行求解

c l o s e ( X , Z , Y, l , m , a , b , d ) ;

float dr;

Point1 ar, br;

c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;

// (a,b) 是两者中较近的点对

if (dr < d) {a = ar; b = br; d = dr;} M e r g e ( Z , Y,l,m,r);// 重构Y / /距离小于d的点放入Z int k = l; // Z的游标 for (i = l; i <= r; i++) if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i]; // 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对 for (i = l; i < k; i++){ for (int j = i+1; j < k && Z[j].y - Z[i].y < d; j + + ) { float dp = dist(Z[i], Z[j]); if (dp < d) {// 较近的点对 d = dp; a = X[Z[i].p]; b = X[Z[j].p];} } } } 函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以创建分别与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的角色互相交换，依次执行两个递归调用来获取A和B中的最近点对。在两次递归调用返回后，必须保证Z不发生改变，但对Y则无此要求。不过，仅Y [ l : r ]可能会发生改变。通过合并操作（见程序1 4 - 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。为实现图1 4 - 1 6的策略，首先扫描Y [ 1 : r ]，并收集距分割线小于的点，将这些点存放在Z [ 1 : k - 1 ]中。可按如下两种方式来把RA中点p 与p 的比较区内的所有点进行配对：1) 与RB 中y 坐标≥p.y 的点配对；2) 与y 坐标≤p.y 的点配对。这可以通过将每个点Z [ i ]（1≤i < k，不管该点是在RA 还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。 2. 复杂性分析令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?). 这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。