回溯/分治限界法

 问题描述

给定1个1000行×20列的0-1矩阵,对于该矩阵的任意1列,其中值为1的元素的数量不超过10%。

设有两个非空集合A和B,

每个集合由矩阵的若干列组成。集合A和B互斥是指对于矩阵的任意一行,同时满足下列2个条件:

1)若A中有一个或多个元素在这一行上的值是1,则B中的元素在这一行全部是0;

2)若B中有一个或多个元素在这一行上的值是1,则A中的元素在这一行全部是0。

请你设计一个算法,找出一对互斥集合A和B,使得A和B包含的列的总数最大。

问题分析

首先,我们需要弄明白互斥的一些性质,一个集合A对应一个集合B,当扩充集合A的时候,B中元素的个数一定小于等于原先的个数,原因是加入往A中加入元素使得与A互斥的条件得到加强满足条件的列的数量必然小于等于原来的数量,不过有一点值得注意的是,数量是小于等于,所以当我们在搜索集合A的过程中,并不能通过当前解的值来判断当前状态是否为达到最优值,因为如果之后再往A里加元素的时候B中元素的数量是可能不变的,甚至可能超过当前最优解的,所以我们可以使当前的解与未选择的列的和与当前最优值比较,当小于当前最优值的时候,这个子树就没必要继续往下搜索了.

算法设计

为了方便处理,将1000*20的矩阵进行转置20*1000的矩阵,这样可以方便处理,同时,为了提高效率,对每一行进行了预处理,找出与每一列互斥的其他列将他们存到一个集合中,当往A中加入元素的时候,求集合B与加入新的列的互斥集合的交集.这样就形成了新的集合B.当集合B为空集的时候显然结果的不正确的,所以我们要注意排除这情况.当一个状态的集合B为空集的时候,这颗子树就没必要继续往下搜索了.这一步可以大大的提高算法的效率.

算法实现

 

 

运行结果

由于生成的矩阵较大,这里就不展示该01矩阵中包含1000个1以下为输出:

Leave a Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

本站所有文章均为原创,若需转载,请注明出处©twn29004 | 陕ICP备 20000896 网站备案号

总访问量:8764207    今日访问量:172    您是今天第:172 个访问者