最强算法分析

根据慕课上的清华大学的算法分析与设计整理出来。

算法分析

• 1.算法的主要内容
  • 1.两个例子
    • 1.调度问题
      • 1.问题
        • 有n项任务,每项任务加工时间已知.从 0时刻开始陆续安排到一台机器上加工.每个任务的完成时间是从 0 时刻到任务加工截止的时间. 求: 总完成时间（所有任务完成时间之和）最短的安排方案
      • 2.实例
        • 任务集s={1,2,3,4,5}, 加工时间:t1=3,t2=8,t3=5,t4=10,t5=15
      • 3.贪心法的解
        • 1.算法：按加工时间(3,8,5,10,15)从小到大安排
        • 2.总完成时间： t= 3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15)= 3×5 + 5×4 + 8×3 +10×2 +15= 94
      • 4.问题建模
        • 1.输入: 任务集：s={1,2,… ,n},第j项任务加工时间:tj ∈Z+,j=1,2…,n.
        • 2.输出：调度i,S 的排列i1,i2,…,in
        • 3.目标函数：i的完成时间:
          • 每个任务执行的次数越在前执行次数越多最前面应为时间最少的
        • 4.解I*：使得t(I*)达到最小,即t(i* )=min{t(I)|i为S的排列}
    • 2.算法设计
      • 1.问题建模
      • 2.选择什么算法？如何描述这个方法？
      • 3.这个方法是否对所有实例都得到最优解？如何证明？
      • 4.如果不是,能否找到反例？
    • 3.投资问题
      • 1.问题
        • m元钱,投资n个项目.效益函数fi(x),表示第i个项目投x元的效益,i=1,2,…,n.求如何分配每个项目的钱数使得总效益最大？
      • 2.建模
        • 1.输入：n,m,fi(x),i=1,2,...,n,x=1,2,...,m
        • 2.解：n维向量<x1,x2,… ,xn>,xi是第i个项目的钱数,使得下述条件满足：
        • 3.目标函数:
        • 4.约束条件:
      • 3.蛮力算法
        • 对所有满足下述条件的向量 <x1,x2,…,xn> ,x1+x2 + … +xn=m,xi为非负整数,i=1,2 ,...,n,计算相应的效益:f1(x1)+f2(x2)+ … +fn(xn)从中确认效益最大的向量
    • 4.小结
      • 1.问题求解的关键
        • 1.建模：对输入参数和解给出形式化或半形式化的描述
        • 2.设计算法：采用什么算法设计技术,正确性——是否对所有的实例都得到正确的解
        • 3.分析算法——效率
  • 2.问题计算复杂度的界定:排序问题
    • 1.排序算法的效率
  • 3.货郎问题与计算复杂性理论
    • 1.货郎问题
      • 1.问题
        • 有n个城市,已知任两个城市之间的距离.求一条每个城市恰好经过1次的回路,使得总长度最小
      • 2.建模与算法
        • 1.输入: 有穷个城市的集合c={c1,c2,…,cn},距离d(ci,cj)=d(cj,ci)∈Z+,1≤i<j≤n
        • 2.解：1,2 …,n的排列k1,k2,…,kn使得：
      • 3.现状
        • 至今没找到有效的算法
    • 2.0-1背包问题
      • 1.问题
        • 有n个件物品要装入背包,第i件物品的重量Wi,价值vi,i=1,2,…,n.背包最多允许装入的重量为B,问如何选择装入背包的物品,使得总价值达到最大？
      • 2.建模
        • 1.问题的解：0-1向量 <x1,x2,...,xn>xi=1⇔ 物品i装入背包
        • 2.目标函数:
        • 3.约束条件:
    • 3.双机调度
      • 1.问题
        • 有n项任务,任务i的加工时间为ti,ti∈Z+,i=1,2,…,n.用两台相同的机器加工,从0时刻开始计时,完成时间是后停止加工机器的停机时间.问如何把这些任务分配到两台机器上,使得完成时间达到最小？
      • 2.建模
        • 解: 0-1向量 <x1,x2,...,xn>,xi=1表示任务i分 配到第一台机器,i=1,2,...,n.如何对该问题建模?目标函数与约束条件是什么？不妨设机器1的加工时间 ≤ 机器2的加工时间令T=t1+t2+...+tn,d=T/2 ,机器1的加工时间不超过D,且达到最大.
    • 4.NP-hard问题
      • 1.这样的问题有数千个,大量存在于各个应用领域
      • 2.至今没找到有效算法：现有的算法的运行时间是输入规模的指数或更高阶函数
      • 3.至今没有人能够证明对于这类问题不存在多项式时间的算法
      • 4.从是否存在多项式时间算法的角度看,这些问题彼此是等价的.这些问题的难度处于可有效计算的边界
    • 5.算法+数据结构=编程
      • 1.好的算法
        • 提高求解问题的效率,节省存储空间
      • 2.算法的研究目标
        • 1.算法设计技术: 问题→建模并寻找算法
        • 2.算法分析方法: 算法→算法的评价
        • 3.问题复杂度分析: 算法类→问题复杂度估计
        • 4.计算复杂性理论: 问题类→能够求解的边界
  • 4.算法及其时间复杂度
    • 1.问题及实例
      • 1.问题
        • 需要回答的一般性提问,通常含若干参数
      • 2.问题描述
        • 定义问题参数(集合,变量,函数,序列等)说明每个参数的取值范围及参数间的关系定义问题的解说明解满足的条件(优化目标或约束条件)
      • 3.问题实例
        • 参数的一组赋值可得到问题的一个实例
    • 2.算法
      • 1.算法
        • 有限条指令的序列,这个指令序列确定了解决某个问题的一系列运算或操作
      • 2.算法A解问题P
        • 把问题P的任何实例作为算法A的输入每步计算是确定性的A能够在有限步停机输出该实例的正确的解
    • 3.基本运算与输入规模
      • 1.算法时间复杂度
        • 针对指定基本运算,计数算法所做运算次数
      • 2.基本运算
        • 比较,加法,乘法,置指针,交换
        • • 排序: 元素之间的比较 • 检索: 被检索元素x与数组元素的比较 • 整数乘法: 每位数字相乘(位乘)1次m位和n位整数相乘要做mn次位乘 • 矩阵相乘: 每对元素乘1次i×j矩阵与j×k矩阵相乘要做ijk次乘法 • 图的遍历: 置指针
      • 3.输入规模
        • 输入串编码长度,通常用下述参数度量：数组元素多少,调度问题的任务个数,图的顶点数与边数等
        • • 排序：数组中元素个数n • 检索：被检索数组的元素个数n • 整数乘法：两个整数的位数m,n • 矩阵相乘：矩阵的行列数i,j,k • 图的遍历：图的顶点数n,边数m
    • 4.算法的两种时间复杂度
      • 1.最坏情况下的时间复杂度W(n)
        • 算法求解输入规模为n的实例所需要的最长时间
      • 2.平均情况下的时间复杂度A(n)
        • 在给定同样规模为n的输入实例的概率分布下,算法求解这些实例所需要的平均时间
  • 5.算法的伪码表示
    • 1.算法的伪码描述
      • 赋值语句：← 分支语句：if…then… [else…] 循环语句：while,for,repeat until 转向语句：goto 输出语句：return 调用：直接写过程的名字 注释：//…
  • 6.函数的渐近的界
    • 1.大O符号:≤
      • 1.定义
        • 设f和g是定义域为自然数集N上的函数.若存在正数c和n0,使得对一切n≥n0有0≤f(n)≤cg(n)成立,则称f(n)的渐近的上界是g(n),记作f(n)=O(g(n))
      • 2.注意
        • 1.f(n)=O(g(n)),f(n)的阶不高于g(n)的阶
        • 2.可能存在多个正数c,只要指出一个即可
        • 3.对前面有限个值可以不满足不等式
        • 4.常函数可以写作O(1)
    • 2.大Ω符号:≥
      • 1.定义
        • 设f和g是定义域为自然数集N上的函数.若存在正数c和n0,使得对一切n≥n0有0≤cg(n)≤f(n)成立,则称f(n)的渐近的下界是g(n),记作f(n)=Ω(g(n))
      • 2.注意
        • 1.f(n)=Ω(g(n)),f(n)的阶不低于g(n)的阶
        • 2.可能存在多个正数c,只要指出一个即可
        • 3.对前面有限个值可以不满足不等式
    • 3.小o符号:＜
      • 1.定义
        • 设f和g是定义域为自然数集N上的函数.若对于任意正数c都存在n0,使得对一切n≥n0有 0≤f(n)<cg(n)成立,记作f(n)=O(g(n))
      • 2.注意
        • 1.f(n)=O(g(n)),f(n)的阶低于g(n)的阶
        • 2.对不同正数c,n0不一样.c越小n0越大
        • 3.对前面有限个n值可以不满足不等式
    • 4.小ω符号:＞
      • 1.定义
        • 设f和g是定义域为自然数集N上的函数.若对于任意正数c都存在n0,使得对一切n≥n0有 0≤cg(n)<f(n)成立,记作f(n)= ω(g(n))
      • 2.注意
        • 1.f(n)= ω(g(n)),f(n)的阶高于g(n)的阶
        • 2.对不同正数c,n0不一样.c越小n0越大
        • 3.对前面有限个n值可以不满足不等式
    • 5.Θ符号:=
      • 1.定义
        • 若f(n)=O(g(n))且f(n)= Ω(g(n)),则记作f(n)= Θ(g(n))
      • 2.注意
        • 1.f(n)的阶与g(n)的阶相等
        • 2.对前面有限个n值可以不满足条件
  • 7.有关函数渐近的界的定理
    • 1.定理1
    • 2.定理2
    • 3.定理3
      • 假设函数f和g的定义域为自然数集,若对某个其它函数h,有f=O(h)和g=O(h),那么f+g=O(h).该性质可以推广到有限个函数.算法由有限步骤构成.若每一步的时间复杂度函数的上界都是h(n),那么该算法的时间复杂度函数可以写作O(h(n))
  • 8.几类重要的函数
    • 1.基本函数类
    • 2.对数函数
    • 3.指数函数与阶乘
    • 4.取整函数
  • 9.评价算法的主要方面
    • 1.正确性
      • 1.评价算法的首要因素
      • 2.程序正确性证明,程序测试,即使很小的错误也可能会引发巨大的连锁反应,导致严重的后果
    • 2.健壮性
      • 1.算法/程序不仅对正确的输入能计算出正确的结果,对不正确的输入也能应对处理
    • 3.简单性
      • 1.算法/程序的可读性好,已调试,改进
    • 4.高效性
      • 1.时间/空间复杂度较低,特别是时间复杂度
    • 5.最优性
      • 1.证明所给算法是解决同一类问题中最好的
• 2.算法的数学基础
  • 1.序列求和的方法
    • 1.数列求和公式
      • 1.等差、等比数列与调和级数
    • 2.估计和式上界的放大法
    • 3.估计和式渐近的界
  • 2.递推方程与算法分析
    • 1.递推方程
      • 1.定义
        • 设序列a0,a1,...,an简记为{an},一个把an与某些个ai(i<n)联系起来的等式叫做关于序列{an}的递推方程
      • 2.求解
        • 给定关于序列{an}的递推方程和若干初值,计算an
    • 2.例子
      • 1.Hanoi塔问题
        • 1.问题
          • n个盘子从大到小顺序放在A柱上,要把它们从A移到c,每次移动1个盘子,移动时不允许大盘压在小盘上.设计一种移动方法
        • 2.伪码
          • 算法 Hanoi (A, C, n) // n个盘子A到C 1. if n=1 then move (A, C) // 1个盘子A到C 2. else Hanoi (A, B, n-1) 3. move (A, C) 4. Hanoi (B, C, n-1) 设 n个盘子的移动次数为 T(n),T(n) = 2 T(n-1) + 1， T(1) = 1， 解 T(n) = 2^n -1 这是一个难解的问题，不存在多项式时间的算法！
  • 3.迭代法求解递推方程
    • 1.迭代法
      • 1.定义
        • • 不断用递推方程的右部替换左部 • 每次替换,随着n的降低在和式中多出一项 • 直到出现初值停止迭代 • 将初值代入并对和式求和 • 可用数学归纳法验证解的正确性
      • 2.Hanoi塔算法
    • 2.换元迭代
      • 1.定义
        • • 将对n的递推式换成对其他变元k的递推式 • 对k直接迭代 • 将解(关于k的函数)转换成关于n的函数
      • 2.二分归并排序
    • 3.解的正确性-归纳验证
      • 证明:下述递推方程的解是W(n)=n(n-1)/2,W(n)=W(n-1)+n-1,W(1)=0 方法：数学归纳法,证n=1,W(1)=1(1-1)/2= 0, 假设对于n,解满足方程,则W(n+1)=W(n)+n=n(n-1)/2 +n=n[(n-1)/2+1]=n(n+1)/2
  • 4.差消法化简高阶递推方程
    • 1.快速排序平均工作量
    • 2.差消化简
      • 1.利用两个方程相减,将右边的项尽可能消去,以达到降阶的目的
  • 5.递归树
    • 1.递归树的概念
      • • 递归树是迭代计算的模型. • 递归树的生成过程与迭代过程一致. • 递归树上所有项恰好是迭代之后产生和式中的项. • 对递归树上的项求和就是迭代后方程的解
    • 2.迭代在递归树中的表示
    • 3.递归树的生成规则
      • • 初始,递归树只有根结点,其值为W(n) • 不断继续下述过程：将函数项叶结点的迭代式W(m)表示成二层子树,用该子树替换该叶结点 • 继续递归树的生成,直到树中无函数项(只有初值)为止
  • 6.主定理及其证明
    • 1.应用背景
      • 求解递推方程t(n)=At(n/b)+f(n) A： 归约后的子问题个数 n/b：归约后子问题的规模 f(n)：归约过程及组合子问题的解的工作量
    • 2.主定理
  • 7.主定理的应用
    • 1.求解递推方程
    • 2.递归算法分析
    • 3.不能使用主定理的例子
