算法设计-复习.ppt

作业： 1.0-1背包问题的算法设计策略与分析 2.设计一个实际问题，能够应用所学算法或经过变换解决。如流水作业调度算法可以应用到产品生产安排、设备分配等；旅行售货员问题可以应用到邮递员送信、物理配送线路选择等问题。 3.提出一个综合性问题，利用所学知识，设计出新的的算法。如旅行社优化安排旅游线路问题，设计出综合考虑游客、季节、费用等因素的优化算法。 4.21位水仙花数的算法设计与分析 5.旅行售货员问题的算法设计策略与分析 6.迷宫问题的算法设计策略与分析 7.n后问题的算法设计策略与分析 当一个问题具有最优子结构性质时，可用动态规划求解。但有时会有更简单有效的算法。 贪心算法并不是从整体最优上加以考虑，它所作出的选择只是某种意义上的局部最优选择。即使贪心算法不能得到整体最优解，但其最终结果也是最优解的很好的近似解。 （2）贪心算法解决 我们先计算出当前局部的最优解m(i,j),通过循环继续找出max(m(i+1,z))。 这也能体现出贪心算法比动态规划算法解决0-1背包问题的便捷性。 用贪心算法解决问题的前提是一个问题具有最优子结构性质。它所做的每一个选择都是当前状态下的局部最好选择。在解决背包问题中，也体现出了贪心算法在解决某些问题时的高效性。虽然贪心算法并不一定求出最优解，但也是解决问题的重要方法。 (1)定义解空间：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)} （3）回溯法解决 (2)构造解空间树： 0-1背包问题是子集选取问题。 其解空间可以用子集树表示。 在有哪些信誉好的足球投注网站解空间树时，只要其左儿子结点是一个可行结点，有哪些信誉好的足球投注网站就进入其左子树。 当右子树中有可能包含最优解时才进入右子树有哪些信誉好的足球投注网站。否则将右子树剪去。 可行性约束函数： ∑wixi≤C 上界函数： Bound() 利用回溯法解决问题完善但对于背包问题比较麻烦。回溯法在解决多个最优解问题时有很大的优势。 由于计算上界函数需要O(n)时间，在最坏情况下有O(2n)个右孩子结点需要上界函数，故计算0/1背包问题的回溯算法所需的计算时间复杂度为O(n2n)。 （3）分支限界法解决 0/1背包问题的分枝－限界算法可以使用最大收益算法定界函数来计算活结点的收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不可能超过upprofit，活结点的最大堆使用upprofit作为关键值域。 在子集树中执行最大收益分枝定界有哪些信誉好的足球投注网站的函数首先初始化活结点的最大堆，并使用一个数组bestx 来记录最优解。 函数中的循环首先检验E结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列（即最大堆）；仅当结点右孩子的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。 回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是O（解空间的最大路径长度)，而分枝限界所占用的内存为O（解空间大小）。对于一个子集空间，回溯法需要O(n)的内存空间, 而分枝限界则需要O(2n)的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法,并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中,它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。 在对0-1背包问题的求解过程中，我们可以清晰的看出四种算法的优劣性和各自的策略。四种算法解决背包问题的效率也各有差别。贪心算法效率最高，但并不一定是最优解；回溯法也比较好，但求解过程麻烦，并且是求出所有的最优解；动态规划最差，因为递归是最占用系统资源的方法。 （5）各种算法比较 最大收益或最小耗费分枝限界法，FIFO法 占用内存较大、效率不高 速度较快、易求解 O(2n) 分枝-限界法 判断右子树按效益密度vi/wi对剩余对象排序 时间复杂度较高 能够获得最优解 O(n2n) 回溯法 建立动态规划递归方程 速度较慢 可求得最有决策序列 O(min{nc，2n}) 动态规划法 启发式方法 很难得到最优解 速度较快 O(2n) 贪心法 改进方法 缺点 优点 时间复杂度 设计方法 * * 主要内容 分治策略 动态规划 贪心算法 回溯法 0-1背包问题的算法设计策略对比与分析 分支限界法 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 1.分治法 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 因为问题的计算复杂性一般是随