算法设计第六章答案.pdf

算法实现题5-9：拉丁矩阵问题 问题描述：现有n 种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列 成m 行n 列的一个矩阵，m=n ，使矩阵中每一行和每一列的宝石都没有相同形 状。试设计一个算法，计算出对于给定的m 和n ，有多少中不同的宝石排列方案。 即，给定一个m*n 大小的矩阵，每一行n 个元素是1~n 的一种排列， 拉丁矩阵要求每一列上的m 个元素不能够有重复。 解空间：对于每一行而言，是一个深度为n 的排列树；因而，整个空间是m 个 深度为n 的排列树。 剪枝函数：每一列上的m 个元素存在重复。 因而，这个问题存在两个有关深度的变量r （行）和c （列），即Backtrace(r,c) void Backtrace(int r,int c) { for(int i=c;i=n;i++) if(ok(r,c,board[r][i])) { Swap(board[r][c],board[r][i]); if(c==n) { if(r==m) count+= 1.0; else Backtrace(r+ 1,2); } else Backtrace(r,c+ 1) ； Swap(board[r][c],board[r][i]); } } 其中，第一个for 循环：同一深度上的各子结点扩展；ok 函数是剪枝函数； 如果不考虑“行r ”，并且去掉红色方框中的代码，则整个回溯函数跟排列树形式 的代码框架一样；其中，红色部分主要是针对“行r ”进行递归（深度加1）。 习题6.1：01 背包问题的栈式分支限界法 栈式分支限界法将活结点表以后进先出（LIFO ）的方式存储于一个栈中。试 设计一个解01 背包问题的栈式分支限界法，并说明栈式分支限界法与回溯法的 区别。 解空间：子集树 A 1 0 B C 1 0 1 0 D E F G 1）队列式分支界限法和栈式分支界限法对比： 队列式分支限界法活结点列表变化过程：（先进先出） 1{A} 2 {B,C} 3 {C,D,E} 4 {D,E,F,G} 5 {E,F,G} 6 {F,G} 7 {G} 8{} 栈式分支限界法活结点列表变化过程：（后进先出） 1{A} 2 {B,C} 3 {B,F,G} 4 {B,F} 5 {B} 6 {D,E} 7 {D} 8{} 从各结点的扩展次序来讲，队列式分支限界法是标准的宽度优先，栈式分支限界 则类似于深度优先。 回溯法： 各结点的遍历次序是： A-B-D-B-E-A-C-F-C-G 回溯法是深度优先，而且结点A,B,C 都两次成为扩展结点； 但是，栈式分支限界法各结点只有一次机会成为扩展结点。 2 ）程序流程 整个流程与队列式分支限界法的01 背包问题一样，只是插入活结点的操作：由 insert()改为push() ，重新选择下一个扩展结点的操作：由delete()改为pop() 。 算法主函数是： 一个while(1)循环，循环结束条件是活结点列表为空，即当前扩展结点为空，表 示所有可行的结点都已经得到遍历；并且输出最优解。 每一次循环作用是：在当前的扩展结点下，将以当前扩展结点作为父结点的下一 层子结点都加入到活结点列表里，并且选择一个新的扩展结点，进入下一层循环； 其中，剪枝函数包括左结点的容量约束（约束函数）和右结点的最大价值判断（界 限函数）； 开始 根结点加入活结点列表， 并作为当前扩展结点 活结点列表 是 为空？ 否