• 3.分治的设计思想
  • 1.分治策略的设计思想
    • 1.分治策略
      • 1.将原始问题划分或者归结为规模较小的子问题 2.递归或迭代求解每个子问题 3.将子问题的解综合得到原问题的解 4.算法的分析方法:递推方程
      • 注意： 1.子问题与原始问题性质完全一样 2.子问题之间可彼此独立地求解 3.递归停止时子问题可直接求解
    • 2.二分检索
      • 1.伪码
        • 算法 Binary Search (T, l, r, x) 输入：数组 T，下标从 l 到 r；数 x 输出：j // 若x在T 中, j 为下标; 否则为 0 1. l←1; r←n 2. while l≤r do 3. m←(l +r)/2 // m为中间位置 4. if T[m]=x then return m // x是中位数 5. else if T[m]>x then r←m-1 6. else l←m+1 7. return 0
      • 2.设计思想
        • • 通过x与中位数的比较,将原问题归结为规模减半的子问题,如果x小于中数, 则子问题由小于x的数构成,否则子问题由大于x的数构成. • 对子问题进行二分检索. • 当子问题规模为1时,直接比较x与t[m],若相等则返回m,否则返回 0.
      • 3.时间复杂度分析
        • W(n)=W(Ln/2」)+1,W(1)=1,可以解出w(n)=Llogn」+1
    • 3.二分归并排序
      • 1.伪码
        • 算法 Merge Sort (A, p, r) 输入：数组 A[ p .. r] 输出：元素按从小到大排序的数组 A 1. if p < r 2. then q ←( p + r)/2 对半划分 3. Merge Sort (A, p, q) 子问题1 4. Merge Sort (A, q+1, r) 子问题 2 5. Merge (A, p, q, r) 综合解
      • 2.设计思想
        • • 划分将原问题归结为规模为n/2 的2 个子问题 • 继续划分,将原问题归结为规模为n/4 的 4 个子问题.继续...,当子问题规模为1时,划分结束. • 从规模1到n/2,陆续归并被排好序的两个子数组.每归并一次,数组规模扩大一倍,直到原始数组
      • 3.时间复杂度分析
        • W(n)= 2W(n/2)+n-1,W(1)= 0,可以解出,W(n)=nlogn-n+1
  • 2.分治的一般描述
    • 1.一般性描述
    • 2.设计要点
      • • 原问题可以划分或者归约为规模较小的子问题,子问题与原问题具有相同的性质 子问题的求解彼此独立,划分时子问题的规模尽可能均衡 • 子问题规模足够小时可直接求解 • 子问题的解综合得到原问题的解 • 算法实现：递归或迭代
    • 3.时间分析
      • 1.递推方程
        • •P1,P2,…,Pk为划分后产生的子问题 •f(n)为划分子问题以及将子问题的解综合得到原问题解的总工作量 •规模为c的最小子问题的工作量为C
    • 4.两类常见的递推方程
    • 5.递推方程的求解
      • 方程1：迭代法、递归树 方程2：迭代法、换元法、递归树、主定理
    • 6.方程2的解
  • 3.芯片测试
    • 1.一次测试过程
      • 1.测试方法
        • 将2片芯片（A和B）置于测试台上,互相进行测试,测试报告是“好”或“坏”,只取其一
      • 2.假设
        • 好芯片的报告一定是正确的,坏芯片的报告是不确定的（可能会出错）
    • 2.测试结果分析
    • 3.问题
      • 1.输入
        • n片芯片,其中好芯片至少比坏芯片多1片
      • 2.问题
        • 设计一种测试方法,通过测试从n片芯片中挑出1片好芯片
      • 3.要求
        • 使用最少的测试次数
    • 4.判定芯片A的好坏
      • 1.问题
        • 给定芯片A,判定A的好坏
      • 2.方法
        • 1.用其他n-1片芯片对A测试
        • 2.奇数
          • n=7：好芯片数≥4. A好,6个报告中至少 3 个报“好” A坏,6个报告中至少 4 个报“坏”
          • n是奇数：好芯片数≥(n+1)/2. A好,至少有(n-1)/2个报“好” A坏,至少有(n+1)/2个报告“坏”
          • 结论：至少一半报“好”,A是好芯片, 超过一半报“坏”,A是坏芯片.
        • 3.偶数
          • n=8：好芯片数≥5. A好,7个报告中至少 4 个报“好” A坏,7个报告中至少 5 个报“坏”
          • n是偶数：好芯片数≥n/2+1. A好,至少有n/2个报告“好” A坏,至少有n/2+1个报告“坏”
          • 结论：n-1份报告中, 至少一半报“好”,则A为好芯片 超过一半报“坏”,则A为坏芯片
    • 5.蛮力算法
      • 1.测试方法
        • 任取1片测试,如果是好芯片,测试结束；如果是坏芯片,抛弃,再从剩下芯片中任取1片测试,直到得到1片好芯片
      • 2.时间估计
        • 第1片坏芯片,最多测试n-2次, 第2片坏芯片,最多测试n-3次,总计Θ(n^2)
    • 6.分治算法
      • 1.偶数
        • 1.方法
          • 假设n为偶数,将n片芯片两两一组做测试淘汰,剩下芯片构成子问题,进入下一轮分组淘汰
        • 2.淘汰规则
          • "好,好" →任留1片,进入下轮 其他情况→全部抛弃
        • 3.递归截止条件：n≤3
          • 3 片芯片,1次测试可得到好芯片.1或 2 片芯片,不再需要测试
      • 2.奇数
        • 1.当n为奇数时,增加一轮对轮空芯片的单独测试,如果该芯片为好芯片,算法结束；如果是坏芯片,则淘汰该芯片
    • 7.伪码描述
    • 8.时间复杂度
      • W(n)=W(n/2)+O(n),W(3)=1,W(2)=W(1)= 0 解得W(n)=O(n)
  • 4.快速排序
    • 1.基本思想
      • • 用首元素x作划分标准,将输入数组A划分成不超过x的元素构成的数组AL,大于x的元素构成的数组AR.其中AL,AR从左到右存放在数组A的位置. • 递归地对子问题AL和AR进行排序,直到子问题规模为1时停止
    • 2.伪码
    • 3.划分过程
    • 4.时间复杂度
      • 1.最坏情况
        • W(n)=W(n-1)+n-1,W(1)= 0,W(n)=n(n-1)/2
      • 2.最好划分
        • T(n)= 2t(n/2)+n-1,T(1)= 0,T(n)=Θ(nlogn)
      • 3.均衡划分
        • 均衡划分：子问题的规模比不变,例如为1:9,T(n)=t(n/10)+t(9n/10)+n,T(1)= 0 根据递归树,时间复杂度,T(n)= Θ(nlogn)
      • 4.平均时间复杂度
  • 5.幂乘算法及应用
    • 1.传统算法
      • 1.顺序相乘,乘法次数: Θ(n)
    • 2.分治算法
    • 3.分治算法分析
      • 以乘法作为基本运算,子问题规模：不超过n/2 两个规模近似n/2的子问题完全一样,只要计算1次,W(n)=W(n/2)+ Θ(1),W(n)= Θ(logn)
    • 4.应用
      • 1.Fibonacci数列：1,1,2,3,5,8,13,21,…
      • 2.增加f0=0,得到数列 0,1,1,2,3,5,8,13,21,…
      • 3.问题:已知f0=0,f1=1,给定n,计算fn
      • 4.通常算法：从f0,f1,… 开始,根据递推公式Fn=fn-1+fn-2,陆续相加可得Fn,时间复杂度为Θ(n)
      • 5.Fibonacci数的性质
        • 1.定理1设{Fn}为fibonacci数构成的数列,那么
      • 6.算法
        • 1.
        • 2.时间复杂度
          • • 矩阵乘法次数t(n)=Θ(logn) • 每次矩阵乘法需要做 8 次元素相乘 • 总计元素相乘次数为Θ(logn)
  • 6.改进分治算法的途 径1:减少子问题数
    • 1.依据
      • 1.分治算法的时间复杂度方程W(n)=AW(n/b)+d(n) A：子问题数,n/b：子问题规模,d(n)：划分与综合工作量
      • 2.当A较大,b较小,d(n)不大时,方程的解：
      • 3.减少a是降低函数W(n)的阶的途径.利用子问题的依赖关系,使某些子问题的解通过组合其他子问题的解而得到
    • 2.整数位乘问题
      • 1.输入：x,y是n位二进制数,n= 2^k
      • 2.普通乘法：需要O(n^2)次位乘运算
      • 3.简单划分
      • 4.减少子问题个数
        • 1.子问题间的依赖关系：代数变换AD+BC=(A-B)(D-C)+AC + BD
        • 2.算法复杂度W(n)= 3W(n/2)+cn,W(1)=1
        • 3.方程的解:W(n)=O(nlog3)=O(n^1.59)
    • 3.矩阵相乘问题
      • 1.输入：A,B 为n阶矩阵,n=2^k
      • 2.通常矩阵乘法：C 中有n2个元素,每个元素需要做n次乘法,以元素相乘为基本运算W(n)=O(n^3)
      • 3.简单分治算法
        • 1.
        • 2.递推方程W(n)= 8W(n/2)+cn^2,W(1)=1,解W(n)=O(n^3)
      • 4.Strassen矩阵乘法
        • 1.变换方法：设计m1,M2,…,M7,对应7个子问题
        • 2.利用中间矩阵,得到结果矩阵
        • 3.时间复杂度:W(n)= 7W(n/2)+18(n/2)^2,W(1)=1,解W(n)=O(n^log7)=O(n^2.8075)
      • 5.矩阵乘法的研究及应用
        • 1.难度
          • •coppersmith–Winograd算法：O(n^2.376)目前为止最好的上界 • 目前为止最好的下界是：Ω(n^2)
        • 2.应用
          • • 科学计算、图像处理、数据挖掘等 • 回归、聚类、主成分分析、决策树等挖掘算法常涉及大规模矩阵运算
    • 4.改进途径小结
      • • 适用于：子问题个数多,划分和综合工作量不太大,时间复杂度函数W(n)= Θ(n^logb^a) • 利用子问题依赖关系,用某些子问题解的代数表达式表示另一些子问题的解,减少独立计算子问题个数. • 综合解的工作量可能会增加,但增加的工作量不影响W(n)的阶
  • 7.改进分治算法的途 径2：增加预处理
    • 1.平面点对问题
      • 1.问题
        • 输入: 平面点集P中有n个点,n>1 输出:P中的两个点,其距离最小
      • 2.蛮力算法
        • C(n,2)个点对,计算最小距离,O(n^2)
      • 3.分治策略
        • P 划为大小相等的PL和PR
        • 1.分别计算PL、PR中最近点对 2.计算PL与PR中各一个点的最近点对 3.上述情况下的最近点对是解
      • 4.算法伪码
      • 5.跨边界处理
      • 6.算法分析
        • T(n)=2T(n/2)+O(nlogn),T(n)=O(1),n≤3,递归树求解t(n)=O(n(logn)^2)
      • 7.增加预处理
        • 1.原算法：在每次划分时对子问题数组重新排序
        • 2.改进算法
          • 1.在递归前对x,y排序,作为预处理 2.划分时对排序的数组x,y进行拆分,得到针对子问题PL的数组xL,YL及针对子问题PR的数组xR,YR,原问题规模为n,拆分的时间为O(n)
      • 8.改进算法时间复杂度
        • 递归过程:T(n),预处理:O(nlogn) W(n)=t(n)+O(nlogn) t(n)= 2T(n/2)+O(n) t(n)=O(1)n≤3,解得t(n)=O(nlogn)
    • 2.小结
      • 1.依据:W(n)=AW(n/b)+f(n)
      • 2.提高算法效率的方法
        • 1.减少子问题个数a：W(n)=O(n^logb^a)
        • 2.增加预处理,减少f(n)
