9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

导弹拦截nlogn算法



拦截导弹
? 给定N个数
– 求最长的不上升子序列长度 – 求最少有多少个不上升序列能覆盖所有的数, 即求最少覆盖序列。

? N<=10000.

分析
? 设f(i)表示前i个数的最长不上升序列的长度。 则, f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 这

里0<j<i<=n。 显然时间复杂度为O(n2)。 ? 上述式子的含义:找到i之前的某j,这个数 不比第i个数小,对于所有的j取f(j)的最大值。

优化
? 分析样例 i f 1 2 3 4 5 6 7 8 389 207 155 300 299 170 158 65 1 2 3 2 3 4 5 6

? 这里找j,是在1~i之间进行寻找,那么我们能否快速查找到 我们所要更改的j呢? ? 要能更改需要两个条件: – j<i and a[j]>=a[i] – f(j)尽可能大 ? 以上两个条件提示我们后面的值一定要小于等于前面的值。 因此我们试着构建一个下降的序列。在这个下降的序列中 查找可以更改的f值,使得序列的值尽可能大。

? 具体过程:
i 1 2 3 4 5 6 7 8

389
第 1次 第 2次 389 389

207

155

300

299

170

158

65

207

第 3次
第 4次 第 5次 第 6次 第 7次 第 8次

389
389 389 389 389 389

207
300 300 300 300 300

155
155 299 299 299 299 (由于207<300<389,因此更新) (由于155<299<300,因此更新) 170 170 170 158 158 65

思考?
? 有些同学可能会问: – 对于每个f,为什么只保留一个数值呢? – 而对于该序列,为什么要保留较大的值呢? 1. 再回过头来看方程: f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 该式子表示找前面的一个最大f的符合条件的j,因此只要保 存符合条件的最大的j就可以了。 2. 在f值相同的情况下,保留较大的数显然更好。因为后面 的数若能跟较小的数构成下降序列也一定能能较大的数 构成下降序列,反之则不一定。例如207与300的f=2,但 207不能与299构成下降序列,而300则可以。
3. 因为生成的序列为有序序列,因此我们可以采用二分查 找的方法很快查找到更新的值,时间复杂度为O(n㏒n)

求导弹的最小覆盖
? 第二问很容易想到贪心法:那就是采取多次求最 长不上升序列的办法,然后得出总次数。 ? 上述贪心法不正确,很容易就能举出反例。 例如: “7 5 4 1 6 3 2” 用多次求最长不上升序列所有为 “7 5 4 3 2”、“1”、“6”共3套系统; 但其实只要2套,分别为: “7 5 4 1”与“6 3 2”。 ? 那么,正确的做法又是什么呢?

分析
? 上述问题的原因是若干次最优决策值和不 一定能推导出整个问题的最优。 ? 为了解决这个问题下面介绍一个重要性质:
– 最少链划分=最长反链长度

? 为了证明这个性质,需要了解离散数学中 偏序集的相关概念和性质以及偏序集的 Dilworth定理。

偏序集
? 偏序是在集合X上的二元关系≤(这只是个抽象符号,不是 “小于或等于”),它满足自反性、反对称性和传递性。 即,对于X中的任意元素a,b和c,有:
– 自反性:a≤a; – 反对称性:如果a≤b且b≤a,则有a=b; – 传递性:如果a≤b且b≤c,则a≤c 。

? 带有偏序关系的集合称为偏序集。 ? 令(X,≤)是一个偏序集,对于集合中的两个元素a、b,如果 有a≤b或者b≤a,则称a和b是可比的,否则a和b不可比。 ? 一个反链A是X的一个子集,它的任意两个元素都不能进 行比较。 ? 一个链C是X的一个子集,它的任意两个元素都可比。

定理
? 在X中,对于元素a,如果任意元素b,都有a≤b, 则称a为极小元。 ? 定理1:令(X,≤)是一个有限偏序集,并令r是其 最大链的大小。则X可以被划分成r个但不能再少 的反链。 ? 其对偶定理称为Dilworth定理: 令(X,≤)是一个有限偏序集,并令m是反链的最 大的大小。则X可以被划分成m个但不能再少的链。

