考虑输入参数在什么取值范围内用贪心法可以得到最优解
估计近视算法和最优解的误差,对所有的输入实例贪心法所得到的解和最优解的误差(误差上届)
贪心算法往往有多种策略,在选择策略时的排除手段主要是举反例
适合证明设计自然数的命题P(n)
证明P(1)为真,(或P(0)为真)
若对任意n有P(n)为真,证明P(n+1)为真
适合证明设计自然数的命题P(n)
证明P(1)为真,(或P(0)为真)
证明对于任意小于n的k有P(k)为真,证明P(n)为真
给一个集合两端[begin,end],给出n个活动,每个活动占用的集合是[ai,bi],要求在这个集合内占用不能重复的安排最多的活动(注意不是占用最多的资源,而是安排最多项活动)
每次选择待选集合中满足相容性且结束时间最早的元素加入选择集合. 使用select函数每次从剩余待选集合中挑选符合相容性的结束时间最早的元素加入选择序列,最后没有选择的时候的选择序列就是最优解.
算法select每次在未加入过的元素中选择结束时间最近且符合相容性的元素添加到选择序列末位. 算法Select执行到第k步,选择k项活动, i1=1,i2,…ik 则存在最优解A包含活动i1=1,i2,…ik (选择序列就是最优解,当前选择序列是最优解子集)
k=1,证明存在最优解包含活动1 任取最优解集A,A中活动按结束时间递增排列,如果A的第一个活动j不是1,那么用1替换j得到集合A’, 因为1的结束时间最近,即f1<fj<2号任务开始的时间,替换完成后符合相容性, 此时A’集合的元素个数和A集合相等,A’也是最优解,且含有1.
假设命题对k为真,证明对k+1也为真 算法执行到第k步选择了活动i1,i2,…,ik,有最优解A包含i1,i2,…,ik,A剩余的元素从待选集合S’中选择.
select算法的k+1步会从待选集合中选取一个starttime>fk,且endtime最小的元素Sfmin. 设此时Ak+1号元素为j,j不等于Sfmin,则有fj>fSfmin,sj>fk,此时用Sfmin替换j元素,满足sSfmin>fk,fSmin<fj,设替换后的集合是A’,A’元素个数显然等于A,则A’也是最优解.转化成子问题也能求解,待选数组S’和A抛去i1,i2,…,ik,的部分又重新组合成了一个归纳基础n个集装箱,标号是1-n,集装箱i重量是wi,轮船装载重量限制是C,无体积限制,问如何装使得装载的集装箱最多?设对于任意i,wi<=C 这个问题是0-1背包问题的子问题,集装箱相当于物品,物品重量是wi,价值vi都是1,装载限制C相当于背包重量限制b.
设<x1,…xn>表示解向量,xi=0或1代表不装/装 目标函数: 约束条件:
轻者优先
将集装箱按照重量升序排列 按照标号从小到大装箱,知道下一个箱子使得总重超过轮船装载重量限制则停止.
对于装载问题任何规模为n的实例,算法能得到最优解. 设集装箱重量升序标记是1-n
规模是1名题正确 对于任何只含有一个箱子的实例,贪心法有最优解 显然正确.
规模是n正确,则规模是n+1也正确 总体来说还是假设最优解进行替换得到的解和最优解等效的方法.贪心有的证明时候考虑的就是这么简单,毕竟贪心自己也只能考虑一步.
客户的属性是工作需要消耗的时间ti和要求完成的时间时间di. f(i)是我们安排的客户开始的时间 那么单个客户的延迟就是f(i)+ti-di,小于0无延迟. 注意目标函数**不是总延迟最小,而是最大的延迟最小**.
算法Schedule 输入:A客户,T单个客户用时,D客户要求结束时间 输出:f开始时间表.
按照di从小到大排列逐个安排.
从一个没有空闲的最优解出发,逐步转变成没有逆序的解,根据引理1这个解和算法解具有相同的最大延迟,
假设一个最优调度存在逆序,那么一定有一个相邻的逆序i,j.交换这个相邻的逆序,则这对逆序被消除了,得到的解依然是最优. 交换i,j不影响其他工作的延迟(i,j看做一个整体)交换后j的延迟不会增加,但是i的延迟可能会增加证明i在交换后调度f2的延迟小于j在调度f1的延迟 设有di,ti,dj,tj,fs任务开始 对于调度f1只观察ij情况有 i延迟=fs+ti-dij延迟=fs+ti+tj-dj 对于调度f2有j延迟=fs+tj-dji延迟=fs+tj+ti-di 又因为i,j是一组逆序,对于f1,f(i)<f(j),di>dj 所以:f2的i延迟=fs+tj+ti-di<f1的j延迟=fs+ti+tj-dj,所以最大延迟可能不变或缩小 每次交换之后逆序数-1,至多经过n(n-1)/2次交换得到一个没有逆序的最优调度,等价于算法的解.用0-1字符串作为代码表示字符,要求任何字符的代码都不能作为其他字符代码的前缀 这样从前到后进行解码就有了唯一性,否则可能是不唯一的
从前向后的字符串解析过程就像是树从根结点开始的搜索过程,每层就是1位. 二元前缀码可以由一个二叉树表示. 比如:
是每个码出现的频率*码长 B = ∑ n = 1 N f ( x i ) ∗ d ( x i ) B = \sum_{n=1}^Nf(x_i)*d(x_i) B=∑n=1Nf(xi)∗d(xi)之和.
给定字符集 C = x 1 + x 2 + , . . . , + x n C={x_1+x_2+,...,+x_n} C=x1+x2+,...,+xn和频率集 F = f i , i ∈ [ 1 , n ] F={f_i},i\in[1,n] F=fi,i∈[1,n],求关于 C C C的一个最优前缀码(平均传输位数最小) 实际上就是元素集C和开销集合F,F需要开销多少次用层高D来表示,可以是并归几次,也可以是码长多长.
数学形式就这样 B = ∑ n = 1 N f ( x i ) ∗ d ( x i ) B = \sum_{n=1}^Nf(x_i)*d(x_i) B=n=1∑Nf(xi)∗d(xi) 是个对形如如上的函数求最小值的问题.已知 F F F在规则内安排 D D D使得总量最小.
字 符 集 C , 频 率 集 F 字符集C,频率集F 字符集C,频率集F
一 棵 树 T 或 者 一 个 队 列 Q 一棵树T或者一个队列Q 一棵树T或者一个队列Q 树根节点或队列剩下的最后一个元素的频率就是最小频率.
C 是 字 符 集 , ∀ c ∈ C , f ( c ) 是 频 率 , x , y ∈ C 且 , f ( x ) f ( y ) 频 率 最 小 , 那 么 存 在 最 优 二 元 前 缀 码 使 得 x , y 等 长 且 仅 在 最 后 一 位 不 同 C是字符集,\forall c {\in}C,f(c)是频率,x,y{\in}C且,f(x)f(y)频率最小,那么存在最优二元前缀码使得x,y等长且仅在最后一位不同 C是字符集,∀c∈C,f(c)是频率,x,y∈C且,f(x)f(y)频率最小,那么存在最优二元前缀码使得x,y等长且仅在最后一位不同 表示在树上就是是最后一级子叶节点
加入有最优二元前缀码使得最小频率的 x , y x,y x,y不是最底层子叶节点,记最底层子叶节点为 a , b a,b a,b交换x,a,y,有交换后的 平均传输位数比交换前的小.
设 T 是 二 元 前 缀 码 的 二 叉 树 , ∀ x , y ∈ T , x , y 是 兄 弟 子 叶 , z 是 x , y 的 父 亲 节 点 设T是二元前缀码的二叉树,\forall x,y{\in}T,x,y是兄弟子叶,z是x,y的父亲节点 设T是二元前缀码的二叉树,∀x,y∈T,x,y是兄弟子叶,z是x,y的父亲节点 设 有 树 T ′ = T − { x , y } 设有树T'=T-\{x,y\} 设有树T′=T−{x,y} 且 令 z 的 频 率 f ( z ) = f ( x ) + f ( y ) 且令z的频率f(z)=f(x)+f(y) 且令z的频率f(z)=f(x)+f(y) 有 T ′ 是 新 的 字 符 集 合 C ′ = ( C − { x , y } ) ∪ { z } 的 二 叉 树 有T'是新的字符集合C'=(C-\{x,y\})\cup\{z\}的二叉树 有T′是新的字符集合C′=(C−{x,y})∪{z}的二叉树 设 L 是 每 层 之 间 减 少 的 码 位 , 一 般 情 况 下 L = = 1 设L是每层之间减少的码位,一般情况下L==1 设L是每层之间减少的码位,一般情况下L==1 那 么 B ( T ) = B ( T ′ ) + ( f ( x ) + f ( y ) ) ∗ L ; 那么B(T)=B(T')+(f(x)+f(y))*L; 那么B(T)=B(T′)+(f(x)+f(y))∗L;
平均传输位数是个累加式,且只累加树的子叶节点,在上面的变化中,减少了两个子叶节点的累加共享: ( f ( x ) + f ( y ) ) ∗ 本 层 编 码 长 度 (f(x)+f(y))*本层编码长度 (f(x)+f(y))∗本层编码长度 增加了一个子叶节点,增加的贡献是: ( f ( x ) + f ( y ) ) ∗ 本 层 − 1 层 的 编 码 长 度 (f(x)+f(y))*本层-1层的编码长度 (f(x)+f(y))∗本层−1层的编码长度 二者相减是: ( f ( x ) + f ( y ) ) ∗ L (f(x)+f(y))*L (f(x)+f(y))∗LL是每层编码长度减少量.
Huffman算法对任意规模为n( n ≥ 2 n\ge2 n≥2)的字符集C都得到关于C的最优前缀码的二叉树
对于 n = 2 n=2 n=2的字符集,Huffman算法得到最优前缀码
显然.
假设Hufman对于规模为k的字符集都得到最优前缀码,那么对于规模为k+1的字符集也得到最优前缀码.
假设Huffman对于规模为k的字符集可以得到最优前缀码,考虑规模为k+1的字符集 C = { x 1 , x 2 , x 3 , . . . , x k + 1 } C=\{x_1,x_2,x_3,...,x_{k+1}\} C={x1,x2,x3,...,xk+1} 其 中 x 1 , x 2 ∈ C 是 频 率 最 小 的 两 个 字 符 其中x_1,x_2\in C是频率最小的两个字符 其中x1,x2∈C是频率最小的两个字符,令: C ′ = ( C − { x 1 , x 2 } ) ∪ { z } C'=(C-\{x_1,x_2\})\cup\{z\} C′=(C−{x1,x2})∪{z} f ( z ) = f ( x 1 ) + f ( x 2 ) f(z)=f(x_1)+f(x_2) f(z)=f(x1)+f(x2) 规模缩小了1变成了k 根据归纳假设,算法得到了一颗关于 字 符 集 C ′ , 频 率 集 F ′ 字符集C',频率集F' 字符集C′,频率集F′的最优前缀码二叉树T’(很可能和T的树相差很大) 把 x 1 , x 2 x_1,x_2 x1,x2作为z的儿子附加到T’中的z下,得到一个新的树T’’,他的字符集和原始字符集一致 现在证明T’'也是关于最初字符集C的前缀二叉树. 主要由定理2计算 设对于最初树T有: B = B m i n B=Bmin B=Bmin 对于去掉两个最小的 x 1 , x 2 x_1,x_2 x1,x2树有按Huffman的新的最小 B ′ B' B′: 对于加上 x 1 , x 2 x_1,x_2 x1,x2之后的树有: B ′ ′ = B ′ − f ( z ) ∗ L z 层 码 长 + ( f ( x ) + f ( y ) ) ∗ L ( z + 1 ) 层 码 长 = B ′ + ( f ( x ) + f ( y ) ) ∗ L B''=B'-f(z)*L_{z层码长}+(f(x)+f(y))*L_{(z+1)层码长}=B'+(f(x)+f(y))*L B′′=B′−f(z)∗Lz层码长+(f(x)+f(y))∗L(z+1)层码长=B′+(f(x)+f(y))∗L 下 图 的 ∗ ′ 我 用 ′ ′ 表 示 了 下图的*'我用''表示了 下图的∗′我用′′表示了