• 4.典型的分治算法
  • 1.选最大与最小
    • 1.选择问题
      • 位置处在中间的元素,称为中位元素,n为奇数,中位数唯一,i=(n+1)/2,n为偶数,可指定i=n/2+1
    • 2.选最大
      • 1.算法：顺序比较,算法最坏情况下的时间W(n)=n-1
      • 2.伪码
    • 3.选最大最小
      • 1.通常算法
        • 1.顺序比较,先选最大max
        • 2.顺序比较,在剩余数组中选最小min,类似于选最大算法,但比较时保留较小的数
        • 3.时间复杂性：W(n)=n-1+n-2= 2n-3
      • 2.分组算法
        • 1.伪码
        • 2.最坏情况
      • 3.分治算法
        • 1.将数组L从中间划分为两个子数组L1和L2 2.递归地在L1中求最大maxl 和min1 3.递归地在L2中求最大max2 和min2 4.max←max{maxl ,max2} 5.min←min{minl ,min2}
        • 6.最坏情况
          • 假设n= 2^k,W(n)= 2W(n/2)+ 2 ,W(2)=1,解W(2^k)= 3*2^k-1– 2= 3n/2 - 2
      • 4.小结
        • 1.选最大：顺序比较,比较次数n-1
        • 2.选最大最小 • 选最大+选最小,比较次数 2n-3 • 分组： 比较次数┌3n/2┐-2 • 分治：n=2^k,比较次数 3n/2-2
  • 2.选第二大
    • 1.通常算法
      • 1．顺序比较找到最大max 2．从剩下n-1个数中找最大,就是第二大second
      • 3.时间复杂度：W(n)=n-1+n-2= 2n-3
    • 2.提高效率的途径
      • • 成为第二大数的条件：仅在与最大数的比较中被淘汰. • 要确定第二大数,必须知道最大数. • 在确定最大数的过程中记录下被最大数直接淘汰的元素. • 在上述范围（被最大数直接淘汰的数）内的最大数就是第二大数. • 设计思想： 用空间换时间
    • 3.锦标赛算法
      • 1.两两分组比较,大者进入下一轮,直到剩下1个元素max为止 2.在每次比较中淘汰较小元素,将被淘汰元素记录在淘汰它的元素的链表上 3.检查max的链表,从中找到最大元,即second
      • 4.时间复杂度
      • 5.伪码
  • 3.一般选择问题
    • 1.问题
      • 问题：选第k小. 输入：数组s,S 的长度n,正整数k,1≤k≤n. 输出：第k小的数
    • 2.应用
      • 1.管道位置
        • 某区域有n口油井,需要修建输油管道.根据设计要求,水平方向有一条主管道,每口油井修一条垂直方向的支管道通向主管道.如何选择主管道的位置,以使得支管道长度的总和最小？
      • 2.最优解:Y坐标的中位数
    • 3.简单的算法
      • 1.算法一：调用k次选最小算法,时间复杂度为O(kn)
      • 2.算法二：先排序,然后输出第k小的数,时间复杂度为O(nlogn)
    • 4.分治算法
      • 1.思想
        • 1.用某个元素m*作为标准将s划分成s1与s2,其中s1的元素小于m*,S2 的元素大于等于m*
        • 2.如果k≤|S1|,则在s1中找第k小. 如果k= |S1|+1,则m*是第k小 如果k> |S1|+1,则在s2中找第k-|S1|-1小
      • 2.m*的选择与划分过程
      • 3.归约为子问题
        • 将A,D两个区域比较大小之后,确定S1,S2区域,之后在两个子问题中递归
      • 4.伪码
    • 5.复杂度分析
      • 1.用m*划分
        • n= 5(2r +1),|A|= |D|= 2r,子问题规模至多： 2r+2r+3r+2= 7r+2
      • 2.子问题规模估计
      • 3.递推方程
        • 算法工作量W(n) 行2:O(n)//每5个数找中位数,构成M 行3:W(n/5)//m中找中位数m* 行4:O(n)// 用m*划分集合s 行8-9：W(7n/10)//递归 W(n)≤W(n/5)+W(7n/10)+O(n)
      • 4.递归树
      • 5.讨论
        • 1.分组时为什么5个元素一组？3个一组或 7个一组行不行？
        • 2.求m*的工作量与 |M|=n/t 相关,t 为每组元素数.t大,|M|小
        • 3.归约后子问题大小与分组元素数t有关.t大,子问题规模大
      • 6.3分组时的子问题规模
        • 1.n= 3(2r +1)r=(n/3 -1)/2=n/6 -1/2 子问题规模最多为 4r+1= 4n/6-1
        • 2.算法的时间复杂度满足方程W(n)=W(n/3)+W(4n/6)+cn,由递归树得W(n)=Θ(nlogn)
      • 7.关键
        • |M|与归约后子问题规模之和小于n,递归树每行的工作量构成公比小于1的等比级数,算法复杂度才是O(n)
  • 4.卷积及其应用
    • 1.向量计算
    • 2.卷积与多项式乘法
    • 3.应用：信号平滑处理
  • 5.卷积计算
  • 6.快速傅立叶变换:FFT算法
  • 7.平面点集的凸包
    • 1.问题
      • 1.给定大量离散点的集合Q,求一个最小的凸多边形,使得Q中的点在该多边形内或者边上
      • 2.应用背景: 图形处理中用于形状识别：字形识别、碰撞检测等
    • 2.分治算法
      • 1.以连接最大纵坐标点ymax和最小纵坐标点ymin的线段d={ymax,ymin}划分L为左点集Lleft和右点集Lright
      • 2.Deal(Lleft)；Deal(Lright)
    • 3.Deal(Lleft)
      • Deal( Lleft ) 1. 以d和距离d最远点P构成三角形，P加入凸包，另外两条边分别记作a和b 2. 检查Lleft中其他点是否在三角形内；在则从L中删除；否则根据在a或b边的外侧划分在两个子问题中 3. Deal(a) 4. Deal(b)
      • 考虑Lleft： 确定距d最远的点P在三角形内的点,删除； a外的点与a构成Lleft的子问题; b外的点与b构成Lleft的子问题
    • 4.算法分析
      • • 初始用d划分 O(n) • Deal 递归调用 W(n) – 找凸包顶点P O(n) – 根据点的位置划分子问题 O(n) • W(n) = W(n-1) + O(n) //极端情况,另外一边只有一个点 W(3) = O(1) 最坏情况为O(n^2) T(n) = O(n) + W(n) = O(n^2) • Graham扫描算法 O (nlogn)
• 5.动态规划的设计
  • 1.例子: 最短路径
    • 1.问题
      • 1.输入：起点集合{s1,S2,...,Sn},终点集合{T1,t2,...,tm},中间结点集,边集E,对于任意边e有长度 输出：一条从起点到终点的最短路
    • 2.蛮力算法
      • 1.考察每一条从某个起点到某个终点的路径,计算长度,从其中找出最短路径,在上述实例中,如果网络的层数为k,那么路径条数将接近于2^k
    • 3.动态规划
      • 1.思想
        • 1.多阶段决策过程.每步求解的问题是后面阶段求解问题的子问题.每步决策将依赖于以前步骤的决策结果
      • 2.子问题界定
        • 1.后边界不变,前边界前移si Aj Bk ClTm
      • 3.最短路长的依赖关系
      • 4.优化原则:最优子结构性质
        • 1.优化函数的特点：任何最短路的子路径相对于子问题始、终点最短
        • 2.优化原则：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列
    • 4.一个反例
      • 1.求总长模10的最小路径
      • 2.动态规划算法的解：下,上,上,上,最优解：下,下,下,下
      • 3.不满足优化原则,不能用动态规划
    • 5.总结
      • 1.求解过程是多阶段决策过程,每步处理一个子问题,可用于求解组合优化问题
      • 2.适用条件：问题要满足优化原则或最优子结构性质,即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列
  • 2.算法设计: 矩阵链
    • 1.设计要素
      • 1.问题建模,优化的目标函数是什么？约束条件是什么？ 2.如何划分子问题（边界）？ 3.问题的优化函数值与子问题的优化函数值存在着什么依赖关系？(递推方程) 4.是否满足优化原则？ 5.最小子问题怎样界定？其优化函数值,即初值等于什么？
    • 2.问题
      • 1.设A1,A2 ,… ,An为矩阵序列,Ai为Pi-1×Pi阶矩阵,i=1,2,… ,n.试确定矩阵的乘法顺序,使得元素相乘的总次数最少
      • 2.输入：向量P= <P0,P1,… ,Pn>,其中P0,P1,…,Pn为n个矩阵的行与列数 输出：矩阵链乘法加括号的位置
    • 3.基本运算次数
      • 1.矩阵A：i行j列,B:j行k列,以元素相乘作基本运算,计算AB的工作量
      • 2.AB:i行k列,计算每个元素需要做j次乘法,总计乘法次数为ijk
    • 4.蛮力算法
      • 1.加n个括号的方法有 种,是一个Catalan数,是指数级别
    • 5.动态规划
      • 1.子问题划分
      • 2.子问题的依赖关系
        • 1.最优划分最后一次相乘发生在矩阵k的位置,即Ai..j=Ai..k×Ak+1..j Ai..j最优运算次数依赖于Ai..k与Ak+1..j 的最优运算次数
      • 3.递推方程
    • 6.小结
      • 1.多阶段决策过程,每步处理一个子问题,界定子问题的边界
      • 2.列出优化函数的递推方程及初值
      • 3.问题要满足优化原则或最优子结构性质,即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列
  • 3.递归实现
    • 1.部分伪码
    • 2.算法分析
    • 3.子问题的产生
    • 4.子问题的计数
      • 边界不同的子问题：15 个 递归计算的子问题：81个
    • 5.结论
      • 1.与蛮力算法相比较,动态规划算法利用了子问题优化函数间的依赖关系,时间复杂度有所降低
      • 2.动态规划算法的递归实现效率不高,原因在于同一子问题多次重复出现,每次出现都需要重新计算一遍
      • 3.采取空间换时间策略,记录每个子问题首次计算结果,后面用到时就直接取值,每子问题只计算一次
  • 4.迭代实现
    • 1.关键
      • 1.每个子问题只计算一次
      • 2.迭代过程 – 从最小的子问题算起 – 考虑计算顺序,以保证后面用到的值前面已经计算好 – 存储结构保存计算结果——备忘录
      • 3.解的追踪 – 设计标记函数标记每步的决策 – 考虑根据标记函数追踪解的算法
    • 2.不同子问题
      • 长度1：只含1个矩阵,有n个子问题(不需要计算) 长度2：含2个矩阵,n-1个子问题 长度3：含3个矩阵,n-2个子问题 长度n-1：含n-1个矩阵,2个子问题 长度n：原始问题,只有1个
    • 3.迭代顺序
      • 长度为1：初值,m[i,i] = 0 长度为2：1..2,2..3,3..4,...,n-1..n 长度为3：1..3,2..4,3..5,...,n-2..n 长度为n-1：1..n-1,2..n 长度为n：1..n
    • 4.算法
    • 5.时间复杂度
      • 1.根据伪码：行 2,3,7 都是O(n),循环执行O(n^3)次,内部为O(1),W(n)=O(n^3)
      • 2.根据备忘录：估计每项工作量,求和.子问题有O(n^2)个,确定每个子问题的 最少乘法次数需要对不同划分位置比较,需要O(n)时间.W(n)=O(n^3)
      • 3.追踪解工作量O(n),总工作量O(n^3)
    • 6.实例
    • 7.两种实现的比较
      • 递归实现：时间复杂性高,空间较小 迭代实现：时间复杂性低,空间消耗多
      • 1.原因：递归实现子问题多次重复计算,子问题计算次数呈指数增长.迭代实现每个子问题只计算一次
      • 2.动态规划时间复杂度：备忘录各项计算量之和 + 追踪解工作量 通常追踪工作量不超过计算工作量 ,是问题规模的多项式函数
    • 8.要素
      • • 划分子问题,确定子问题边界,将问题求解转变成多步判断的过程. • 定义优化函数,以该函数极大(或极小)值作为依据,确定是否满足优化原则. • 列优化函数的递推方程和边界条件 • 自底向上计算,设计备忘录(表格) • 考虑是否需要设立标记函数 • 用递推方程或备忘录估计时间复杂度
  • 5.投资问题
    • 1.建模
      • 1.问题：m元钱,n项投资,fi(x): 将x元投入第i个项目的效益.求使得总效益最大的投资方案
      • 2.建模： 问题的解是向量 <x1,x2,...,xn>,xi是投给项目i的钱数,i=1,2,...,n. 目标函数max{f1(x1)+f2(x2)+…+fn(xn)} 约束条件x1+x2+…+xn=m,xi∈N
    • 2.子问题界定
      • 子问题界定：由参数k和x界定 k：考虑对项目1,2,...,k的投资 x：投资总钱数不超过x
    • 3.与矩阵链参数区别
      • 1.这两个参数为不同类型的参数,矩阵链为相同类型参数,类型不同时,考虑子问题计算顺序
    • 4.子问题计算顺序
      • 1.先计算k,再计算x,k=1,2,...,n,对于给定的k,x=1,2,...,m
    • 5.递推方程
      • 1.Fk(x):x元钱投给前k个项目最大效益
      • 2.多步判断：若知道p元钱(p≤x)投给前k-1个项目的最大效益Fk-1(p),确定x元钱投给前k个项目的方案
      • 3.
    • 6.时间复杂度
      • 1.备忘录表中有m行n列,共计mn项,xk有x+1种可能的取值,计算Fk(x)项(2≤k≤n,1≤x≤m)需要：x+1次加法,x次比较
      • 2.对备忘录中所有的项求和
    • 7.实例
  • 6.背包问题
    • 1.背包问题
      • 一个旅行者随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为Wi,vi.如果背包的最大重量限制是b,每种物品可以放多个.怎样选择放入背包的物品以使得背包的价值最大?不妨设上述Wi,vi,b都是正整数
    • 2.建模
      • 1.解是<x1,x2,...,xn>, 其中xi是装入背包的第i种物品个数
      • 线性规划问题: 由线性条件约束的线性函数取最大或最小的问题 整数规划问题: 线性规划问题的变量xi都是非负整数
    • 3.子问题界定
      • k：考虑对物品1,2,...,k的选择 y：背包总重量不超过y
    • 4.子问题计算顺序
      • k=1,2,...,n,对于给定的k,y=1,2,...,b
    • 5.递推方程
      • 1.Fk(y): 装前k种物品,总重不超过y,背包达到的最大价值
    • 6.类似投资问题,两者区别
      • 投资问题: 对项目投入的钱不同,得到的收益也不同,是一个函数,而背包问题的价值是确定的,是个常数
    • 7.标记函数
      • 1.ik(y): 装前k种物品,总重不超y,背包达到最大价值时装入物品的最大标号
    • 8.实例
    • 9.追踪算法
    • 10.时间复杂度
      • 1.备忘录需计算nb项,每项常数时间,计算时间为O(nb)
      • 2.伪多项式时间算法：时间为参数b和n的多项式,不是输入规模的多项式. 参数b是整数,表达b需要logb位,输入规模是logb
    • 11.推广
      • 1.物品数受限背包：第i种物品最多用ni个
      • 2.0-1背包问题：xi= 0,1,i=1,2,… ,n
      • 3.多背包问题：m个背包,背包j装入最大重量bj ,j=1,2,… ,m.在满足所有背包重量约束条件下使装入物品价值最大
      • 4.二维背包问题：每件物品有重量Wi和体积ti,i=1,2,… ,n,背包总重不超过b,体积不超过V,如何选择物品以得到最大价值.
  • 7.最长公共子序列LCS
    • 1.子序列
      • 1.若存在x的元素构成的严格递增序列,并不一定是连续序列,使得
    • 2.蛮力算法
      • 1.不妨设m≤n,|X|=m,|Y|=n算法：依次检查X的每个子序列在Y中是否出现
      • 2.时间复杂度：每个子序列O(n)时间X有 2^m 个子序列,最坏情况下时间复杂度：O(n2^m)
    • 3.子问题界定
      • 1.参数i和j界定子问题 X的终止位置是i,y的终止位置是j,xi=<x1,x2,…,xi>,Yj=<y1,y2,…,yj>
    • 4.依赖关系
      • 1.设x=<x1,x2,…,xm>,y=<y1,y2,…,yn>, Z=<z1,z2,…,zk>为X和Y的LCS,那么
    • 5.递推方程
      • 令x与y的子序列Xi= <x1,x2,… ,xi>, Yj= <y1,y2,… ,yj> C[i,j]：xi与yj的LCS的长度
    • 6.标记函数
      • 标记函数：B[i,j],值为↖、←、↑ C[i,j]=C[i-1,j-1]+1: ↖ C[i,j]=C[i,j-1]: ← C[i,j]=C[i-1,j]:↑ 
    • 7.伪码
    • 8.追踪解
      • 算法 Structure Sequence(B, i, j) 输入：B[i, j] 输出：X与Y的最长公共子序列 1. if i=0 or j=0 then return //序列为空 2. if B[i, j] =“↖” 3. then 输出X[i] //只有斜向上的方向才输出字符,其他方向只移动 4. Structure Sequence(B, i－1, j－1) 5. else if B[i,j]=“↑” 6. then Structure Sequence (B, i－1, j) 7. else Structure Sequence (B, i, j－1)
    • 9.标记函数的实例
    • 10.时空复杂度
      • 计算优化函数和标记函数： 赋初值，为O(m)+O(n) 计算优化、标记函数迭代Θ(mn)次， 循环体内常数次运算，时间为Θ(mn) 构造解： 每步缩小 X 或Y的长度，时间Θ(m+n)
      • 算法时间复杂度：Θ(mn) 空间复杂度：Θ(mn)
