qq_29333729 2019-06-24 10:43 采纳率: 0%
浏览 475
已结题

查找满足多个互斥条件的分组方法

问题:有n个元素a、b、c、d、e、f...,要求将这些元素拆分成m个分组,同时满足条件:集合{a,b,c,d},{b,d,f},{c,e}....内的元素不能在同一个分组。

默认n和m满足分组条件,1个元素可以出现在多个条件集合内;结果不唯一,只要给出1个较优结果,即各个分组内元素数量较均匀。

我的能想到的方法是,先整理出每个元素与其他元素的互斥关系,比如a不能与{b,c,d}在同1分组,b不能与{a,c,d,f}在同1分组...,然后将每个元素互斥条件最多的,从多到少随机分配在m个分组内,每次随机验证是否满足条件,全部随机完成返回结果。

但是这个方法比较暴力,而且不能给出最优解,计算开销也比较大。

求算法大神给个思路或意见。

  • 写回答

1条回答

  • bighero4 2019-06-24 15:33
    关注

    如果是计算最小要分成几组,可以使用拓扑排序,这里分成指定的组数,需要改进下。建议去看看NOIP2013普及复试中的第4题车站分级的问题,或许那里的解题思想可以借用。

    评论

报告相同问题?

悬赏问题

  • ¥15 fluent的在模拟压强时使用希望得到一些建议
  • ¥15 STM32驱动继电器
  • ¥15 Windows server update services
  • ¥15 关于#c语言#的问题:我现在在做一个墨水屏设计,2.9英寸的小屏怎么换4.2英寸大屏
  • ¥15 模糊pid与pid仿真结果几乎一样
  • ¥15 java的GUI的运用
  • ¥15 Web.config连不上数据库
  • ¥15 我想付费需要AKM公司DSP开发资料及相关开发。
  • ¥15 怎么配置广告联盟瀑布流
  • ¥15 Rstudio 保存代码闪退