转自天涯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月10日星期四
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 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
// 初始化第一个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);
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
{// 返回背包最优装载的收益
// bestx[i] = 1 当且仅当物品i 属于最优装载
// 使用最大收益分枝定界算法
// 定义一个最多可容纳1 0 0 0个活节点的最大堆
H = new MaxHeap
// 为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
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
// 初始化层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
{// 旅行商问题的最小耗费分枝定界算法
// 定义一个最多可容纳1 0 0 0个活节点的最小堆
MinHeap
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 ]上的顶点时，它的子节点可行。对于每个可行的孩子节点，将边
如果有向图没有旅行路径，程序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 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
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.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 . 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
QNode
{// 如果不是叶节点，则向队列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 = 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 . 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
* 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中增添一个层为l e v上限重量为w t的活节点
// 新节点是E的一个孩子
// 当且仅当新节点是左孩子ch 为t r u e
bbnode *b = new bbnode;
b->parent = E;
b->LChild = ch;
HeapNode
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
// 第一剩余重量的数组
// 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
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】
订阅：
博文 (Atom)
