算法分析设计 Posted on 2022-07-03 00:00:00 2022-07-03 00:00:00 by Author 摘要 期末算法分析设计考试总结 ## 【一】分治算法 分治算法得时间复杂度为:O(N)=aT(n/b)+f(n) 当 n=1时候,O(1)=1,其余为:nlog(n),链接:[时间复杂度分析](https://blog.csdn.net/qq_42691315/article/details/114105766);降低时间复杂度应减小a, ### 【二】动态规划 **动态规划概念**:多阶段决策过程的优化问题。可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。 **使用条件**:**有重叠子问题和优化子结构**。当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构。在问题的求解过程中,很多子问题的解将被多次使用即为重叠子问题。 ### 【三】贪心算法 **贪心算法的概念**:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。 **适用条件**:(1):**1、贪心选择性质**:一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。**2、最优子结构性质**:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。 **与动态规划不同之处**:贪心不能保证求得的最后解是最佳的,一般复杂度低,每一步的最优解一定包含上一步的最优解。;而动态规划本质是穷举法,可以保证结果是最佳的,复杂度高。 ### 【四】解空间 **解空间的概念**:一个问题的解空间是它的所有可能的解构成的集合。 **回溯算法常用的搜索策略**:深度优先搜索策略。 **分支限界算法与回溯算法关系**:分支限界法类似于回溯算法,但是回溯算法求的是可行解,分支限界法求得是最优解(在某种条件下)。分支限界法在回溯算法基础上增加了限界函数,可以筛选去除掉回溯算法求的可行解。并且由于分支限界算法加了一些约束,所以解空间树会比回溯算法的解空间树 分支少,分支限界使用的策略是广度优先和优先队列优;但是回溯算法使用的深度优先算法策略,分支限界算法的活结点只能访问一次,而回溯算法则不是。 ## 计算题 ### 【一】递推关系 ### 【二】 二分检索 ![二分检索问题](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2022-07-02/-5880683594804544432.png) ### 【三】递归树求解 ![递归树](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2022-07-02/-2405271265683595553) ### 【四】 判断阶数 洛必达法则,自己算,看高阶还是低阶 ## 综合题 ### 【一】 汉诺塔问题 ![](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2022-07-02/-6971435012444644112.png) ![时间复杂度分析](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2022-07-02/8546530929657169498.png) ### 【三】二分归并算法 ![](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2022-07-02/-2405271265683595553) 一、简答 1. 什么是算法?算法的基本概念和性质? 定义:求解问题的一系列指令步骤,用来将输入数据转换成输出结果 特征:有零个或多个外部量作输入;至少一个量作为输出;组成算法的每条指令清晰;算法中每条指令的执行次数有限。 核心:解决问题基本操作和步骤——顺序和控制 2. 什么是分治法?解决什么问题?具有什么特性?分治法的时间复杂度如何降低? 基本思想: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。 问题特点: (1)可缩性。问题的规模缩小到一定的程度就可以容易地解决; (2)最有子结构性。问题可以分解为若干个规模较小的相同问题; (3)可合性。利用该问题分解出的子问题的解可以合并为该问题的解; (4)独立性。该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 经典问题:(递归) 归并排序、堆排序、快速排序、二分查找、全排列问题、整数划分问题、求第k大元素。 分治法的时间复杂度如何降低?W(n)=aW(n/b)+d(n) (1)降低a的数值,减少子问题的个数 减少子问题数量的策略是有前提的,具体分析如下: 若这个分治算法的时间复杂度递推式满足主定理的第一个结论的条件,那么就可以得知其时间复杂度W(n)=Θ(n^logb`a),Θ是同阶符号,此时只要让对数中的a值减小,时间复杂度就会降低,a代表了划分的个数,也就是少划分几个子问题。 具体的减少策略是:找出子问题之间的依赖关系,也就是某些子问题的解可以由其他子问题依赖推导出来,那这些子问题可以减少。 例:整数位乘问题 (2)降低d(n)的阶,增加预处理 在分治之前,可以通过预处理一些数据来降低d(n)的阶,使得每次递归的时候d(n)不会带来一些过多的时间开销。 3.什么是贪心算法?解决什么问题?问题特性? 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 适用问题:局部最优策略能导致产生全局最优解。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。 Dijkstra算法、Prim算法和Kruskal算法都属于典型的贪心算法。 4.证明一个问题可以用贪心法解决 ①贪心选择性质 考察一个问题的整体最优解 证明:可修改这个解,使其以贪心选择开始 ②最优子结构性质 在规模为n的最优解下,包含的规模为n-1的解是这个规模下的最优解 ③每一步使用贪心选择,可以获得最优的解 归纳法证明:通过每一步的贪心,最终得到最优解 5.什么是动态规划?基本步骤?与贪心的区别? 基本思想: 将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解) 应用场景: 适用动态规划的问题必须满足最优化原理、无后效性和重叠性。 (1)最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。如果可以把局部子问题的解结合起来得到全局最优解,那这个问题就具备最优子结构。 (2)无后效性 将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。即要求每个子问题的决策不能对后面其他未解决的问题产影响, 如果产生就无法保证决策的最优性。 (3)子问题的重叠性 如果计算最优解时需要处理很多相同的问题,那么这个问题就具备重复子问题。 动态规划必须保证我们分割成的子问题也能按照相同的方法分割成更小的子问题, 并这些自问题的最终分割情况是可以解决的。 基本步骤: (1)分析最优解的性质,并刻画其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。 (4)根据计算最优值时得到的信息,构造一个最优解 与贪心的区别: (1)贪心:每一步的最优解一定包含上一步的最优解,上一步之前的最优解则不作保留;动态规划:全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有的局部最优解. (2)动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常自顶向下的方式进行 (3)贪心不能保证求得的最后解是最佳的,一般复杂度低;而动态规划本质是穷举法,可以保证结果是最佳的,复杂度高。 6.回溯法基本思想?解空间?名词解释(活结点,扩展结点),剪枝函数如何设计?扩展到其他问题中如何求解? 基本思想: 从一条路往前走,能进则进,不能进则退回来,换一条路再试。 确定了解空间的组织结构后,回溯法从根节点出发,以深度优先搜索方式搜索整个解空间。回溯法以这种工作方式递归地在解空间中搜索,直到找到所要求的解或解空间所有解都被遍历过为止。 解空间:子集树或排列树 名词解释: 活结点:自身已生成但其孩子结点没有全部生成的结点 扩展结点:指正在产生孩子结点的结点,E结点 死结点:指其所有结点均已产生的节点 首先根节点成为活结点,同时也成为当前的扩展结点 剪枝函数: 回溯法搜索解空间树时,通常采用两种策略避免无效搜索,提高回溯法的搜索效率。其一是用约束函数在当前节点(扩展节点)处剪去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。 可行性剪枝: 该方法判断继续搜索能否得出答案,如果不能直接回溯。 最优性剪枝:它记录当前得到的最优值,如果当前结点已经无法产生比当前更优的解时,可以提前回溯。 扩展到其他问题中如何求解? 应用回溯法解问题时,首先应该明确问题的解空间。 一个复杂问题的解决往往由多部分构成,即,一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。 解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来,解任何问题都有一个目标,在约束条件下使目标达到最优的可行解称为该问题的最优解。 7.分支限界搜索策略?与回溯的区别? 分支限界法是求解纯整数规划或混合整数规划问题的经典方法 基本思想: (1)以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树 (2)分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中 (3)然后从活结点表中取下一结点成为当前扩展结点 (4)重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止 搜索策略: 在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解 与回溯的区别: (1)求解目标不同 回溯法的求解目标是找出解空间树中满足约束条件的所有解 分支限界法的求解目标则是尽快找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解 分支限界法通常用于解决离散值的最优化问题 (2)搜索方式不同 回溯法以深度优先的方式(遍历结点)搜索解空间树 分支限界法以广度优先或最小耗费优先的方式搜索解空间树 (3)对扩展结点的扩展方式不同 分支限界法中,每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点,就一次性产生其所有儿子结点 (4)存储空间的要求不同 分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大 两种常见的分支限界法: (1)队列式分支限界法 按照队列先进先出(FIFO)原则选取下一个结点为扩展结点 从活结点表中取出结点的顺序与加入结点的顺序相同,因此活结点表的性质与队列相同 (2)优先队列分支限界法(代价最小或效益最大) 每个结点都有一个对应的耗费或收益,以此决定结点的优先级 从优先队列中选取优先级最高的结点成为当前扩展结点 如果查找一个具有最小耗费的解:则活结点表可用小顶堆来建立,下一个扩展结点就是具有最小耗费的活结点 如果希望搜索一个具有最大收益的解:则可用大顶堆来构造活结点表,下一个扩展结点是具有最大收益的活结点 二、综合题 1.分治法求最大子段和 将数组分成左右两半,分别计算左边的最大和、右边的最大和、跨边界的最大和,然后比较其中最大者 MaxSubSum(A, left, right){ // 如果A只有一个元素,则输出元素值(当值为负数时输出0); center (left+right)/2; leftsum <-MaxSubSum(A, left,center); rightsum <-MaxSubSum(A, center+1, right); s1 <- A1[center]; s2 <-A2[center]; sum <- s1+s2; if leftsum>sum then sum <-leftsum; if rightsum>sum then sum <-rightsum; } 时间复杂度: 假设问题规模即数组长度为n,那么: 第一次:[0, n/2], [n/2+1, n],每一部分是n/2 第二次:[0, n/4], [n/4+1, n/2], [n/2+1, 3n/4], [3n/4+1, n],每一部分是n/4 ... 第i次:假设第i次每个问题都不可再分,则每一部分为 n / n = 1,共有n项,于是有2^i = n 解得i = logn每一次分治的时间复杂度是O(n),二者相乘得时间复杂度O(nlogn) 2.分治法,循环赛日程表 设有 n=个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表: (1) 每个选手必须与其他 n−1个选手各赛一次; (2) 每个选手一天只能参赛一次; (3) 循环赛在n−1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行,第j列处填入第i个选手在第j天所遇到的选手。其中 1≤i≤n1,1≤j≤n−1。 按分治策略,我们可以将所有的选手分为两半,则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分,直到只剩下两个选手时,比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 ROUND-ROBIN-CALENDAR-REC(A,n): if n == 1: then A[1][1] = 1 return ROUND-ROBIN-CALENDAR-REC(A,n/2) m=n/2 for i = 1 to m for j = 1 to m do A[i][j+m]=A[i][j]+m A[i+m][j]=A[i][j+m] A[i+m][j+m]=A[i][j] 时间复杂度: 3.贪心算法,最小生成树(prim、kruskal)过程 (3)prim算法:每次都选择到下一顶点权最小的边。 初始S={1},选择连接S与V−S集合的最短边e={i,j},其中i∈S, j∈V−S.将e加入树T,j加入S。继续执行上述过程,直到S=V为止。 时间复杂度: 算法步骤执行O(n)次,每次执行O(n)时间:找连接 S与V-S 的最短边。算法时间:T(n) = O (n2) (2)Kruskal算法:每次都选择权最小的可以连通两个不同连通分支的边 按照长度从小到大对边排序.(2)依次考察当前最短边 e ,如果e与T的边不构成回路,则把e加入树T,否则跳过e. 直到选择了n-1条边为止. 算法时间:T(n) = O (n2) 4.贪心算法,活动安排 4.活动安排 算法思想:首先根据活动的结束时间将所有活动按升序排序,然后首先设定第一个活动选入可以独占使用资源的活动集合,之后依次比较待选集合当中活动是否与选中集合当中最后一个活动冲突,如果不冲突则选入活动。整个思想确保了资源的在使用时间最长,并且将得出最多活动使用资源解集当中的一个解。 伪代码: n ← length [S] A ← {1} j ← 1 for i ← 2 to n do if si ≥ fj then A ← A ∪{ i } j ← i return A 时间复杂度:当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。 5.动态规划,0-1背包 算法思想: 建立优化解代价的递归方程 递归地划分子问题 自底向上计算优化解的代价,记录优化解的构造信息:根据递归方程,自底向上从规模最小的子问题的最优解的代价开始计算,然后不断利用子问题的最优解代价构造更大问题最优解代价,直到计算出m(1,c)为止 算法伪码: (设w-1<C) void Knapsack(float v[], int w[], int C, int n, float m[n][]) { for (j=0; j<w[n];j++) m[n][i]=0; for (j= w[n]; j<=C; jt+) m[n][们]= v[n]; for ( i= n-1 ; i >= 2 ; i--){ for ( j=0 ; j<= w[i]-1; j++) m[i][i]=m[i+1][i];for (j=wi]; j<-C ; j++) m[i][i]=max {m[i+1][i], m[i+1][j-w[i]]+v[i]}; } if(C<wl )m[1][C]=m[2][C];else m[1][C]=max {m[2][C], m[2][C-w[1]]+v[1]}; } 时间复杂度:T(n)=O(2n) 6. 动态规划,图像压缩 算法思想: 对每个段给出两个整数值,一个表示该段含有的像素个数,一个表示每个像素所占用的二进制位数.比如第i段,有l[i]个像素,每个像素用b[i]位. 伪代码: Compress (P,n) Lmax ←256;header←11; S[0]←0 for i ←1 to n do b[i] ←length(P[i]) bmax ←b[i] S[i]←S[i−1]+bmax l[i] ←1 for j←2 to min{i, Lmax} do if bmax < b[i−j+1] then bmax ← b[i−j+1] if S[i] > S[i− j] + j *bmax then S[i] ← S[i− j] + j *bmax l[i]← j S[i]← S[i] + header 时间复杂度:O(n) 7.动态规划,最大子段和 基本思想:前边界为1,后边界i,C[i]是A[1.. i]中必须包含元素A[i]的向前连续延伸的最大子段和。 伪代码: MaxSum (A, n) sum←0 b←0 for i ←1 to n do if b > 0 then b ← b + A[i] else b ← A[i] if b > sum then sum b c ← i return sum , c 时间复杂度:O(n) 8.回溯法,装载问题 用回溯法解装载问题时,用子集树表示其解空间显然是最合适的。用可行性约束函数可剪去不满足约束条件的子树。在子集树的第j+1层的结点Z处,用cw记当前的装载重量,即当 cw>C1 时,以结点Z为根的子树中所有结点都不满足约束条件,因而该子树中的解均为不可行解,故可将该子树剪去。(该约束函数去除不可行解,得到所有可行解)。 可以引入一个限界函数,用于剪去不含最优解的子树,从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量;bestw是当前最优载重量;r是剩余集装箱的重量,即。定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此,当cw+r<=bestw时,可将z的右子树剪去。 子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间称为子集树。例如,那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有2^n个叶节点,其节点总个数为2^(n+1)-1。遍历子集树的任何算法均需要O(2^n)的计算时间(装载问题,0-1背包) void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } 排列树 :当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树 。排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间(旅行社售货员、n皇后) void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } 9. 分支限界,0-1背包 算法的思想 首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。 在实现时,由Bound计算当前结点处的上界。在解空间树的当前扩展结点处,仅当要进入右子树时才计算右子树的上界Bound,以判断是否将右子树剪。进入左子树时不需要计算上界,因为其上界与其父节点上界相同。 在优先队列分支限界法中,结点的优先级定义为:以结点的价值上界作为优先级(由bound函数计算出) 伪码 while (i != n+1){//非叶结点 //检查当前扩展结点的左儿子结点 Typew wt = cw + w[i]; if (wt <= c){//左儿子结点为可行结点 if (cp+p[i]> bestp) bestp = cp+p[i]; AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);} up = Bound(i+1); //检查当前扩展结点的右儿子结点 if (up >= bestp)//右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); //取下一个扩展节点 时间复杂性:算法的时间复杂度为O(n2n)。 10.分支限界,装载 队列式分支限界法 解装载问题的队列式分支限界法仅求出所要求的最优值,稍后进一步构造最优解。 首先检测当前扩展结点的左儿子结点是否为可行结点。如果是,则将其加入到活结点队列Q中。 然后,将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后,当前扩展结点被舍弃。 活结点队列中,队首元素被取出作为当前扩展结点。 活结点队列已空,算法终止。 算法的改进 算法MaxLoading初始时bestw=0,直到搜索到第一个叶结点才更新bestw。在搜索到第一个叶结点前,总有Ew+r>bestw, 此时右子树测试不起作用。 为确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。 代码改进(伪代码) while (true) { // 检查左儿子结点 // wt=Ew + w[i]; // 左儿子结点的重量 if (wt<= c) { // 可行结点 if (wt > bestw) bestw = wt; //提前更新bestW,注意更新条件 // 加入活结点队列 if (i <= n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r > bestw && i <= n) //右儿子剪枝 Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++; r-=w[i];} // 进入下一层 } } 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。 活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量Ew(即:当前扩展结点船的载重量Ew)再加上剩余集装箱的重量r之和(即:将上界Ew+r定义为结点优先级)。 优先队列中优先级最大的活结点成为下一个扩展结点。 子集树中叶结点所相应的载重量与其优先级(上界值)相同,即:该叶子结点的上界值等于当前叶子结点处船的重量Ew。 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 求最优解 在优先队列的每一个活结点中,保存从解空间树的根结点到该活结点的路径,在算法确定了达到最优值的叶结点时,就在该叶结点处同时得到相应的最优解。 在算法的搜索进程中,保存当前已构造出的部分解空间树,这样在算法确定了达到最优值的叶结点时,可以在解空间树中从该叶结点开始向根结点回溯,构造出相应的最优解。 时间复杂度:O(2n) 11. 回溯,哨兵问题 算法思想: 设回溯搜索时,当前关注的陈列室是[iji],假设该陈列室已经受到监视,即y[i][li]==1,此时在陈列室[i]处设置一个警卫机器人哨位,即x[i][ij]==1,相应于解空间树的一个节点q,在陈列室[ i+1,j]处设置一个机器人哨位,x[i+1][i]==1,相应于解空间树的另一个节点p。容易看出,以q为根的子树的解,不优于以p为根的子树的解,以q为根的子树可以剪去。因此,在以从上到下,从左到右的顺序依次考察每一个陈列室时,已受监视的陈列室不必设置警卫机器人哨位。 设陈列室[ii]是从上到下、从左到右搜索到的第一个未受监视的陈列室,为了使陈列室[i,i]受到监视,可在陈列室[i+1,j]、[iji]、[ij+1]处设置警卫机器人哨位,在这3处设置哨位的解空间树中的结点分别为p、q、r。 当y[li][j+1]==1时,以q为根的子树的解,不优于以p为根的子树的解,当 y[i]lj+1]==1且y[i][j+2]==-1时,以r为根的子树的解,不优于以p为根的子树的解。搜索时应按照p、q、r的顺序来扩展结点,并检测节点p对节点q和节点r的控制条件。 伪码: int [] [ ] bestx=new int [ MAX][MAX];//x用来设置当前警卫,y用来表示监控 //情况,bestx返回最终结果 int n,m,best,k = 0, t = 0;//当前已设置的警卫数为k,受监视的陈列室 //数为t,当前最少警卫数为best void change (int i, int j){ //在(i,j)处设置一个警卫,并改变其周围受//监控情况 x[ i][j] = 1; k+十; for (int r = l; r <= 5; r++) {//在自己本身跟上下左右五个地方设置受控 int p = i + d[r] [ 1]; int q = j + d[r][2];y[p] [ q]++; if (y[p] [q] == 1) t十十; } void restore(int i, int j) { }//撤销在(i,j)处设置的警卫,并改变其周围 //受监控情况 void search (int i, int j) { }//回溯搜索,从上到下、从左至右搜索没被监控的 /!位置 时间复杂度:因此时间复杂度为:O(n2n ) 三、计算 1.动态规划,0-1背包 对于以下四个物品 (1): W=2,V=1 (2): W=3,V=3 (3): W=4,V=5 (4): W=7,V=9 若背包容量为10,则装入价值最大为多少? 根据公式构造dp表,其中i为物品标号,p表示背包剩余容量 Val(i,p)=val(i-1,p) 0⩽p⩽ Val(i,p)=max{val(i-1,p),val(i-1,p-)+} ⩽p 物品 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 2 0 0 1 3 3 4 4 4 4 4 4 3 0 0 1 3 5 5 6 8 8 9 9 4 0 0 1 3 5 5 6 9 9 10 12 根据表格可知装入物品2和4,可以使背包内物品总价值最大。 根据dp表的构造,我们可以得到动态规划求解0-1背包的算法思想。第一步:判断背包当前的容量j是否大于物品当前的质量,如果物品的质量大于背包的容量那么就舍弃。第二步:如果背包可以装下这个物品,就需要判断装下该物品获取的最大价值是不是大于不装下这个物品所获取的最大价值,如果大于那么就把东西装下。 2. 求解复杂度(递推/递归树,迭代,主定理) 递归: int fibo(int n){ if(n<=1) return 1; return fibo(n-1)+fibo(n-2); } 时间复杂度:T(n)=O(1)+T(n-1)=n-1O(1)+T(1)=nO(1)=O(n) 迭代: 汉诺塔: 时间复杂度: T(1)=1= T(2)=2T(1)+1= T(3)=2T(2)+1= …… T(n) == 故:T(n)==O() 主定理法: 合并排序问题
{{ item.content }}
{{ child.content }}