《算法设计与分析》第08章

1、l 规定每个规定每个xi取值的约束条件称为取值的约束条件称为（explicit constraint）。）。l 对给定的一个问题实例，显式约束规定了所有对给定的一个问题实例，显式约束规定了所有可能的元组，它们组成问题的候选解集，被称为可能的元组，它们组成问题的候选解集，被称为该问题实例的该问题实例的解空间解空间（solution space）。）。l （implicit constraint）给出了判定一）给出了判定一个候选解是否为可行解的条件。个候选解是否为可行解的条件。 ，也称代价函数（，也称代价函数（cost function），用来），用来衡量每个可行解的优劣。使目标函数取最大（或最衡

2、量每个可行解的优劣。使目标函数取最大（或最小）值的可行解为问题的最优解。小）值的可行解为问题的最优解。（state space）是描述问题解空间的树）是描述问题解空间的树形 结 构 。 树 中 每 个 结 点 称 为 一 个形 结 构 。 树 中 每 个 结 点 称 为 一 个（problem state）。如果从根到树中某个状态的路）。如果从根到树中某个状态的路径代表一个作为候选解的元组，则称该状态为径代表一个作为候选解的元组，则称该状态为（solution state）。如果从根到某个解状态的路）。如果从根到某个解状态的路径代表一个作为可行解的元组，则称该解状态为径代表一个作为可行解的元组

3、，则称该解状态为(answer state)。 l为了提高搜索效率，在搜索过程中使用为了提高搜索效率，在搜索过程中使用（constraint function），可以避免无谓地搜索那些），可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还已知不含答案状态的子树。如果是最优化问题，还可使用可使用（bound function）剪去那些不可）剪去那些不可能包含最优答案结点的子树。约束函数和限界函数能包含最优答案结点的子树。约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统减少问题求解

