来一份温柔 2019-11-12 12:29 采纳率: 0%
浏览 1336
已采纳

回溯法/分支限界法求解0-1矩阵的互斥集合问题

给定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包含的列的总数最大。

  • 写回答

2条回答 默认 最新

  • bobhuang 2019-11-12 17:17
    关注

    讲个思路:
    由于集合为任意列的组合,总共20列,所以用二进制位来表示比较方便计算。可以用32位整数来表示一个集合。
    题设的条件,从一个角度来理解,即每行或者A或者B,必须有一个全0的列组成的集合;对应的,另外一个集合是任意的,可以全0,可以含有1。

    对第i行来说,先分出为0的列的集合,记为C[i].
    初始时,A和B均为全集。
    对后续的每个i = [0 ~ 999],有两种选择:
    1. 这行选择A为全0,新的A取A和C[i]的交集,计算为 A = A & C[i], B不变。
    2. 这行选择B为全0, 新的B取B和C[i]的交集,计算为 B = B & C[i], A不变。
    用一个大小1000的数组记录当前每行的选择。

    如果此时A或B出现空集,则组合失败,回溯到上一个i。
    如果到达最后一个i=999,且A和B都不为空,则得到一个有效解。
    遍历完所有可能之后,取所有有效解中A和B的列总数最大的那个,作为最优解。

    特别的,对全是0的行,不需要进行计算。

    总的可能空间比较恐怖,有2的1000次方,但是计算中有几个优化计算的方法:
    1. 对全0的优化。
    2. 出现空集的优化。
    3. 当A和B的列数小于等于当前有效解时,不可能更有,也可以优化。

    最终计算时间可能不会很长。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 已采纳回答 8月30日

悬赏问题

  • ¥15 vue2(标签-chrome|关键词-浏览器兼容)
  • ¥15 python网络流自动生成系统 医学领域
  • ¥15 sql查询仓库里都有什么
  • ¥15 代码的修改,添加和运行完善
  • ¥15 krpano-场景分组和自定义地图分组
  • ¥15 lammps Gpu加速出错
  • ¥15 关于PLUS模型中kapaa值的问题
  • ¥15 关于博途V17进行仿真时无法建立连接问题
  • ¥15 机器学习教材中的例题询问
  • ¥15 求.net core 几款免费的pdf编辑器