算法分析与设计no6.pdf

算法分析与设计 No.6 Analysis and Design of Algorithm 2017年3月9 日 第二章要点回顾  递归算法  概念（阶乘、Fibonacci数列、双递归）  例子（整数划分问题、Hanoi塔问题）  Hanoi塔算法、运行轨迹、分析时间复杂度  递推方程（迭代法求解）  递归的优缺点  分治策略  基本思想、适用条件、基本步骤  分治效率分析：给出了五种计算方法  范例学习：二分有哪些信誉好的足球投注网站、大整数乘法、Strassen矩阵乘 法、二分归并排序、快速排序、最近点对问题 2 第三章 动态规划 3 学习要点  理解动态规划算法的概念  掌握动态规划算法的基本要素  最优子结构性质  重叠子问题性质  掌握设计动态规划算法的步骤。  找出最优解的性质，并刻划其结构特征  递归地定义最优值  以自底向上的方式计算出最优值  根据计算最优值时得到的信息，构造最优解 4 动态规划算法概述 概述  最优化问题  最优性原理  动态规划法的设计思想 6 最优化问题  有n个输入，它的解由这n个输入的一个子集 组成，这个子集必须满足某些事先给定的条 件，这些条件称为约束条件，满足约束条件 的解称为问题的可行解。  满足约束条件的可行解可能不只一个，为了 衡量这些可行解的优劣，事先给出一定的标 准，这些标准通常以函数的形式给出，这些 标准函数称为目标函数，使目标函数取得极 值 （极大或极小）的可行解称为最优解，这 类问题就称为最优化问题。 7 例：付款问题 问题：超市自动POS机要找给顾客数量最少的现金。 分析：假定POS机中有n张面值为p i(1≤i≤n) 的货币， 用集合P={p , p , …, p }表示，如果POS机需支付的 1 2 n 现金为A ，那么，它必须从P 中选取一个最小子集S ， 使得 m p i S , p i A (m | S |) i 1 如果用向量X=( x , x , …, x )表示S 中所选取的货币， 1 2 n 则 1 p S  i x i  0 p i S 8 例：付款问题 n 那么，POS机支付的现金必须满足 x p A i i