4、所需实际生成的状态结点数，它们统称为称为（pruning function）。）。l使用剪枝函数的深度优先生成状态空间树中结点使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为的求解方法称为（backtracking）；广度优）；广度优先生成结点，并使用剪枝函数的方法称为先生成结点，并使用剪枝函数的方法称为（branch-and-bound）。）。 lVoid RBacktrack(int k)l/应以应以Rbacktrack(0)调用本函数调用本函数l for (每个每个xk,使得使得 xk T(x0,xk-1)l &(Bk(x0,xk)l if ( (x0,x1,xk)是一个

5、可行解是一个可行解)l 输出输出 (x0,x1,xk); l RBacktrack(k+1); l llVoid IBacktrack(int n)ll int k=0;l while (k=0)l if (还剩下尚未检测的还剩下尚未检测的xk，使得，使得xkl T(x0,xk-1) & Bk(x0,xk)l if ( (x0,x1,xk)是一个可行解是一个可行解)l 输出输出(x0,x1,xk);l k+;l l else k-; l l l回溯算法的回溯算法的可达可达O(p(n)n!)（或（或O(p(n)2n)或或O(p(n)nn)），这里），这里p(n)是是n的多项的多项式，是生

6、成一个结点所需的时间。式，是生成一个结点所需的时间。（Monte Carlo）。这种估计方法的）。这种估计方法的基本思想是在状态空间树中随机选择一条路径基本思想是在状态空间树中随机选择一条路径(x0, x1, xn 1)。设。设X是这条随机路径上，代表部分向量是这条随机路径上，代表部分向量(x0, x1, xk 1)的结点，如果在的结点，如果在X处不受限制的孩子数处不受限制的孩子数目是目是mk，则认为与，则认为与X同层的其他结点不受限制的孩同层的其他结点不受限制的孩子数目也都是子数目也都是mk。l整个状态空间树上将实际生成的结点数估计为整个状态空间树上将实际生成的结点数估计为l m = 1+m

7、0+m0m1+m0m1m2+ lint Estimate(SType* x)ll int k=0,m=1,r=1;l do l SetType S= xk| xk T(x1,xk 1) l & Bk(x1,xk=true)；l if (!Size(S) return m;l r=r*Size(S);m=m+r;l xk=Choose(S);k+;l while(1);lln n- -皇后问题要求在一个皇后问题要求在一个n n n n的棋盘上放置的棋盘上放置n n个皇后，个皇后，使得它们彼此不受使得它们彼此不受“攻击攻击”。n n- -皇后问题要求寻找皇后问题要求寻找在棋盘上放置这在棋盘

8、上放置这n n个皇后的方案，使得它们中任何两个皇后的方案，使得它们中任何两个都不在同一行、同一列或同一斜线上。个都不在同一行、同一列或同一斜线上。 l皇后问题的状态空间树是一棵皇后问题的状态空间树是一棵排列树有排列树有n!个叶结点，遍历排列树的时间为个叶结点，遍历排列树的时间为 (n!)。 lbool Place(int k, int i,int* x)l/判定两个皇后是否在同一列或在同一斜线上判定两个皇后是否在同一列或在同一斜线上l for (int j=0;jk;j+)l if (xj=i) | (abs(xj-i)=abs(j-k)l return false;l return true

9、;l lvoid NQueens(int n,int *x)ll NQueens(0,n,x);l void NQueens(int k,int n,int *x) for (int i=0; in;i+) if (Place(k,i,x) xk=i; if (k=n-1) for(i=0;in;i+)coutxi ; coutendl; else NQueens(k+1,n,x); l可通过计算得到这可通过计算得到这5次试验中实际需要生成的结次试验中实际需要生成的结点数的平均值为点数的平均值为1625。8-皇后问题状态空间树的结皇后问题状态空间树的结点总数是：点总数是：l l因此，需要实际生

10、成的结点数目大约占总结点数因此，需要实际生成的结点数目大约占总结点数的的1.55%。 70jj0i109601)i8(1：可变长度元组和固定长度元组。：可变长度元组和固定长度元组。（x0,xk 1,xk），），0 kn。元组的。元组的每个分量的取值可以是元素值，也可以是选入子集每个分量的取值可以是元素值，也可以是选入子集的正数的下标。的正数的下标。（x0,x1,xn 1），），xi 0,1, 0 in。xi=0，表示，表示wi未选入子集，未选入子集，xi=1，表示，表示wi入选子集。入选子集。 l称这种从称这种从n个元素的集合中找出满足某些性质的个元素的集合中找出满足某些性质的子集的状态空间树

11、为子集的状态空间树为。子集树有。子集树有2n个解状态，个解状态，遍历子集树的时间为遍历子集树的时间为(2n)。lBk(x0,x1,xk) 为为true，当且仅当，当且仅当 1k0i1k0ikii1nkiiiiMwxw Mwxw且且 else if (s+wk+wk+1=m)&(s+wk+1=m) xk=0; SumOfSub(s,k+1,r-wk,x,m,w); void SumOfSub (int* x,int n,float m,float* w) float r=0; for(int i=0;i=m & w0=m) SumOfSub(0,0,r,x,m,w); l设有设有

12、n=6个正数的集合个正数的集合W=(5,10,12,13,15,18)和整和整数数M=30，求，求W的所有元素之和为的所有元素之和为M的子集。的子集。 0 E)ji,( 1 ji a 其它其它如果如果l约束函数：对所有约束函数：对所有i和和j，0 i,jk，i j，若，若aij=1，则则xi xj。 template void MGraph: mColoring(int k,int m,int *x) do NextValue(k,m,x); if (!xk) break; if (k = n-1) for (int i=0; in; i+) cout xi ; cout endl; else

13、 mColoring(k+1,m,x); while(1); template void MGraph: mColoring(int m,int *x) mColoring(0,m,x); l 算法的计算时间上界可由状态空间树的结点数算法的计算时间上界可由状态空间树的结点数确定。确定。l每个结点的处理时间即每个结点的处理时间即NextValue的执行时间，的执行时间，为为O(mn)。因此总时间为。因此总时间为 1n0iim)nm(O)1m/()mm(nnmn1nn1ii l已知图已知图G=(V,E)是一个是一个n个结点的连通图。连通图个结点的连通图。连通图G的一个的一个(Hamiltonlan

14、 cycle)是图是图G的一个的一个回路，它经过图中每个结点，且只经过一次。一个回路，它经过图中每个结点，且只经过一次。一个哈密顿环是从某个结点哈密顿环是从某个结点v0 V开始，沿着图开始，沿着图G的的n条条边环行的一条路径（边环行的一条路径（v0,v1,vn 1,vn），其中，），其中，(vi,vi+1) E,0 in，它访问图中每个结点且只访问一，它访问图中每个结点且只访问一次，最后返回开始结点，即除次，最后返回开始结点，即除v0=vn，路径上其余结，路径上其余结点各不相同。点各不相同。 ltemplate lvoid MGraph:NextValue(int k,int *x)ll do

15、 l xk=(xk+1)% n; l if (!xk) return;l if (axk-1xk) l for (int j=0;jk;j+) if (xj=xk) break; l if (j=k) l if (kn-1)|(k=n-1) & axn-1x0)l return; l l while(1);l template void ExtMGraph:Hamiltonian(int k,int *x) do NextValue(k,x); if (!xk) return; if (k=n-1) for (int i=0; in; i+) coutxi ; cout 0n; els

16、e Hamiltonian(k+1,x); while (1); template void ExtMGraph: Hamiltonian(int *x) Hamiltonian(1,x); 1n0ii)S(fn1)S(MFT(batch job schedule)(batch job schedule)问题要求确问题要求确定这定这n n个作业的最优作业调度方案使其个作业的最优作业调度方案使其MFTMFT最小。这最小。这等价于求使得所有作业的完成时间之和等价于求使得所有作业的完成时间之和l最小的调度方案。最小的调度方案。 1n0ii)S(f)S(FT l设有三个作业和两台设备，作业任务的处理时

17、间为设有三个作业和两台设备，作业任务的处理时间为（a0,a1,a2）=(2,3,2)和（和（b0,b1,b2）=(1,1,3)。这三个作。这三个作业有业有6种可能的调度方案：种可能的调度方案：(0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0),它们相应的完成时间之和分别是它们相应的完成时间之和分别是19,18,20,21,19,19。其中，最佳调度方案。其中，最佳调度方案S=(0,2,1)。在这一调度方案下，在这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。 1n0ii)S(f)S(FTl求解这一问题没有有效的约束函数，但可以使用最求解这一问题没有有效的约束函数，但可以使用最优解的上界值优解的上界值U U进行剪枝。如果对于已经调度的作业进行剪枝。如果对于已经调度的作业子集的某种排列，所需的完成时间和已经大于迄今为子集的某种排列，所需的完成时间和已经大于迄今为止所记录下的关于最优调度方案的完成时间和的上界止所记录下的关于最优调度方案的完成时间和的上界值值U,U,则该分枝可以剪去。则该分枝可以剪去。 int JobSch(int *x); private: void JobSch(int i,int *x); int *a,*b,n