• 6.动态规划的应用
  • 0.设计要点
    • 1.引入参数来界定子问题的边界.注意子问题的重叠程度
    • 2.给出带边界参数的优化函数定义与优化函数的递推关系,找到递推关系的初值
    • 3.判断该优化问题是否满足优化原则
    • 4.考虑是否需要标记函数
    • 5.采用自底向上的实现技术,从最小的子问题开始迭代计算,计算中用备忘录保留优化函数和标记函数的值
    • 6.动态规划算法的时间复杂度是对所有子问题(备忘录)的计算工作量求和(可能需要追踪解的工作量)
    • 7.动态规划算法一般使用较多的存储空间,这往往成为限制动态规划算法使用的瓶颈因素
  • 1.图像压缩
  • 2.最大子段和
    • 0.问题
      • 给定n个数(可以为负数)的序列,求它的最大子段和
    • 1.几种算法
      • 1.对所有的(i,j)对,顺序求和ai+...+Aj并比较出最大的和
      • 2.分治策略: 将数组分成左右两半,分别计算左边的最大和、右边的最大和、跨边的最大和,然后比较其中最大者
      • 3.动态规划
    • 2.子问题界定
      • 前边界为1,后边界i,C[i]是A[1..i]中必须包含元素A[i]的向前连续延伸的最大子段和
    • 3.递推方程
      • C[i]=max{C[i－1]+A[i],A[i]},若A[1]>0,c[1]=A[1],否则C[1]=0 ,OPT(A)=max{C[i]}
    • 4.伪码
      • 算法 MaxSum (A, n) 输入：数组A 输出：最大子段和sum, 子段最后位置c 1. sum←0 2. b←0 3. for i ←1 to n do //子问题后边界i 4. if b > 0 //当前和为正数时,才加上后一项,为负数时,直接等于后一项 5. then b ← b + A[i] 6. else b ← A[i] 7. if b > sum //找到更大的和,才更换c的位置 8. then sum ← b 9. c ← i 10. return sum , c
    • 5.复杂度
      • 时间复杂度：O(n),空间复杂度：O(n)
  • 3.最优二叉搜索树
    • 1.概念
      • 1.二叉搜索树
        • 1.集合S为排序的n个元素,x1<x2<…<xn,将这些元素存储在一棵二叉树的结点上,以查找x是否在这些数中.如果x不在,确定x在那个空隙（方结点）
      • 2.存取概率分布
        • 1.给定序列s= <x1,x2,…,xn>,x在xi的概率为bi,x在(xi,xi+1)的概率为ai,S 的存取概率分布如下：P= <A0,b1,a1,b2,a2,… ,bn,an>
      • 3.平均比较次数
        • 结点xi在T中的深度是d(xi),i=1,2,…,n, 空隙Lj 的深度为d(Lj),j=0,1,…,n,平均比较次数为：
    • 2.问题
      • 1.给定数据集S= <x1,x2 ,…,xn>,及S的存取概率分布如下：P= <A0 ,b1,a1,b2 ,a2 ,… ,bn,an>,求一棵最优的( 即平均比较次数最少的 )二分检索树
    • 3.子问题划分
      • 子问题边界为(i,j) 数据集：s[i,j]= <xi,xi+1,… ,xj > 存取概率分布：P[i,j]=<ai－1,bi,ai,bi+1,… ,bj ,aj>
    • 4.子问题归约
      • 以xk作为根归结为子问题：S[i,k−1],P[i,k−1]s[k+1,j],P[k+1,j]
    • 5.子问题的概率之和
      • 是P[i,j]中所有概率(数据与空隙)之和
    • 6.递推方程
      • 1.设m[i,j]是相对于输入s[i,j]和P[i,j]的最优二叉搜索树的平均比较次数
    • 7.实例
    • 8.复杂性估计
      • i,j的所有组合O(n^2)种,每种要对不同的k进行计算,k=O(n),每次计算为常数时间 时间复杂性：t(n)=O(n^3)空间复杂度：s(n)=O(n^2)
  • 4.RNA二级结构预测
  • 5.序列对比
    • 1.问题
      • 为确定两个序列之间的相似性或同源性,将它们按照一定的规律排列,进行比对
    • 2.应用
      • 生物信息学中用于研究同源性,如蛋白质序列或dNA序列.在比对中,错配与突变相对应,空位与插入或缺失相对应.计算语言学中用于语言进化或文本相似性的研究
    • 3..编辑距离
      • 给定两个序列s1和s2,通过一系列字符编辑（插入、删除、替换）等操作,将S1转变成s2.完成这种转换所需要的最少的编辑操作个数称为s1和S2 的编辑距离
    • 4.子问题界定和归约
      • 1.S1[1..n]和s2 [1..m]表示两个序列 子问题：S1[1..i]和s2[1..j],边界(i,j) (从后向前不断处理)
    • 5.递推方程
      • C[i,j]：S1[1..i]和S2[1..j]的编辑距离 4种处理方式都能完成操作,取最小的
    • 6.复杂度分析
      • 子问题由i,j界定,有O(mn)个子问题 • 每个子问题的计算为常数时间 • 算法的时间复杂度是O(nm)
