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
{// 用回溯算法解决旅行商问题
// 返回最优旅游路径的耗费，最优路径存入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
{// 旅行商问题的回溯算法
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
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;">
没有评论:
发表评论