i)的含义,用递推的方法写出求解步骤,得到结果)Р理解并掌握0/1背包问题的动态规划求解过程,会采用序偶直接解n值不大的0/1背包问题。Р第8章回溯法Р回溯法:是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。Р理解回溯法的基本思想,掌握状态空间树的画法及各种含义。掌握n皇后问题的算法及执行踪迹。Р能画出0/背包问题的状态空间树及子集树。Р回溯法效率的因素:Р?(1)产生x[k]的时间。Р?(2)满足显约束的x[k]值的个数。Р?(3)计算约束函数constraint的时间。Р?(4)计算上界函数bound的时间。Р?(5)满足约束函数和上界函数约束的所有x[k]的个数Р第9章分支限界法(了解)Р分支限界法的基本思想:Р(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式 搜索问题的解空间树。Р(2)在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。Р(3)此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程,这个过程一直持续到找到所需的解或活结点表这空时为止。Р最常见的分支限界法有两种:队列式(FIFO)分支限界法和优先队列式分支限界法。Р上课反复讲、反复强调的几个问题,要求懂原理,会设计(关键是思路,表达方法可以是语言、伪代码、代码),会进行复杂度分析。Р建议:答题时不要把所有的东西写一大段,适当分步骤、分要点,如XXX算法原理Р①做什么,怎么做Р②做什么,怎么做Р……等
全文预览