• 7.贪心法的设计
  • 1.活动选择
    • 1.问题
      • 输入：S={1,2,… ,n}为n项活动的集合,si,fi分别为活动i的开始和结束时间. 活动i与j相容 ⇔si≥fj 或sj ≥fi.求：最大的两两相容的活动集A
    • 2.贪心算法
      • 0.挑选过程是多步判断,每步依据某种“短视”的策略进行活动选择,选择时注意满足相容性条件
      • 1.开始时间早的优先,排序使s1≤s2≤…≤sn,从前向后挑选
      • 2.占用时间少的优先,排序使得f1－s1≤f2－s2≤…≤fn－sn,从前向后挑选
      • 3.结束早的优先,排序使f1≤f2≤…≤fn,从前向后挑选
    • 3.策略3伪码
      • 算法 Greedy Select 输入：活动集 S，si , fi, i = 1, 2, … , n， f1 ≤ … ≤ fn 输出：A ⊆ S，选中的活动子集 1. n ← length[S] 2. A ← {1} 3. j ← 1 4. for i ← 2 to n do 5. if si ≥ fj 6. then A ← A∪{ i } 7. j ← i 8. return A 完成时间 t = max { fk: k∈A }
      • 算法1,2得不到最优解
    • 4.贪心算法特点
      • (1)贪心法适用于组合优化问题. (2)求解过程是多步判断过程,最终的判断序列对应于问题的最优解. (3)依据某种“短视的”贪心选择性质判断,性质好坏决定算法的成败. (4)贪心法必须进行正确性证明. (5)证明贪心法不正确的技巧：举反例.贪心法的优势：算法简单,时间和空间复杂性低
  • 2.正确性证明
    • 1.第一数学归纳法
      • 1.适合证明涉及自然数的命题P(n)
      • 归纳基础：证明P(1)为真(或P(0)为真). 归纳步骤: 若对所有n有P(n)为真,证明P(n+1)为真
    • 2.第二数学归纳法
      • 1.适合证明涉及自然数的命题P(n)
      • 归纳基础：证明P(1)为真(或P(0)为真). 归纳步骤：若对所有小于n的k有P(k)真,证明P(n)为真
    • 3.算法正确性归纳证明
      • 1.叙述一个有关自然数n的命题,该命题断定该贪心策略的执行最终将导致最优解.其中自然数n可以代表算法步数或者问题规模
      • 2.证明命题对所有的自然数为真.归纳基础(从最小实例规模开始) 归纳步骤(第一或第二数学归纳法)
    • 4.活动选择算法的命题
      • 算法select执行到第k步,选择k项活动i1=1,i2 ,… ,ik,则存在最优解A包含活动i1=1,i2 ,…,ik.根据上述命题：对于任何k,算法前k步的选择都将导致最优解,至多到第n步将得到问题实例的最优解
    • 5.归纳基础
      • 令s={1,2,…,n}是活动集,且f1≤…≤fn,归纳基础:k=1,证明存在最优解包含活动1 证: 任取最优解A,A中活动按截止时间递增排列.如果A的第一个活动为j,j ≠1,用1替换A的活动j得到解A',即A'=(A−{j})∪{1},由于f1≤fj ,A' 也是最优解,且含有1
    • 6.归纳步骤
      • 1.假设命题对k为真,证明对k+1也为真
      • 2.证:算法执行到第k步,选择了活动i1=1,i2,…,ik,根据归纳假设存在最优解A包含i1=1,i2,…,ik,A中剩下活动选自集合S',S'={i|i∈S,si≥fk}A={i1,i2,… ,ik} ∪ B
      • 3.B是s'的最优解.（若不然,S' 的最优解为B*,B*的活动比 B多,那么B*∪{1,i2,… ,ik} 是s的最优解,且比A的活动多,与A的最优性矛盾.）
      • 4.将S'看成子问题,根据归纳基础,存在s'的最优解B'有S'中的第一个活动ik+1,且 |B'|= |B|,于是{i1,i2,...,ik} ∪ B'={i1,i2,...,ik,ik+1} ∪( B'−{ik+1})也是原问题的最优解
  • 3.最优装载问题
    • 1.问题
      • n个集装箱1,2,… ,n装上轮船,集装箱i的重量Wi,轮船装载重量限制为C,无体积限制.问如何装使得上船的集装箱最多？不妨设每个箱子的重量Wi≤C,该问题是0-1背包问题的子问题.集装箱相当于物品,物品重量是Wi,价值vi都等于1,轮船载重限制c相当于背包重量限制b
    • 2.建模
      • 设 <x1,x2,...,xn> 表示解向量,xi= 0,1, xi=1当且仅当第i个集装箱装上船
    • 3.算法设计
      • 1.贪心策略：轻者优先
      • 2.将集装箱排序,使得w1≤W2 ≤...≤Wn,按照标号从小到大装箱,直到装入 下一个箱子将使得集装箱总重超过轮船装载重量限制,则停止
    • 4.正确性证明思路
    • 5.小结
      • 1.装载问题是0-1背包的子问题(每件物品重量为1),NP难的问题存在多项式时间可解的子问题
      • 2.贪心法证明：对规模归纳
  • 4.最小延迟调度
    • 1.问题
      • 客户集合A,∀i∈A,ti为服务时间,di为要求完成时间,ti,di为正整数.一个调度f:A→N,f(i)为客户i的开始时间.求最大延迟达到最小的调度,即求f使得
    • 1.贪心策略
      • 1.按照ti从小到大安排,对某些实例得不到最优解
      • 2.按照di−ti从小到大安排,对某些实例得不到最优解
      • 3.按照di从小到大安排,按完成时间从早到晚安排任务,没有空闲
        • 算法 Schedule 输入：A, T, D 输出：f 1. 排序 A 使得 d1 ≤ d2 ≤ … ≤ dn 2. f(1) ← 0 //从0时刻起 3. i ← 2 4. while i ≤ n do 5. f(i) ← f(i−1) + ti−1 //没有空闲 6. i ← i + 1
    • 2.交换论证：正确性证明
      • 1.证明思路
        • • 分析一般最优解与算法解的区别（成分,排列顺序不同） • 设计一种转换操作（替换成分或交换次序）,可以在有限步将任意一个普通最优解逐步转换成算法的解 • 上述每步转换都不降低解的最优性质
      • 2.贪心算法的解的性质
        • 没有空闲时间,没有逆序.逆序(i,j):f(i)<f(j)且di>dj
    • 3.引理
      • 1.所有没有逆序、没有空闲时间的调度具有相同的最大延迟
      • 2.证: 设f没有逆序,在f中具有相同完成时间d的客户i1,i2,… ,ik连续安排,其开始时刻为t0,完成这些任务的时刻是t,最大延迟为最后任务延迟t−d,与i1,i2,… ,ik的排列次序无关
    • 4.证明要点
      • 0.从一个没有空闲的最优解出发,逐步转变成没有逆序的解.根据引理1,这个解和算法解具有相同的最大延迟
      • 1.如果一个最优调度存在逆序,那么存在i<n使得(i,i+1)构成一个逆序,称为相邻的逆序
      • 2.交换相邻逆序i和j,得到的解仍旧最优
      • 3.每次交换后逆序数减1,至多经过n(n−1)/2 次交换得到一个没有逆序的最优调度—等价于算法的解
    • 5.交换相邻逆序仍旧最优
      • 0.设f1是一个任意最优解,存在相邻逆序(i,j).交换i和j的顺序,得到解f2.那么f2的最大延迟不超过f1的最大延迟
      • (1)交换i,j与其他客户延迟时间无关 (2)交换后不增加j的延迟,但可能增加i的延迟 (3)i在f2的延迟小于j在f1的延迟 ,因此小于f1的最大延迟 r
    • 6.小结
      • 0.贪心法正确性证明方法：交换论证
      • 1.分析算法解与一般最优解的区别,找到把一般解改造成算法解的一系列操作(替换成份、交换次序)
      • 2.证明操作步数有限
      • 3.证明每步操作后的得到解仍旧保持最优
  • 5.得不到最优解 的处理方法
    • 1.处理办法
      • 1.输入参数分析
        • 考虑输入参数在什么取值范围内使用贪心法可以得到最优解
      • 2.误差分析
        • 估计贪心法——近似算法所得到的解与最优解的误差（对所有的输入实例在最坏情况下误差的上界）
    • 2.找零钱
      • 1.问题
        • 设有n种零钱,重量分别为w1,w2,...,wn,价值分别为v1=1,v2,...,vn.需要付的总钱数是y.不妨设币值和钱数都为正整数.问：如何付钱使得所付钱的总重最轻?
      • 2.建模
        • 令选用第i种硬币的数目是xi,i=1,2,… ,n
      • 3.动态规划
        • 设Fk(y)表示用前k种零钱,总钱数为y的最小重量
      • 4.贪心法
        • 1.单位价值重量轻的货币优先
        • 2.使用前k种零钱,总钱数为y贪心法的总重为gk(y)
        • 3.n=1,2贪心法是最优解,n=1只有一种零钱,F1(y)=g1(y),n= 2,x2越大,得到解越好
      • 5.判别条件
        • 0.对每个正整数k,假设对所有非负整数y有Gk(y)=fk(y),且存在P和 δ 满足 vk+1=Pvk－δ,其中 0 ≤ δ <vk,vk≤vk+1,p为正整数,则下面的命题等价：
      • 6.几点说明
        • 1.根据条件(1)与(3)的等价性,可以对k= 3,4,...,n,依次利用条件(3)对贪心法是否得到最优解做出判别
        • 2.条件(3)验证1次需O(k)时间,k=O(n),整个验证时间O(n^2)
        • 3.条件(2)是条件(1)在y=Pvk时的特殊情况.若条件(1)成立,显然有条件(2)成立.反之,若条件(2)不成立,则条件(1)不成立,钱数y=Pvk恰好提供了一个贪心法不正确的反例
      • 7.验证实例
• 8.重要的贪心算法
  • 1.最优前缀码
    • 1.二元前缀码
      • 用0-1字符串作为代码表示字符,要求任何字符的代码都不能作为其它字符代码的前缀
    • 2.前缀码的二叉树表示
    • 3.平均传输位数
      • 0.
      • 1.问题: 给定字符集C={x1,x2,...,xn}和每个字符的频率f(xi),i=1,2,...,n.求关于C的一个最优前缀码(平均传输位数最小)
    • 4.哈夫曼树伪码
      • 算法 Huffman(C ) 输入：C ={x1, x2,…, xn}, f(xi), i=1,2,…,n. 输出：Q / /队列 1. n←|C | 2. Q←C //频率递增队列Q 3. for i←1 to n−1 do 4. z←Allocate-Node() //生成结点 z 5. z.left←Q中最小元 //最小作z左儿子 6. z.right←Q中最小元 //最小作z右儿子 7. f(z)←f(x)+f(y) 8. Insert(Q,z) // 将 z 插入Q 9. return Q
    • 5.最优前缀码引理
      • 1.C是字符集,∀c∈C,f(c)为频率,x,y∈C,f(x),f(y)频率最小,那么存在最优二元缀码使得x,y码字等长且仅在最后一位不同
      • 2.设T是二元前缀码的二叉树,∀x,y∈T,x,y是树叶兄弟,z 是x,y的父亲,令T'=T−{x,y} 且令z的频率f(z)=f(x)+f(y)T'是对应二元前缀码C'=(C−{x,y})∪{z}的二叉树,那么B(T)=B(T')+f(x)+f(y)
  • 2.哈夫曼算法
    • 1.正确性证明
    • 2.应用:文件归并
      • 1.问题
        • 给定一组不同长度的排好序文件构成的集合s={f1, … , fn},其中 fi表示第i个文件含有的项数. 使用二分归并将这些文件归并成一个有序文件
      • 2.归并过程对应于二叉树
        • 文件为树叶. fi与 fj 归并的文件是它们的父结点
  • 3.最小生成树
    • 1.定义
      • 无向连通带权图G=(V,E,W),其中W(e)∈W是边e的权.G的一棵生成树T是包含了G的所有顶点的树, 树中各边的权之和W(T)称为树的权,具有最小权的生成树称为G的最小生成树
    • 2.性质
      • (1)T是G的生成树当且仅当T无圈且有n－1条边. (2)如果T是G的生成树,e∉T,那么T∪{e}含有一个圈C(回路) (3)去掉圈C的任意一条边,就得到G的另外一棵生成树T'
    • 3.贪心法
      • Prim 算法,Kruskal 算法
  • 4.Prim算法
    • 1.设计思想
      • 初始s={1},选择连接s与 V−S 集合的最短边e={i,j},其中 i∈S,j∈V−S. 将e加入树T,j 加入s. 继续执行上述过程,直到s=V 为止
    • 2.伪码
      • 算法 Prim ( G, E, W ) 1．S ← { 1 } 2．while V − S ≠ ∅ do 3． 从V−S中选择 j 使得 j 到 S中顶点的边权最小 4． S ← S ∪{ j }
    • 3.正确性证明
    • 4.时间复杂度
      • 算法步骤执行O(n)次,每次执行O(n)时间,找连接s与V-S 的最短边 算法时间：T(n)=O(n^2),不依赖于|E|,适合边稠密的图
  • 5.Kruskal算法
    • 1.设计思想
      • (1)按照长度从小到大对边排序. (2)依次考察当前最短边e,如果e与T的边不构成回路,则把e加入树T,否则跳过e. 直到选择了n-1条边为止
    • 2.伪码
      • 算法 Kruskal 输入：连通图G // 顶点数n，边数m 输出：G 的最小生成树 1. 权从小到大排序E的边, E={e1,e2,…,em} 2. T ← ∅ 3．repeat 4. e ← E中的最短边 5． if e 的两端点不在同一连通分支 6. then T ←T∪{e} 7. E ← E－{e} 8. until T 包含了n－1条边
    • 3.正确性证明
    • 4.时间复杂度
      • 1.采用堆存放边集合,时间复杂度O(|E|log|E|),适合边稀疏而顶点较多的图
    • 5.应用: 数据分组
      • 1.问题
        • 一组数据(照片,文件,生物标本)要把它们按照相关性进行分类. 用相似度函数或“距离”来描述个体之间的差距. 如果分成5类,使得每类内部的个体尽可能相近,不同类之间的个体尽可能地“远离”. 如何划分
      • 2.单链聚类
        • 类似于Kruskal算法 (1) 按照边长从小到大对边排序 (2) 依次考察当前最短边 e ，如果 e 与 已经选中的边不构成回路，则把 e 加入集合，否则跳过 e. 计数图的连通分支个数. (3) 直到保留了k个连通分支为止
  • 6.单源最短路径
    • 1.问题
      • 给定带权有向网络g=(V,E,W),每条边e=<i,j>的权W(e)为非负实数,表示从i到j的距离. 源点s∈V. 求: 从s出发到达其它结点的最短路径
    • 2.有关概念
      • 1.x∈S ⇔x∈V 且从s到x的最短路径已经找到,初始：S={s} ,S= V 时算法结束
      • 2.从s到u相对于S的最短路径：从s到u且仅经过s中顶点的最短路径
      • dist [u]：从s到u相对S最短路径的长度 short [u]：从s到u的最短路径的长度 dist [u]≥short[u]
    • 3.设计思想
      • 输入：有向图 G = (V, E, W ), V = { 1, 2, … , n }，s = 1 输出：从s到每个顶点的最短路径 1. 初始 S={1} 2. 对于i∈V− S，计算1到 i 的相对 S 的最短路，长度 dist [i] 3. 选择V− S中 dist 值最小的 j，将j加入 S，修改V− S中顶点的dist 值. 4. 继续上述过程，直到 S=V为止.
    • 4.伪码
      • 算法 Dijkstra 1. S←{ s } 2. dist [s]←0 3. for i∈V −{ s } do 4. dist[i]←w(s,i) //s到i没边, w(s,i)=∞ 5. while V− S≠∅ do 6. 从V− S取相对S的最短路径顶点 j 7. S←S∪{ j} 8. for i∈V−S do 9. if dist [j]+w(j,i)<dist [i] //更新dist值 10. then dist [i]←dist [j]+w(j,i)
    • 5.正确性证明
    • 6.时间复杂度
      • 时间复杂度：O(nm) 算法进行n-1步,每步挑选1个具有最小dist函数值的结点进入S,需要O(m)时间 选用基于堆实现的优先队列的数据结构,可以将算法时间复杂度降到O(mlogn)
• 9.回溯算法的设计
  • 1.几个例子
    • 1.4后问题
      • 1.问题
        • 1.在 4 × 4 的方格棋盘上放置4个皇后,使得没有两个皇后在同一行、同一列、也不在同一条45度的斜线上.问有多少种可能的布局
        • 2.解是 4 维向量 <x1,x2,x3,x4 >
      • 2.搜索空间
        • 4叉树,每个结点有4个儿子,分别代表选择1,2,3,4列位置,第i层选择解向量中第i个分量的值最深层的树叶是解按深度优先次序遍历树,找到所有解
    • 2.0-1背包问题
      • 1.问题
        • 有n种物品,每种物品只有1个. 第i种物品价值为vi, 重量为Wi,i=1,2,…,n. 问如何选择放入背包的物品,使得总重量不超过 B, 而价值达到最大
      • 2.搜索空间
        • 0-1取值的二叉树, 称为子集树,有2^n片树叶
    • 3.货郎问题
      • 1.问题
        • 有n个城市,已知任两个城市之间的距离,求一条每个城市恰好经过一次的回路,使得总长度最小
      • 2.搜索空间
        • 排列树, 有(n-1)!片树叶
  • 2.设计思想
    • 1.问题分析
    • 2.基本思想
      • (1)适用：求解搜索问题和优化问题. (2)搜索空间：树,结点对应部分解向量,可行解在树叶上. (3)搜索过程：采用系统的方法隐含遍历搜索树.系统的方法: 深度/宽度优先,隐含:并不是真的将每棵树都走完,不满足要求的会直接回溯 (4)搜索策略：深度优先,宽度优先,函数优先,宽深结合等 (5)结点分支判定条件：满足约束条件---分支扩张解向量,不满足约束条件,回溯到该结点的父结点. (6)结点状态：动态生成白结点(尚未访问),灰结点(正在访问该结点为根的子树),黑结点(该结点为根的子树遍历完成) (7)存储：当前路径
    • 3.适用条件
      • 1.在结点<x1,x2,...,xk>处P(x1,x2, …,xk)为真⇔ 向量<x1,x2, …,xk> 满足某个性质
      • 2.多米诺性质：P(x1,x2,…,xk+1)→P(x1,x2,…,xk)0<k<n , ¬P(x1,x2,…,xk)→¬P(x1,x2,…,xk+1)0<k<n, k维向量不满足约束条件,扩张向量到k+1维仍旧不满足,可以回溯
    • 4.一个反例
      • 例 求不等式的整数解 5x1+4x2−x3≤10,1≤xk≤3,k=1,2,3 , P(x1, …,xk): 将x1,x2, … ,xk代入原不等式的相应部分,部分和小于等于10 不满足多米诺性质： 5x1+ 4x2 −x3 ≤10 ⇏ 5x1+ 4x2 ≤10 变换使得问题满足多米诺性质：令x3=3−x3', 5x1+ 4x2 +x3'≤13,1≤x1,x2≤3, 0≤x3'≤2
    • 5.设计步骤
      • (1)定义解向量和每个分量的取值范围,解向量为 <x1,x2, …,xn>,确定xi的取值集合为xi,i=1,2,…,n (2)在<x1,x2,…,xk-1>确定如何计算xk取值集合Sk,sk ⊆xk (3)确定结点儿子的排列规则 (4)判断是否满足多米诺性质 (5)确定每个结点分支的约束条件 (6)确定搜索策略: 深度优先,宽度优先等 (7)确定存储搜索路径的数据结构
  • 3.实现及实例
    • 1.递归实现
      • 算法 ReBack (k) //在第k层做了什么事情 1. if k>n then <x1,x2,…,xn>是解 2. else while Sk ≠ ∅ do //还未满足题目要求,对第k个分量进行赋值,判断可取值的集合是否为空 3. xk ← Sk 中最小值 4. Sk ← Sk – { xk } //赋值结束后删除此值 5. 计算 Sk+1 6. ReBack (k+1) 算法 ReBacktrack (n) 输入：n 输出：所有的解 1. for k←1 to n 计算 Xk且Sk←Xk 2. ReBack (1)
    • 2.迭代实现
      • 迭代算法 Backtrack 输入：n 输出：所有的解 1. 对于 i =1, 2, … , n 确定Xi //确定初始取值 2. k ← 1 3. 计算 Sk //计算当前的取值范围 4. while Sk ≠ ∅ do //满足约束分支搜索 5. xk←Sk中最小值; Sk←Sk –{xk} 6. if k < n then 7. k ← k+1; 计算 Sk 8. else < x1, x2, … , xn>是解 9. if k >1 then k ← k-1； goto 4 //取值范围为空,但k不为0时回溯
    • 3.装载问题
      • 1.问题
        • 有n个集装箱,需要装上两艘载重分别为c1和c2的轮船.Wi为第i个集装箱的重量,且W1+w2+...+wn≤c1+c2 问：是否存在一种合理的装载方案把这n个集装箱装上船
      • 2.思路
        • 令第一艘船的装入量为W1, 1. 用回溯算法求使得c1−W1达到最小的装载方案. 2. 若满足w1+w2+...+wn−W1≤c2,则回答“Yes”,否则回答“No”
      • 3.伪码
        • 算法 Loading (W, c1), 1. Sort(W); 2. B←c1; best←c1; i←1; //B为当前空隙,best最小空隙 3. while i≤n do 4. if 装入 i后重量不超过 c1 5. then B←B−wi; x[i]←1; i←i+1; 6. else x[i]←0; i←i+1; 7. if B<best then 记录解；best←B; 8. Backtrack(i)； //回溯 9. if i=1 then return 最优解 10. else goto 3 . 子过程 Backtrack 算法 Backtrack(i) 1. while i >1 and x[ i ] = 0 do 2. i←i−1; //沿右分支一直回溯发现左分支边，或到根为止 3. if x[i]=1 4. then x[i]←0; 5. B←B+wi; 6. i←i+1.
      • 4.时间复杂性
        • W(n)=O(2^n)
  • 4.图的着色
    • 1.问题
      • 输入：无向连通图g和m种颜色的集合用这些颜色给图的顶点着色,每个顶点一种颜色. 要求是：G的每条边的两个顶点着不同颜色. 输出：所有可能的着色方案. 如果不存在着色方案,回答“No”
    • 2.解向量
      • G=(V,E),V={1,2, ... ,n},颜色编号：1, 2, … ,m 解向量：<x1,x2, ...,xn>,x1,x2, …,xn∈{1,2, ..,m} 结点的部分向量 <x1,x2 , … ,xk>x1,x2, …,xk,1≤k≤n,表示只给顶点1,2,...,k着色的部分方案
    • 3.算法设计
      • 搜索树：m叉树 约束条件：在结点<x1,x2, ... ,xk>处,顶点k+1的邻接表中结点已用过的颜色不能再用,如果邻接表中结点已用过m种颜色,则结点k+1没法着色,从该结点回溯到其父结点. 满足多米诺性质 搜索策略：深度优先
    • 4.时间复杂度
      • O(nm^n)
    • 5.改进途径
      • 根据对称性,只需搜索1/3 的解空间. 当1和2确定, 即<1,2> 以后,只有1解, 在 <1,3> 为根的子树中也只有1个解. 由于3个子树的对称性,总共6个解 在取定<1,2>后,不可扩张成<1,2,3>, 因为7和1,2,3都相邻. 7没法着色. 可以从打叉的结点回溯,而不必搜索其子树
    • 6.应用
      • 1.会场分配问题： 有n项活动需要安排, 对于活动 i,j,如果 i,j时间冲突,就说i与j不相容. 如何分配这些活动,使得每个会场的活动相容且占用会场数最少
      • 2.建模： 活动作为图的顶点,如果i,j不相容,则在i与j之间加一条边,说明两个活动不能安排到同一个会场,会场标号作为颜色标号.求图的一种着色方案,使得使用的颜色数最少
  • 5.搜索树结点数的估计
    • 1.Monte Carlo方法
      • 1. 从根开始,随机选择一条路经,直到不能分支为止, 即从x1,x2 , …, 依次 对xi赋值,每个xi的值是从当时的si中随机选取,直到向量不能扩张为止. 2. 假定搜索树的其他 |si| −1个分支与以上随机选出的路径一样,计数搜索树的点数. 3. 重复步骤1和 2,将结点数进行概率平均.
    • 2.伪码
      • Monte Carlo 输入：n 为皇后数，t 为抽样次数 输出：sum, 即t 次抽样路长平均值 1．sum←0 2．for i ←1 to t do // 取样次数 t 3. m←Estimate(n) // m为结点数,Estimate(n)为一次抽样结果 4. sum ← sum + m 5. sum ← sum / t 一次抽样 m为本次取样得到的树结点总数 k 为层数 r2为上层结点数 r1为本层结点数 r1 = r2⋅ 分支数 n 为树的层数 从树根向下计算,随机选择,直到树叶 算法Estimate(n) 1. m←1; r2←1; k←1 // m 为结点总数 2. while k≤n do 3. if Sk=∅ then return m 不能分支 4. r1←|Sk|*r2 // r1为扩张后结点总数,r2为扩张前结点总数 5. m←m+r1 6. xk←随机选择 Sk的元素 7. r2←r1 8. k←k+1 //层数+1
    • 3.例子
