注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

偏序集的Dilworth定理学习  

2009-10-18 08:58:36|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

导弹拦截是一个经典问题:求一个序列的最长不上升子序列,以及求能最少划分成几组不上升子序列。第一问是经典动态规划,第二问直接的方法是最小路径覆盖, 但是二分图匹配的复杂度较高,我们可以将其转化成求最长上升子序列,其最大值即等于不上升子序列的最小划分数。这就涉及到组合数学中偏序集的 Dilworth定理。(第二问的贪心方法其实就是这个定理的证明过程)

其中第一问和第二问都可以用o(nlogn)的算法解决:

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[100],f[100],g[100];

int main(){

    freopen("lmis.in","r",stdin);

    freopen("lmis.out","w",stdout);

    int n,i;

    scanf("%d",&n);

    memset(g,0x7f,sizeof(g));

    memset(f,0,sizeof(f));

    for(i=0;i<n;i++)

      scanf("%d",&a[i++]);

    for(i=0;i<n;i++){

            int k=lower_bound(g+1,g+n,a[i])-g;

            f[i]=k+1;

            g[k+1]=a[i];

    }

    printf("%d\n",*max_element(f,f+n));

    return 0;

}

 

附:memset(arr,0x7F,sizeof(arr)); //set int to 2139062143

     memset(arr,0x80,sizeof(arr)); //set int to -2139062144
     memset(arr,0x7F,sizeof(arr)); //set double to 1.38242e+306
     memset(arr,0xFE,sizeof(arr)); //set double to -5.31401e+303

先介绍一下偏序关系:

偏序是在集合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不可比。



在X中,对于元素a,如果任意元素b,由b≤a得出b=a,则称a为极小元。

一个反链A是X的一个子集,它的任意两个元素都不能进行比较。

一个链C是X的一个子集,它的任意两个元素都可比。



下面是两个重要定理:

定理1 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。

其对偶定理称为Dilworth定理:

定理2 令(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非空而X(k+1)为空。于是A1,A2,…,Ak就是X的反链的划分,同 时存在链a1<=a2<=…<=ak,其中ai在Ai内。由于r是最长链大小,因此r>=k。由于X被划分成了k个反链,因此 r>=k>=p。因此r=p,定理1得证。



回过头来看导弹拦截第二问。我们定义偏序关系≤:a≤b表示a出现不迟于b且a的值不小于b的值。这个偏序集的最长反链即最长上升子序列,它的不上升子序列是偏序集的链。由Dilworth定理可知,不上升子序列的最小划分数=最长上升子序列的长度。



p.s. 这里的贪心方法是,每次选出所有的在它前面没有大于或等于它的数作为一组。其实我们每次选的是偏序集的最小元,因此我们最终得到的答案就是上面的k。由r<=p及r>=k>=p可以得到r=k=p,因此贪心正确。

参考资料:《Introductory Combinatorics》Fourth Edition,Richard A. Brualdi

参考:http://www.608088.com/show-2730-1.html

  评论这张
 
阅读(1440)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017