个人精品文档资料
{选择最小权值边（i，j）； //贪心选择 if(i∈T1&&j ∈T2)
//边(i,j)一端i在T1分支,一端j在T２分支 { union(i,j); T=T∪{（i，j)} } else T=T∪{（i，j)}; } }
选边过程：
第５章 回溯算法
1、回溯法基本思想？回溯法解题步骤？
答：基本思想：在搜索尝试中找问题的解，当不满足条件就”回溯”返回，尝试别的路径。 解题步骤：(1)针对所给问题，定义问题的解空间；
(2)并确定易于搜索的解空间结构(排列树，子集树);
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数，剪去无效的枝，避免无效搜索。
2、什么叫子集树？什么叫排列树？ 什么叫满m叉树？
答：1）子集树 ：当所给问题是在n个元素的集合S中找出S满足某种性质的子集时，其相应的解空间树称作子集树。
2）排列树 ： 当所给问题是在确定的n个元素满足某种性质的排列中搜索问题的解时，相应的解空间树被称作排列树。
3）满m叉树： 当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。 这类问题的解空间树称为满m叉树。
3、利用回溯法，求解0－1背包问题，要求设计出相应算法？并分析其时间复杂度？ 答：算法描述（递归实现）
double knaspack(double p[ ], double w[ ], double c)
//c是背包载重
欢迎大家下载学习
16
个人精品文档资料
{double cw=0; //当前重量 double cp=0; //当前价值
double bestp=0; //当前最优装载价值 backtrack(1); //深度优先搜索解空间 return bestp; }
double backtrack( int i) //搜索解空间函数 {double n=p.length;
if ( i>n ) // i表示深度（层），i>n搜索到叶子节点 { bestp=cp; return bestp; }
//否则，进入左子树向下深度搜索
else if (cw+w[ i]<=c) //当前物品放入背包不超载 { cw=cw+w[ i]; cp=cp+p[ i]; c=c-w[i]; backtrack(i+1); } //继续向下深度搜索
else //超载，则回溯进入右子树 if ( bound(i+1)>bestp )
//通过限界函数知道右子树可能包含最优解 //即，当前价值＋剩余物品价值大于bestp，进入右子树 backtrack( i+1 ); }
double bound(int i) // 限界函数计算当前价值与剩余价值和 { double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值
while (i <= n && w[ i] <= cleft) // 装载剩下的物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; }
// w[ i]> cleft 跳出循环，背包装满,物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 }
算法分析：
n
该算法计算上界函数bound时间复杂度为O(n); 在最坏的情况下，有2个右孩子节点
n
需要计算上界； 故该算法的时间复杂度为O(n*2)
4、利用回溯法，求解n后问题，要求设计出相应算法，并分析其时间复杂度？ 答：算法描述（递归实现） double nqueen(int nn) { int n=nn;
int sum=0; // 放置皇后的方案数
int x[ n]; // x[ i]表示皇后i放在棋盘的第i行，第x[ i]列
欢迎大家下载学习
17
个人精品文档资料
for (int i=0;i<=n; i++;) x[ i]=0; // 初始化
backtrack(1); // 深度优先搜索解空间 return sum; }
void backtrack ( int t)
{ if( t>n ) // 搜索到叶子节点，方案数＋1，t是层数 sum++; else
for( int i=1; i<=n; i++) // for循环一一判断皇后所在列 { x[ t]=i; // 将第t个皇后放在t行(t不同)，i列 if( place(t) ) // 约束函数，判断是否有冲突 backtrack (t+1); // 放下一个皇后 } }
void place( int k) // 约束函数
{ for( int j=1;j if( (math.abs(k-j)=math.abs(x[ k]-x[ j])) || (x[ k]=x[ j]) ) //k与之前的皇后1…k-1不能在同一斜线 或 同一列 return false; else return true; } 算法分析 ： 对于n皇后问题的解空间共有n!个叶子节点，故排列树最多有n* n!个节点； 最坏的情况下每个节点都要用place函数判断是否可行，每一个节点判断时间为O(n)； 故该算法的时间复杂度记为O(n* n* n!) 第六章 分支限界算法 1、分支限界算法的解题步骤？ 答：1）针对所给问题，定义问题的解空间; 2）确定易于搜索的解空间结构(排列树，子集树); 3）以广度优先方式搜索问题的解空间； 4)在搜索过程中用限界函数，剪去无效的枝，避免无效搜索。 2、常用的两种分支限界算法？并说明其思想？ 答：1）队列式（FIFO先进先出）分支限界算法 将活动结点表组织成一个队列，并按照队列先进先出原则取下一个结点作为扩展结点 基本思想： ①开始，根结点是唯一的活结点，根结点入队列； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子(分支)，用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点队列中。 欢迎大家下载学习 18 个人精品文档资料 ③再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 2）优先队列式分支限界算法 将活结点表组织成一个优先队列（堆），并按照优先队列中规定的结点优先级，选取优先级最高的结点作为当前扩展结点。 基本思想： ①根结点是唯一的活结点，根结点入堆； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子节点； 用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点表中（堆），并给每个结点设置优先级。 ③再从活结点表(堆)中取出堆顶结点(堆中优先级最高结点)为当前扩展结点，……，直到活结点表(堆)为空。 3、分支限界算法与回溯法异同？ 答：相同点：都属于搜索算法； 都需要在问题的解空间中搜索问题的解； 不同点： 1）求解目标不同： 回溯法求解目标是找出解空间树中满足约束条件所有解； 分支限界法求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同： 回溯法以深度优先的方式搜索解空间树； 分支限界法则以广度优先的方式搜索解空间树。 4、 利用优先队列分支限界算法，设计0－1背包问题算法？ 答：队列式分支限界算法（无限界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索 解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，右儿子结点总是可行的，无上界函数 enQueue(ew, i); // 右儿子加入队列 ew = ((Integer) queue.remove()).intValue();// 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空 欢迎大家下载学习 19 个人精品文档资料 else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } } } 队列式分支限界法（带上界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，计算上界函数，检查当前扩展结点的右儿子结点 up = Bound(i+1); if (up >= bestp) //右子树可能含最优解 enQueue(ew, i); //右儿子结点加入队列 ew = ((Integer) queue.remove()).intValue(); // 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空 else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++ // 进入下一层 } } } double bound(int i) // 计算上界函数 {// 计算当前价值与剩余价值和 double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值 while (i <= n && w[ i] <= cleft) // 剩余物品单位重量价值递减序装入物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]> cleft 跳出循环，物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 } n 时间复杂度分析：计算上界时间为O(n)；在最坏的情况下，有2个右孩子节点需要计算上 n 界； 故该算法的时间复杂度为O(n*2) 欢迎大家下载学习 20
算法设计与分析习题 - 图文