• 10.分支限界的优化
  • 1.分支限界
    • 1.组合优化问题
      • 目标函数（极大化或极小化） 约束条件（解满足的条件） 可行解: 搜索空间满足约束条件的解 最优解: 使得目标函数达到极大(或极小)的可行解
    • 2.代价函数
      • • 计算位置：搜索树的结点 • 值：极大化问题是以该点为根的子树所有可行解的值的上界( 极小化问题为下界） • 性质：对极大化问题父结点代价不小于子结点的代价(极小化问题相反)
    • 3.界
      • • 含义：当前得到可行解的目标函数的最大值(极小化问题相反） • 初值：极大化问题初值为 0(极小化问题为最大值) • 更新：得到更好的可行解时
    • 4.分支限界
      • 停止分支回溯父结点的依据： 1. 不满足约束条件 2. 对于极大化问题,代价函数值小于当前界（对于极小化问题是大于界）
    • 5.实例
      • 1.背包问题
        • 4 种物品,重量Wi与价值vi分别为 v1=1,v2=3,v3=5,v4=9 w1=2,W2=3,W3=4,W4=7 背包重量限制为10
      • 2.代价函数的设定
        • • 对结点<x1,x2, …,xk> ,估计以该结点为根的子树中可行解的上界. • 按vi/wi从大到小排序,i=1,2, ... ,n • 代价函数= 已装入价值+ ∆ ∆：还可继续装入最大价值的上界 ∆= 背包剩余重量 ×vk+1/wk+1(可装) ∆= 0(不可装)
      • 3.过程
  • 2.最大团问题
    • 1.概念
      • 无向图G=<V,E>, 求G的最大团. G的子图：G'= <V ',E'>, 其中V '⊆V,E'⊆E, G的补图：=<V,E'>,E'是E关于完全图边集的补集 G中的团：G的完全子图 G的最大团：顶点数最多的团
    • 2.独立集与团
      • 1.G的点独立集：G的顶点子集,且任意两点之间都没有边
      • 2.最大点独立集：顶点最多的点独立集
      • 3.命题：U是G的最大团当且仅当U是G的补集的最大点独立集
    • 3.应用
      • 编码, 故障诊断, 计算机视觉, 聚类分析,经济学, 移动通信,VLSI电路设计
    • 4.问题
      • 给定无向图G= < V,E >, 其中顶点集 V={1, 2, … ,n},边集为E.求G中的最大团
      • 解： <x1,x2, … ,xn>为 0-1向量,xk=1当且仅当顶点k属于最大团
    • 5.蛮力算法
      • 对每个顶点子集,检查是否构成团,即其中每对顶点之间是否都有边. 有2n个子集,至少需要指数时间
    • 6.分支限界
      • 搜索树为子集树. 结点 <x1,x2, … ,xk> 的含义：已检索顶点1, 2, … ,k, 其中xi=1表示顶点i在当前的团内,i=1, 2, … ,k 约束条件：该顶点与当前团内每个顶点都有边相连 界：当前已检索到的极大团的顶点数
    • 7.代价函数
      • 代价函数：目前的团可能扩张为极大团的顶点数上界 f=cn+n−k,其中Cn为目前团的顶点数（初始为0）,k为结点层数,n-k为剩余未搜索的结点
    • 8.时间复杂度
      • 最坏情况下时间：O(n2^n)
    • 9.实例
  • 3.货郎问题
    • 1.定义
      • • 输入:有穷个城市的集合c={c1,c2, …,cn}, 距离 d(ci,cj)=d(cj,ci)∈Z+,1≤i<j≤n • 解：1,2,…,n的排列k1,k2,…,kn使得：
    • 2.算法设计
      • 解向量为 <1, i1,i2,…,in-1>, 其中i1,i2,…,in-1为{2,3,…,n}的排列. 搜索空间为排列树,结点<i1,i2,…,ik> 表示得到k步路线 . 约束条件：令 B={i1, i2, … , ik }, 则 ik+1∈{2, … ,n}−B,即每个结点只能访问一次
    • 3.代价函数与界
      • 界：当前得到的最短巡回路线长度 代价函数：设顶点ci出发的最短边长度为li,dj为选定巡回路线中第j段的长度
    • 4.搜索树
    • 5.实例运行
      • 深度优先遍历搜索树 • 第一个界: <1,2,3,4>,长度为 29 • 第二个界: <1,2,4,3>,长度为 23 • 结点 <1,3,2>: 代价函数值 26>23,不再搜索, 返回<1,3>,右子树向下 • 结点<1,3,4>,代价函数值9+7+2+2=20, 继续,得到可行解<1,3,4,2>,长度 23. • 回溯到结点<1>,沿<1,4>向下...最优解<1,2,4,3>或<1,3,4,2>,长度23
    • 6.算法分析
      • • 搜索树的树叶个数：O((n−1)!),每片树叶对应1条路径,每条路径有n个结点. • 每个结点代价函数计算时间O(1),每条路径的计算时间为O(n) • 最坏情况下算法的时间O(n!)
  • 4.圆排列问题
    • 1.问题
      • 给定n个圆的半径序列, 各圆与底线相切排列, 假定每个圆占大于1的长度,求具有最小长度ln的圆的排列顺序
    • 2.分支限界
      • 解: <i1,i2,…,in> 为1,2,…,n的排列 搜索空间为排列树,部分解向量 <i1,i2,…,ik>：表示前k个圆已排好.令B={i1,i2, …,ik},下一个园选择ik+1 约束条件：ik+1∈{1, 2, … ,n}−B 界：当前得到的最小圆排列长度
    • 3.符号说明
      • k ：算法已经选择了第1—k个圆 rk ：第k个圆的半径 dk ：第k−1个圆到第k个圆的圆心水平距离,k>1 xk ：第k个圆的圆心坐标,规定x1=0, lk ：第1—k个圆的排列长度 Lk：放好1—k个圆以后,对应结点的代价函数值,已有的排列长度+后续的圆排列长度的下界Lk ≤ln
    • 4.长度估计
      • xk=xk-1+dk 部分排列长度:Lk=xk+rk+r1 排列长度:Ln=xk+ dk+1+dk+2 +…+ dn+rn+r1
    • 5.有关量的计算
    • 6.代价函数
    • 7.时间复杂度
      • • 搜索树树叶数为O(n!) • 每条路径代价函数的计算为O(n) • 最坏情况下算法时间复杂度为O(nn!)=O((n+1)!)
    • 8.改进方式
      • 例如,像1,2,…,n-1,n和n,n-1, …,2,1这种互为镜像的排列具有相同的圆排列长度,只计算一个就够了,可减少约一半的计算量。另一方面,如果所给的n个圆中有k个圆有相同的半径,则这k个圆产生的k!个完全相同的圆排列,只计算一个就够了
  • 5.连续邮资
    • 1.问题
      • 给定n种不同面值的邮票,每个信封至多贴m张,试给出邮票的最佳设计,使得从1开始,增量为1的连续邮资区间达到最大
    • 2.算法设计
      • 可行解 ：<x1,x2, … ,xn>,x1=1,x1<x2< …<xn 搜索策略：深度优先 约束条件：在结点 <x1,x2,…,xi> 处,邮资最大连续区间为{1, … , ri},xi+1的取值范围是{xi+1, … , ri+1},因为邮票的面值是不断增长的,至少比前面的多1, 且若xi+1>ri+1, ri+1的邮资将没法支付
    • 3.ri的计算
      • yi(j)：用至多m张面值xi的邮票加上x1,x2, … ,xi-1面值的邮票贴j邮资时的最少邮票数,则j为断点,可能不唯一,取最小的
    • 4.部分搜索树n=4,m=3
  • 小结
    • (1)适于求解组合搜索问题及优化问题 (2)求解条件：满足多米诺性质 (3)解的表示：解向量,求解是不断扩充解向量的过程 (4)回溯条件：搜索问题——约束条件,优化问题——约束条件 + 代价函数 (5)分支策略：深度优先、宽度优先、宽深结合、函数优先 (6)结点状态：白结点,黑结点,灰结点 (7)算法时间复杂度：W(n)=(p(n)f(n)),其中p(n)为每个结点的工作量,f(n)为结点个数最坏情况下时间通常为指数级,平均情况下比蛮力算法好,空间代价小 (8)降低时间复杂性的主要途径： • 根据树的分支设计优先策略结点少分支优先,解多分支优先 • 利用搜索树的对称性裁减子树
• 11.随机算法
  • 1.随机算法
    • 0.前言
      • 1.随机数
        • 1.随机序列
          • 概率相等(均匀随机),不可预测,不可重现
        • 2.在目前的计算机中
          • 1.无法产生真正的随机数,因此在随机算法中使用的随机数都是一定程度上随机的,即伪随机数
          • 2.产生伪随机数的方法: 线性同余法
      • 2.确定性算法
        • 1.输入确定: 则对这个特定输入的每次运行过程是可重复的,运行结果是一样的
    • 1.基本思想
      • 1.引入了随机因素
      • 2.在随机算法中: 不要求算法对所有可能的输入均正确计算,只要求出现错误的可能性小到可以忽略的程度,另外也不要求对同一输入,算法每次执行时给出相同的结果
    • 2.特点
      • 1.有不少问题,目前只有效率很差的确定性求解算法,但用随机算法去求解,可以（很快地）获得相当可信的结果
    • 3.应用领域
      • 1.随机算法在分布式计算、通信、信息检索、计算几何、密码学等许多领域都有着广泛的应用
      • 2.最著名的是在公开密钥体系、RSA算法方面的应用
    • 4.种类
      • 1.通常可分为两类:Las Vegas算法,Monte Carlo算法
    • 5.优点
      • 1.对于某一给定的问题,随机算法所需的时间与空间复杂性,往往比当前已知的、最好的确定性算法要好
      • 2.到目前为止设计出来的各种随机算法,无论是从理解上还是实现上,都是极为简单的
      • 3.随机算法避免了去构造最坏情况的例子
  • 2.Las Vegas算法
    • 1.在少数应用中,可能出现求不出解的情况,但一旦找到一个解,这个解一定是正确的
    • 2.在求不出解时,需再次调用算法进行计算,直到获得解为止
    • 3.对于此类算法,主要是分析算法的时间复杂度的期望值,以及调用一次产生失败（求不出解）的概率
  • 3.Monte Carlo算法
    • 1.通常不能保证计算出来的结果总是正确的,一般只能断定所给解的正确性不小于p （1/2＜p＜1）
    • 2.通过算法的反复执行（即以增大算法的执行时间为代价）,能够使发生错误的概率小到可以忽略的程度
    • 3.由于每次执行的算法是独立的,故k次执行均发生错误的概率为(1-p)^k
    • 4.对于判定问题 （回答只能是“Yes”或“No”）
      • 1.带双错的（two-sidederror）: 回答”Yes”或”No”都有可能错
      • 2.带单错的（one-sidederror）：只有一种回答可能错
      • 3.Las Vegas算法可以看成是单错概率为0的Monte Carlo算法
  • 4.两类算法应用场景
    • 1.在不允许发生错误的应用中（e.g.人造飞船、电网控制等）,Monte Carlo算法不可以使用
    • 2.若小概率的出错允许的话,Monte Carlo算法比Las Vegas算法要节省许多时间,是人们常常采用的方法
  • 5.实例
    • 1.Las Vegas
      • 1.找第k小元素
        • 1.思想
          • 1.在n个数中随机的找一个数A[i]=x,然后将其余n-1个数与x比较,分别放入三个数组中：S1(元素均<x),S2(元素均=x),S3(元素均＞x)
          • 2.若|S1|≥k,则调用Select(k,S1)
          • 3.若（|S1|+|S2|）≥k,则第k小元素就是x
          • 4.否则就有（|S1|+|S2|）＜k,此时调用Select(k-|S1|-|S2|,S3)
        • 2.分析
          • 1.定理：若以等概率方法在n个数中随机取数,则该算法用到的比较数的期望值不超过4n
          • 2.说明：如果有相同的数的话,落在S2中的可能性会更大,比较数的期望值会更小一些
      • 2.Sherwood随机化
        • 1.如果某个问题已经有了一个平均情况下较好的确定性算法,但是该算法在最坏情况下效率不高,此时引入一个随机数发生器（通常是服从均匀分布,根据问题需要也可以产生其他的分布）,可将一个确定性算法改成一个随机算法,使得对于任何输入实例,该算法在概率意义下都有很好的性能(Quicksort)
        • 2.如果算法（所给的确定性算法）无法直接使用Sherwood方法,则可以采用随机预处理的方法,使得输入对象服从均匀分布（或其他分布）,然后再用确定性算法对其进行处理。所得效果在概率意义下与Sherwood型算法相同
        • 3.Sherwood算法总能求得问题的一个解,且所求得的解是正确的
        • 4.当一个确定性算法在最坏情况和平均情况下的时间复杂度有较大差别时,可在确定性算法中引入随机性将其改造为Sherwood算法,以消除或减少问题的好坏输入实例间的差别
      • 3.随机抽样
        • 1.问题
          • 1.设给定n个元素（为简单起见,设为1,2,…n）要求从n个数中随机地选取m数（m≤n）
        • 2.Las Vegas算法
          • 1.可以用一个长为n的布尔数组B来标识i是否被选中,初始时均表为“未选中”,然后随机产生〔1,n〕之间的一个整数i,若B[i]为“未选中”,则将i加入被选中队列,同时把B[i]标识为“已选中”,反复执行直到m个不同的数全部被选出为止
        • 3.存在的问题
          • 1.当n和m很接近时,产生最后几个随机数的时间可能很长（有95％以上的可能性是已选中的数）
          • 1.1改进
            • 当m>n/2时,先去生成(n-m)(<n/2)个随机数,然后再取剩下的m个数作为选出的数
          • 2.当n与m相比大很多时（例：n﹥m^2）,布尔数组B对空间浪费很多
          • 2.1改进
            • 1.用一个允许冲突的、长为m的散列表,来存放产生的随机数,产生一个数后,看其是否在散列表中：若不在则将其加入,若已在则抛弃该数,再去产生下一个数
        • 4.分析
          • 1.设随机变量X表示扔硬币时,第一次碰到“正面朝上”的情况时,已经试过的次数X=k意味着前k-1次均向下,第k次向上概率表示为（p为正面朝上概率,q=1-p为背面朝上概率）,前k-1次均向下,第k次向上（几何分布） •E(X)=1/p
          • 2.设pj是这样的概率：在j-1个数已经选出的前提下,当前随机产生的数是以前尚未选过的数的概率pj=(n-j+1)/n,qj=1-Pj,表示当前随机产生的数是以前选过的j-1个数之一的概率qj=1-Pj=(j-1)/n
          • 3.设随机变量Xj（1≤j≤m）表示：在j-1个数已经选出后,再去找出第j个不同的数时,所需要产生的整数个数,则与前述的X类似,Xj服从几何分布,E(Xj)=1/Pj,设Y表示从n个数中选出m个数时（m≤n/2）,所需产生的整数个数的总和的随机变量（目标）则有Y=X1＋X2＋X3＋…＋Xm E(Y)≤1.69n
          • 4.求解随机抽样问题的算法的时间复杂度T(n)正比于算法产生整数的个数总和Y,所以T(n)的期望值与E(Y)成常数比,即有T(n)=Θ(n)（期望值）
      • 4.n后问题
        • 1.问题
          • 1.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
        • 2.Las Vegas算法
          • 1.对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的
          • 2.在棋盘上相继的各行中随机地放置皇后,并注意使新放置的皇后与已放置的皇后互不攻击,直至n个皇后均已相容地放置好,或已没有下一个皇后的可放置位置时为止
        • 3.与回溯法结合
          • 1.如果将上述随机放置策略与回溯法相结合,可能会获得更好的效果
          • 2.可以先在棋盘的若干行中随机地放置皇后,然后在后继行中用回溯法继续放置,直至找到一个解或宣告失败,随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率也就越大
        • 4.伪码
          • 1) x[8]←0; count←0; 2) for (i=1;i<=8; i++) 2.1) 产生一个[1,8]的随机数j; 2.2) count=count+1; //第count试探 2.3) if (皇后i放在位置j不发生冲突) 则x[i]=j; count=0; 转2)放下一个皇后； if (count==8) 算法失败； else 转2.1重新放皇后i； 3) x[1]~x[8]作为一个解输出；
        • 5.总结
          • 随机放2个皇后,再回溯比完全用回溯快大约两倍 随机放3个皇后,再回溯比完全用回溯快大约一倍 随机放所有皇后,再回溯比完全用回溯慢大约一倍,产生随机数所需的时间导致
    • 2.Monte Carlo
      • 1.字符串相等
        • 1.问题
          • 1.设A处有一个长字符串x,B处也有一个长字符串y,A将x发给B,由B判断是否有x=y
        • 2.算法
          • 1.首先由A发一个x的长度给B,若长度不等,则x≠y
          • 2.若长度相等,则采用“取指纹”的方法
          • 3.A对x进行处理,取出x的“指纹”,然后将x的“指纹”发给B,由B检查x的“指纹”是否等于y的“指纹”,若取k次“指纹”（每次取法不同）,每次两者结果均相同,则认为x与y是相等的,随着k的增大,误判率可趋于0
          • 4.常用的指纹：令I(x)是x的编码,取Ip(x)≡i(x)(modP)作为x的指纹,这里的p是一个小于M的素数,M可根据具体需要调整
        • 3.错判率分析
          • 1.B接到指纹Ip(x)后与Ip(y)比较,如果Ip(x)≠Ip(y),当然有x≠y, 如果Ip(x)=Ip(y)而x≠y,则称此种情况为一个误匹配
          • 2.现在需要确定：误匹配的概率有多大?若总是随机地去取一个小于M的素数p,则对于给定的x和y,Pr[failure]=（使得Ip(x)=Ip(y)但x≠y的素数p(p＜M)的个数）／（小于M的素数的总个数）
          • 3.误匹配的概率小于1/n,当n很大时,误匹配的概率很小,设x≠y,如果取k个不同的小于2n^2的素数来求Ip(x)和Ip(y),即k次试验均有Ip(x)=Ip(y)但x≠y（误匹配）的概率小于1/n^k,当n较大、且重复了k次试验时,误匹配的概率趋于0
      • 2.模式匹配
        • 1.问题
          • 1.给定两个字符串：X=x1,…,xn,Y=y1,…,ym,看Y是否为X的子串？（即Y是否为中的一段）
          • 2.可用KMP算法在O(m+n)时间内获得结果,但算法较为繁琐
        • 2.brute-force思想
          • 1.记X(j)=xjxj＋1…xj+m-1（从X的第j位开始、长度与Y一样的子串）
          • 2.从起始位置j=1开始到j=n-m+1,不去逐一比较X(j)与Y,而仅逐一比较X(j)的指纹Ip（X(j)）与Y的指纹Ip（Y),由于Ip（X(j+1)）可以很方便地根据Ip（X(j)）计算出来,故算法可以很快完成
        • 3.伪码
          • 1.随机取一个小于M的素数p，置j←1； 2.计算Ip(Y)、Ip(X(1))及Wp(=2m mod p)； 3.While j≤n-m+1 do { if Ip(X(j))=Ip(Y) then return j /﹡X(j)极有可能等于Y﹡/ else{根据Ip(X(j))计算出Ip(X(j+1))；j增1} } 4.return 0; /﹡X肯定没有子串等于Y﹡/
        • 4.时间复杂度
          • 1.计算Ip(Y)、Ip(X(1))及2mmodP的时间不超过O(m)次运算,Ip(X(j+1))的计算,只需用O(1)时间,由于循环最多执行n-m+1次,故这部分的时间复杂度为O(n),总的时间复杂性为O(m+n)
        • 5.错判率分析
          • 当Y≠X(j),但Ip(Y)=Ip(X(j))时产生失败,失败的概率Pr[failure]<1/n,即失败的概率只与X的长度有关,与Y的长度无关
        • 6.转成Las Vegas算法
          • 1.当Ip(Y)=Ip(X(j))时,不直接returnj,而去比较Y和X(j),即在returnj之前加一个判断看Y和X(j)是否相等,相等则returnj,否则继续执行循环,如果有子串X(j)与Y相匹配,该算法总能给出正确的位置（即算法出错的概率为0）
      • 3.主元素
        • 1.问题
          • 1.设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时,称元素x是数组T的主元素,对于给定的数组T,判定T数组中是否含有主元素
        • 2.Monte Carlo算法
          • public static boolean majority(int[]t, int n) {// 判定主元素的蒙特卡罗算法 rnd = new Random(); int i=rnd.random(n)+1; int x=t[i]; // 随机选择数组元素 int k=0; for (int j=1;j<=n;j++) if (t[j]==x) k++; return (k>n/2); // k>n/2 时t含有主元素 }
          • 随机选择一个元素,将数组中的数依次和其进行比较,统计相等的次数,若>n/2,则存在
        • 3.多次重复调用
          • public static boolean majorityMC(int[]t, int n, double e) {// 重复多次调用算法majority int k= (int) Math.ceil(Math.log(1/e)/Math.log(2)); for (int i=1;i<=k;i++) if (majority(t,n)) return true; return false; }
          • 1.计算时间和调用的次数相关
      • 4.素数测试
        • 1.问题
          • 1.判断一个数是否为素数,费尔马（fermat ）小定理 若n为素数,且0<a<n,有a^n-1≡1(modn),即Fermat条件a^n-1≡1(modn)是素数的必要条件,反过来说,若a^n-1≠1(modn)则n必为合数,逆定理不成立,但反例不多,特别是当n很大且又是随机选取的时候
        • 2.判定方法
          • 1.直接用Fermat条件2^n-1≡1(modn)来判断n是否为素数,此时,若算法的回答是“合数”,则100％正确,若算法的回答是“素数”,则出错概率很小（带单错）,当n不太大时,满足条件2^n-1≡1(modn)的合数n不多
          • 2.能否对其它的a去测试是否有a^n-1≡1(modn)（a=3,4,…）,从而再排除一些满足条件2^n-1≡1(modn)的合数？ 回答是：可以排除掉一些,但不能完全排除满足Fermat条件的数未必全是素数,有些合数也满足Fermat条件,这些合数被称为Carmichael数
        • 3.二次探测
          • 1.如果p是一个素数,且0<x<p,则方程x^2 ≡1(modP)的解为x=1,p-1
          • 2.利用二次探测定理,可以在基于Fermat条件判断时,增加二次探测,一旦违背二次探测条件,则可得出不是素数的结论
        • 4.代码
          • vote static int power(int a, int p, int n) { // 计算 a^p mod n，并实施对n的二次探测 int x, result; if (p==0) result=1; else { x=power(a,p/2,n); // 递归计算 result=(x*x)%n; // 二次探测 if ((result==1)&&(x!=1)&&(x!=n-1)) composite=true; if ((p%2)==1) // p是奇数 result=(result*a)%n; } return result; } public static boolean prime(int n) {// 素数测试的蒙特卡罗算法 rnd = new Random(); int a, result; composite=false; a=rnd.random(n-3)+2; result=power(a,n-1,n); if (composite||(result!=1)) return fa else return true; }
• 12.NP完全性
  • 0.前言
    • 1.字符串与语言
      • 字母表: 任意一个有限集.常用记号Σ,Γ 符号: 字母表中的元素 字符串: 字母表中符号组成的有限序列,如asdf,通俗地说即单词 串的长度,例:Abcde的长度为5 串的连接,例:abc与de的连接是abcde 串的反转,例:abcde的反转是edcba 空词: 记为ε,长度为0 语言: 一些字符串的集合
    • 2.计算的模型-自动机理论
      • 1.有限自动机(FA)
        • 存储量极小的计算机,在文本处理,编译程序及硬件设计中有应用
      • 2.下推自动机(PDA)
        • 带一个栈的计算机,在程序设计语言和人工智能中有应用
      • 3.图灵机(TM)
        • 有无限可改写存储的计算机,能解决实际计算机所能解决的一切问题
      • 4.FA和PDA是简化的图灵机,一般将以图灵机作为计算的理论模型
    • 3.P与NP是否相等
      • 1.P问题是容易解决的问题
      • 2.NP问题是容易验证的问题
      • 3.P⊆NP,但是P=NP还是P⊂NP(真包含)? 它是21世纪的七大数学难题
  • 1.计算模型
    • 0.说明
      • 1.计算模型是计算机科学的重要组成部分
      • 2.NP-完全概念的原始定义需要借助非确定性Turing机等计算模型的概念
      • 3.计算模型研究中有不少好的思想可供借鉴
    • 1.RAM
      • 1.RandomAccess Machines
      • 2.一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释: 把RAM程序看成是计算一个函数/把RAM程序当作一个语言接受器
    • 2.RASP
      • 1.RandomAccess StoredProgram
      • 2.RASP的整体结构类似于RAM,所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码,第二个寄存器存放地址
    • 3.确定性Turing机
      • 1.什么是计算？ 什么问题是可计算的？
        • 1.Turing认为计算是一个人拿一支笔在一张纸上进行的操作,输入是眼睛看到的符号,根据脑中的规则在纸上擦掉或写上一些符号；再用眼睛看下面的符号,根据规则进行擦写的工作；重复上述工作,直到这个人认为可以结束为止。此时,最后写下的符号就是所要的结果
        • 2.特点：在这个（计算）过程中,只用到了有穷多个符号
        • 3.Turing根据这个过程构造出了一个计算模型,称之为Turing机
        • 4.Turing发现该模型可以实现非常复杂的计算,Turing称：凡是Turing机可以计算的问题就是可计算的,否则就是不可计算的,由此引出可计算性理论的研究
      • 2.丘奇-图灵论题
        • 1.任何合理的计算模型都是相互等价的（计算范围相同）
        • 2.合理：单位时间内可以完成的工作量,有一个多项式的上限
        • 3.迄今为止所有被提出的合理计算模型均满足该论题
      • 3.Turing机的形式
        • 1.单带双向Turing机 单带单向Turing机 多带双向Turing机 多带单向Turin机
        • 2.已经证明,这些Turing机的计算能力（在多项式意义下）相同
        • 3.k带图灵机可形式化地描述为一个7元组(Q,T,I,δ,b,q0,qf)
          • (1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。 (3)I是输入符号的集合，I⊆T。 (4)b是唯一的空白符，b∈T-I。 (5)q0是初始状态。 (6)qf是终止(或接受)状态。 (7)δ是移动函数。它是从Q×T^k的某一子集映射到Q×(T×{L，R，S})^k的函数
        • 4.与RAM模型类似,图灵机既可作为语言接受器,也可作为计算函数的装置
      • 4.根据有限状态控制器的当前状态及每个读写头读到的带符号, 图灵机的一个计算步可实现下面3个操作之一或全部
        • (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头,向左移动一个方格(L) 或向右移动一个方格(R)或停在当前单元不动(S)
    • 4.非确定性Turing机
      • 1.一般地说,将可由多项式时间算法求解的问题看作是易处理的问题,而将需要超多项式时间才能求解的问题看作是难处理的问题
      • 2.有许多问题,从表面上看似乎并不比排序或图的搜索等问题更困难,然而至今人们还没有找到解决这些问题的多项式时间算法,也没有人能够证明这些问题需要超多项式时间下界
      • 3.在图灵机计算模型下,这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性,人们提出了另一个能力更强的计算模型,即非确定性图灵机计算模型,简记为NDTM(NondeterministicTuringMachine)。在非确定性图灵机计算模型下,许多问题可以在多项式时间内求解
      • 4.一台k带DTM（确定性Turing机）根据其当前所在状态及k个读写头当前读到的字符唯一地确定下一步的动作
      • 5.与DTM不同的是,NDTM的每一步动作允许有若干个选择
  • 2.判定问题
    • 1.判定问题：回答是“Yes”或“No”
    • 2.最优化问题（不是Yes-No问题）可以与一个判定问题相对应
      • 比如，最优化问题：团集问题(CLIQUE)：任给一个无向图G，找出G中最大的团集。 团集：点的集合，满足：任两点之间均有边相连 对应的判定问题：G中是否有k-团（k个顶点的团集）？
    • 3.证书
      • 1.若集合S包含判定问题A的所有解,则称S是A的证书集,S中的元素称为A的一个证书（certificate,注意证书不一定是解）
  • 3.P类问题
    • 1.P={L|L是一个能在多项式时间内被一台DTM所接受的语言},P类问题是多项式时间可解的
  • 4.NP类问题
    • 1.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言},NP类问题是多项式时间可验证的
    • 2.一个判定问题中的每一个实例编码为一个符号串ω,使得该实例的回答为Yes当且仅当它的编码ω在多项式时间里被一台NDTM所接受,则称该判定问题属于NP类
    • 3.若判定问题A满足：1、有证书集S；2、存在一个算法F,对于S中的每一个证书α, F都能够在多项式时间里验证α是否为A的一个解,则称A∈NP
    • 4.k-团问题
      • 0.给定无向图G=(V,E),顶点集V的任何一个k顶点子集V'就是k-团问题的一个证书,如果Q是k-团问题的解,则一定有Q∈S
      • 1.对于任给的一个证书V’（k顶点子集即|V’|=k）,只要逐一检查V’中的任意两点 之间是否有边,这样的点共有k(k-1)/2个,若每个点对间均有边相连,则V’是一个k-团,否则不是,验证算法时间为Θ(k^2),故是多项式时间可验证的
    • 5.Hamilton路径问题
      • 0.给定无向图G=(V,E),任何一个由n个互不相同的顶点构成的序列就是H路径问题的一个证书,如果图G有Hamilton路径,则该路径一定属于S
      • 1.对于任给的一个证书即序列,只要逐一检查序列中相邻点之间是否有边相连 若n-1个相邻点对均有边相连,则该序列是Hamilton路径,否则不是 验证算法时间为Θ(n),故是多项式时间可验证的
  • 5.NP-C完全问题
    • 1.定义（狭义,Karp）：称满足下述2条的语言L0是NP-C的, 一个NP完全问题能在多项式时间得到解决,那么NP中每一个问题都可以在多项式时间求解
    • 2.非形式定义,如果一个问题属于NP类,且与NP类中的任何问题是一样“难”的,则说它属于NP-C类,也称其是NP完全的（NP-Complete）
    • 3.NP完全问题是难处理的,迄今为止,未发现有NP完全问题的多项式时间求解方案
    • 4.问题的多项式变换（规约）
      • 1.设IA是判定问题A的任一实例,B是另一判定问题,若存在一个从A到B的映射f满足
      • ∀IA∈A,若IA的答案为‘Yes’,则对应实例f(IA)（与IA相对应的B问题的实例）的答案为‘Yes’ ∀IA∈A,若IA的输入规模为n,则对应实例f(IA)的输入规模不超过PA(n),PA(n)是与判定问题A有关的多项式 ∀IA∈A,若IA的输入规模为n,则对应实例f(IA)的输入在多项式时间p(n)内可计算
      • 2.则称问题A可多项式变换为B,记作A≤pB(≤p亦称Karp规约)
    • 5.多项式变换(规约)的作用
      • 1.若A≤pB且问题B是多项式时间可判定的,则问题A也一定是多项式时间可判定的
      • 2.要证明一个判定问题B是NP-C的,除了要证明B是多项式时间可验证的（从而B属于 NP类）,还要找一个NP-C问题A,证明A可以在多项式时间里变换为B,且A的任一实例回答为‘Yes’与之对应的B的实例回答为‘Yes’
    • 6.限制法
      • 1.要证明问题π∈NP-C,先证明π∈NP,再找一个已知的NP-C问题π’,证明π’是π的特例（在π上加了一些限制）,从而立即有π’≤pπ
    • 7.NP-hard类问题
      • 1.定义
        • 一个语言L满足上述性质(2),但不一定满足性质(1),称该语言是NP难的
      • 2.求解方法
        • 1.当n不太大时,可使用a)动态规划法b)分支限界法c)回溯法
        • 2.求近似解。在误差允许的范围之内找一个解,该近似解可以在多项式时间里得到
        • 3.用启发式算法求解,根据具体问题设计启发式搜索策略,在理论上往往缺乏严格的证明,用实验数据说明算法很有效
        • 4.智能优化算法,常常能获得很好的结果。但有偶然性,与最优解的误差难以给出
  • 6.相互关系
    • 1.P问题属于NP问题,NPC问题属于NP问题。NPC问题同时属于NPhard问题,是NP与NPhard的交集
• 13.近似算法
  • 1.近似算法
    • 1.迄今为止,所有的NP完全问题,均未能找到多项式时间的算法,故当问题规模较大时,求得最优的精确解的可能性很小,在此情况下,往往退而去求比最优精确解稍差一点的解作为问题的近似答案
  • 2.近似算法的性能
    • 1.近似算法一般都比较简单,但设计近似算法时必须关注所设计的算法所得到的近似解与最优解之间的差距到底有多大
    • 2.若一个最优化问题的最优值为c*,求解该问题的一个近似算法求得的近似最优解相 应的目标函数值为c,则将该近似算法的近似比定义为max{c*/c,c/c*}
    • 3.在通常情况下,近似比是问题输入规模n的一个函数ρ(n),即max{c*/c,c/c*} ≤ ρ(n)
  • 3.几个NPC问题 的近似算法
    • 1.装箱问题
      • 1.问题
        • 设有n个物体u1,u2,…,un,每个物体的体积不超过1。另外,有足够多的、体积为1的 箱子。箱子、物体均是长方体且截面相同,问如何装箱,使得所用箱子数最少
      • 2.First-Fit（FF）算法
        • 1.思想
          • 从排在最前面的箱子开始,对每个箱子剩余的体积逐一进行检查,一旦碰到第一个能够装进当前物体的箱子时,就立即把该物体装入这个箱子。对每个物体反复执行上述程序
        • 2.最坏时间复杂度
          • O(n^2)
        • 3.分析
          • 1.记号I：表示某一问题的任一实例,OPT(I)：表示该实例的最优解
          • 2.FF算法满足：对于任何装箱实例I,都有FF(I)≤2OPT(I),更为准确地,对所有装箱问题的实例I,都有FF(I)≤┌17/10OPT(I)┐,且存在OPT(I)任意大的实例I,使得FF(I)≥17/10(OPT(I)-1)
          • 3.用FF算法不能保证所获得的解是最优解
      • 3.Next-Fit（NF）算法
        • 1.思想
          • 先把第一个空箱置为当前箱。然后依次把物品u1,u2,…,un按下列方式装箱：若当前所指的箱子里放得下ui,则把ui放入箱中；若放不下则把ui放入下一个空箱,把当前指针指向（放ui的）该箱
        • 2.最坏时间复杂度
          • O(n)（因为对每个物品只检查当前的箱子）
        • 3.分析
          • NF算法满足：对于任何装箱实例I,都有NF(I)≤2OPT(I)-1
      • 4.Best-Fit（BF）算法
        • 1.思想
          • FF算法的修改：在已装有物品的箱子中,找一个既能放下ui、又使得其剩余空间最小的箱子来放ui
        • 2.分析
          • 表面上看起来该算法要比FF法更能充分利用空间,但实际上,Johnson等人证明了BF法在最坏情况下的性能,本质上与FF法相同
      • 5.FFD（First-Fitdecreasing）算法
        • 1.思想
          • 1.先将所有物品从大到小排序,然后再使用FF法
        • 2.分析
          • 1.对一切装箱实例I,有FFD(I)≤┌4/3OPT(I)┐,当OPT(I)=3k+1时,有FFD(I)≤ ⌊4/3OPT(I)⌋,对所有装箱问题的实例I,有FFD(I)≤11/9OPT(I)+1
    • 2.顶点覆盖
      • 1.问题
        • 1.无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’⊆V,使得若(u,v)是G的一条边,则v∈V’或 u∈V’
        • 2.顶点覆盖V’的大小是它所包含的顶点个数|V’|
        • 3.顶点覆盖问题就是要求在一个给定的无向图中,找出一个具有最小规模的顶点覆盖
      • 2.代码
        • VertexSet approxVertexCover ( Graph g ) { cset=∅； //存储顶点覆盖中的各顶点,初始为空 e1=g.e； //图的边集 while (e1 != ∅) //直至边集为空,所有的边均被覆盖 { 从e1中任取一条边(u,v)； cset=cset∪{u,v}； //将边的端点加入到cset中 从e1中删去与u和v相关联的所有边；//这些边已经被u,v覆盖 } return cset }
    • 3.旅行商问题
      • 1.问题
        • 给定一个完全无向图G=(V,E),其每一边(u,v)∈E有一非负整数代价c(u,v),要找出G中具有最小代价的哈密尔顿回路
      • 2.特殊性质
        • 1.代价函数c往往具有三角不等式性质,即对任意的3个顶点u,v,w∈V,有：c(u,w)≤c(u,v)+c(v,w)
        • 2.当图G中的顶点就是平面上的点,任意2顶点间的代价就是这2点间的欧氏距离时,代价函数c就具有三角不等式性质
      • 3.算法
        • void approxTSP (Graph g) { (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回； }
        • 1.对于给定的无向图G,可以利用找图G的最小生成树的prim算法设计找近似最优的旅行售货员回路的算法
        • 2.当代价函数满足三角不等式时,算法找出的路径的代价不会超过最优路径的代价的2倍
      • 4.一般的旅行商问题
        • 1.在代价函数不一定满足三角不等式的一般情况下,不存在具有常数近似比的解TSP问题的多项式时间近似算法,除非P=NP,换句话说,若P≠NP,则对任意常数ρ>1,不存在近似比为ρ的求解旅行商问题的多项式时间近似算法
• 主题