分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法（divide-and-conquer）的基本思想：A分割成k个更小规模的子问题。B对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。
最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质
贪心算法: 贪心算法总是作出在当前看来最好的选择,它并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。
贪心算法：贪心算法求解的这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
单源最短路径基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。
回溯法的基本思想：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常见的两种分支限界法：（1）队列式(FIFO)分支限界法。按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
布线问题算法思想：解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。
随机存储机RAM它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM由只读输入带、只写输入带、程序存储部件、内存储器和指令计数器5个部分组成。P类和NP类语言的定义P={L|L是一个能在多项式时间内被一台DTM所接受的一眼} NP+{L|L是一个能在多项式时间内被一台NDTM所接受的语言} 由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故P属于NPP类问题：是确定性计算模型下的易解问题类。NP类问题：是非确定性计算模型下的易验证问题类。NP完全类问题：即多项式复杂度的非确定性问题类；简单的写法是NP=P？问题就在这个问号上，到底是NP等于P，还是NP不等于P。算法的渐进时间复杂性的含义？
答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
最坏情况下的时间复杂性和平均时间复杂性有什么不同？
答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn A(n) =∑P(I)T(n，I) I∈Dn
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
采用回溯法求解的问题，其解如何表示？有什么规定？
问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i 快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。 二、递归与分治： 二分搜索算法： public static int binarySearch(int a[], int x, int n) { left = 0; right = n - 1; while (left <= right) { int middle = (left + right)/2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; } return -1; } 棋盘覆盖 public void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, s = size/2; if (dr < tr + s && dc < tc + s) chessBoard(tr, tc, dr, dc, s); else { board[tr + s - 1][tc + s - 1] = t; chessBoard(tr, tc, tr+s-1, tc+s-1, s);} if (dr < tr + s && dc >= tc + s) chessBoard(tr, tc+s, dr, dc, s); else { board[tr + s - 1][tc + s] = t; chessBoard(tr, tc+s, tr+s-1, tc+s, s);} if (dr >= tr + s && dc < tc + s) chessBoard(tr+s, tc, dr, dc, s); else { board[tr + s][tc + s - 1] = t; chessBoard(tr+s, tc, tr+s, tc+s-1, s);} if (dr >= tr + s && dc >= tc + s) chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr + s][tc + s] = t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);} } 三、动态规划 最长公共子序列 void LCSLength(int m，int n，char []x，char []y，int[][]c，int [][]b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } 构造最长公共子序列 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout< else LCS(i，j-1，x，b); } 最优装载 void Loading(int x[], Type w[], Type c, int n) {int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} } 五、回溯法 装载问题 void backtrack (int i) { if (i > n) r -= w[i]; if (cw + w[i] <= c) ｛x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; backtrack(i + 1); } r += w[i]; } 批处理问题： void Flowshop::Backtrack(int i) {if (i > n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f;} else for (int j = i; j <= n; j++) { f1+=M[x[j]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; f+=f2[i]; if (f < bestf) { Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]);} f1- =M[x[j]][1]; f- =f2[i];}} 六、分支限界法 单源最短路径问题 while (true) { for (int j = 1; j <= n; j++) if ((c[E.i][j] dist[j]=E.length+c[E.i][j]; prev[j]=E.i; MinHeapNode N.i=j; N.length=dist[j]; H.Insert(N);} try {H.DeleteMin(E);} catch (OutOfBounds) {break; } } } 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 16．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 17．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 19.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 22、蒙特卡罗算法是（ B ）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 23.下列哪一种算法不是随机化算法（ C ） A. 蒙特卡罗算法B. 拉斯维加斯算法C.动态规划算法D.舍伍德算法 24. （ D ）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 25. 矩阵连乘问题的算法可由（ B）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 A、最小堆 B、最大堆 C、栈 D、数组 27、Strassen矩阵乘法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 29、使用分治法求解不需要满足的条件是（A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 30、下面问题（B ）不能使用贪心法解决。 A 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决0/1背包问题的是（A ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照（C ）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 33、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 34．实现合并排序利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 35．下列是动态规划算法基本要素的是（ D ）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 36．下列算法中通常以自底向下的方式求解最优解的是（ B ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 37．采用广度优先策略搜索的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 38、合并排序算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 39、在下列算法中得到的解未必正确的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 40、背包问题的贪心算法所需的计算时间为（ B ） A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 41．实现大整数的乘法是利用的算法（ C ）。 A、贪心法 B、动态规划法 C、分治策略 D、回溯法 42．0-1背包问题的回溯算法所需的计算时间为（ A ） A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 43．采用最大效益优先搜索方式的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 44．贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 45. 实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 46.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 47.背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 48、广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 49、舍伍德算法是（ B ）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 50、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 51下列哪一种算法是随机化算法（ D ） A. 贪心算法B. 回溯法C.动态规划算法D.舍伍德算法 52. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解 53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 54. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 55. 实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 二、 填空题 1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2、程序是 算法 用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。 4.矩阵连乘问题的算法可由 动态规划 设计实现。 5、拉斯维加斯算法找到的解一定是 正确解。 6、算法是指解决问题的 一种方法 或 一个过程 。 7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。 8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。 9、以深度优先方式系统搜索问题解的算法称为 回溯法 。 10、数值概率算法常用于 数值问题 的求解。 11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。 12、利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。 14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。 16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 17、矩阵连乘问题的算法可由 动态规划 设计实现。 18、拉斯维加斯算法找到的解一定是 正确解。 19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。 21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。 22.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。 23、大整数乘积算法是用 分治法 来设计的。 24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 25、舍伍德算法总能求得问题的 一个解 。 26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 27.快速排序算法是基于 分治策略 的一种排序算法。 28.动态规划算法的两个基本要素是. 最优子结构 性质和 重叠子问题 性质 。 30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 31.分支限界法主要有 队列式（FIFO） 分支限界法和 优先队列式 分支限界法。 32．分支限界法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 33．回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。 34.任何可用计算机求解的问题所需的时间都与其 规模 有关。 35.快速排序算法的性能取决于 划分的对称性 。 三、算法填空 1.背包问题的贪心算法 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c - =w[i]; } if (i<=n) x[i]=c/w[i]; } 2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) { int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for(int j=1； j<=n； j++) { if (b>0) b+= a[j] ； else b=a[i]; ； //一旦某个区段和为负，则从下一个位置累和 if(b>sum) sum=b; } return sum； } 3.贪心算法求装载问题 template void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; ; for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; ;} } 4.贪心算法求活动安排问题 template void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { A[i]=true; j=i; } else A[i]=false; } } 5.快速排序 template void QuickSort (Type a[], int p, int r) { if (p QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 } } 6.排列问题 Template void perm(Type list[], int k, int m ) { //产生[list[k:m]的所有排列 if(k==m) { //只剩下一个元素 for (int i=0;i<=m;i++) cout< else //还有多个元素待排列，递归产生排列 for (int i=k; i<=m; i++) { swap(list[k]，list[i]); perm(list,k+1;m); swap(list[k],list[i]); } } 四、问答题 1.分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 2设计动态规划算法的主要步骤为： （1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。 3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相的。而用分治法求解的问题，经分解得到的子问题往往是互相的。 4. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。 不同点：（1）求解目标不同； （2）搜索方式不同； （3）对扩展结点的扩展方式不同； （4）存储空间的要求不同。 5用回溯法搜索子集树的算法为： void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (constraint(t)&&bound(t)) backtrack(t+1); } } 6. 分治法所能解决的问题一般具有的几个特征是： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互的，即子问题之间不包含公共的子问题。 7. 用分支限界法设计算法的步骤是： (1)针对所给问题，定义问题的解空间（对解进行编码）；分 (2)确定易于搜索的解空间结构（按树或图组织解） ； (3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 8. 常见的两种分支限界法的算法框架 （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 9. 回溯法中常见的两类典型的解空间树是子集树和排列树。 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。 当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。 10. 分支限界法的搜索策略是： 在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。 五、算法题 1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度。 1. template int BinarySearch(Type a[], const Type& x, int n) {//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1 Int left=0; int right=n-1; While (left<=right){ int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } Return -1; } 时间复杂性为O(logn) 2. 利用分治算法写出合并排序的算法，并分析其时间复杂度 1. void MergeSort(Type a[], int left, int right) { if (left mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } } 算法在最坏情况下的时间复杂度为O(nlogn)。 3.N皇后回溯法 bool Queen::Place(int k) { //检查x[k]位置是否合法 for (int j=1;j return true; } void Queen::Backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=n;i++) { x[t]=i; if ( 约束函数 ) Backtrack(t+1); } } 4.最大团问题 void Clique::Backtrack(int i) // 计算最大团 { if (i > n) { // 到达叶结点 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return;} // 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == 0) { // i与j不相连 OK = 0; break;} if (OK ) { // 进入左子树 x[i] = 1; cn++; Backtrack(i+1); x[i] = 0; cn--; } if ( cn + n - i > bestn ) { // 进入右子树 x[i] = 0; Backtrack(i+1); } }下载本文