? 虽然这两个定理内容相似,但第一个定理证明要 简单一些。此处就只证明定理1。

证明:设p为最少反链个数 (1)先证明X不能划分成小于r个反链。由于r是最大 链C的大小,C中任两个元素都可比,因此C中任 两个元素都不能属于同一反链。所以p>=r。 (2)设X1=X,A1是X1中的极小元的集合。从X1中删 除A1得到X2。注意到对于X2中任意元素a2,必存 在X1中的元素a1,使得a1<=a2。令A2是X2中极小 元的集合,从X2中删除A2得到X3……,最终会有 一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的 反链的划分,同时存在链a1<=a2<=…<=ak,其中ai 在Ai内。由于r是最长链大小,因此r>=k。由于X 被划分成了k个反链,因此r>=k>=p。 (3)因此r=p,定理1得证。

解决
? 要求最少的覆盖,按照Dilworth定理 ? 最少链划分 = 最长反链长度 所以最少多少套系统 = 最长导弹高度上升 序列长度。
? 知道了怎样求最长不上升算法,同样也就 知道了怎样求最长上升序列。 ? 时间复杂度O(n㏒n)。



更多相关文章:
堆排序及算法分析
因此 最好或者最坏情况下, 堆排序的运行时间都是 O(nlogn)。 而且堆排序还是原地算法 (in-place algorithm)。 结尾如果不太了解 O,Θ 等渐进符号的,可以参考...
NOIP范围内的DP算法
由于大家都很熟悉了,加上今年来 NOIP 导弹拦截和过河 导弹拦截 过河。 出了好几回,这里不做多说。 特别留意: 1.不降(升)序列的 O(nlogn)算法。 (http:/...
算法分析知识整理
<=lognn=nlogn 任何指数形式 > 任何多项式形式 任何多项式形式 > 任何对数形式 ...(nlogba) d>logba d= logba d<logba Merge 算法处理 n 个元素 merge 的...
Divide and Conquer(卜东波计算机算法作业题3)
排序不具 备两两比较的功能, 可以用冒泡思想和选择排序思想,这样求逆序数的复杂度是 2 O(n ),而利用归并排序思想求逆序对数的算法复杂度可以降低到 O(nlogn)...
算法设计与分析复习题目及答案
D、回溯法 14.哈弗曼编码的贪心算法所需的计算时间为( A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 15.分支限界法解最大团问题时,活结点表的组织形式...
算法设计习题
= Θ(nlogn) 2. 设计一个算法,求给定 n 个元素的第二大元素,并给出算法在最坏情况下使用的比较次 数。 (复杂度至多为 2n-3)算法: Void findsecond(...
1、算法分析复习题目及答案
47.背包问题的贪心算法所需的计算时间为( A、O(n2n) 48、广度优先是( A、分支界限法 49、舍伍德算法是( A、分支界限算法 A B、O(nlogn) C、O(2n) D、...
算法分析考试题
其中,贪心算法部分只有一重循环影响时间复杂度,其时间复杂度为 O(n):而排序算法的 时间复杂度为 O(nlogn)。因此,综合来看算法的时间复杂度为 O(nlogn)。 c、...
算法分析习题参考答案第五章
returnMaxSubSum ( a, 1, n) ; } 该算法所需的计算时间T(n)满足典型的分治算法递归分式 T(n)=2T(n/2)+O(n),分治算法的时间复杂度为 O(nlogn) 3)...
2009-2010学年第二学期《计算机算法设计与分析》试卷A-...
n , f(n)=n, ∴T(n) =Θ (nlogn) 4 2. (15 分)设 n 后问题的显约束条件是两个皇后不能在同一行及同一列,求解 n 后问题的递归的回溯算法如下。...
更多相关标签:
算法训练 拦截导弹    排序算法nlogn    导弹拦截    弹道导弹为什么难拦截    洲际导弹可以拦截吗    美日试射新型拦截导弹    导弹拦截系统    导弹拦截问题    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图