V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mutelog
V2EX  ›  程序员

[算法题] 结对编程最优配对问题

  •  1
     
  •   mutelog · 2017-10-15 19:49:14 +08:00 · 4492 次点击
    这是一个创建于 2356 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有 30 名程序员,两两配对,结对编程 (分成 15 组)。

    二维数组 profit[i][j] = k,表示程序员 i 和程序员 j 配对时的小组效率为 k,求使效率总和最大化时的最优配对。

    对于任意 i != j, profit[i][j] == profit[j][i]
    17 条回复    2017-10-16 12:54:04 +08:00
    karia
        1
    karia  
       2017-10-15 20:04:58 +08:00
    最大流
    karia
        2
    karia  
       2017-10-15 20:07:06 +08:00   ❤️ 1
    mutelog
        3
    mutelog  
    OP
       2017-10-15 20:07:19 +08:00
    @karia 能否更详细地描述下
    mutelog
        4
    mutelog  
    OP
       2017-10-15 20:08:15 +08:00
    @karia 感谢,可否描述下怎么建图
    karia
        5
    karia  
       2017-10-15 20:11:41 +08:00
    @mutelog 起点到 30 个人各有一条无限容量管道,30 个人到 30 个人的管道容量根据邻接矩阵建好,30 个人到终点各有一条无限容量管道
    然后愉快模板
    mutelog
        6
    mutelog  
    OP
       2017-10-15 20:13:45 +08:00
    @karia 这样建图恐怕不对吧,有可能出现 i 和 j 匹配,而 j 不和 i 匹配的情况
    karia
        7
    karia  
       2017-10-15 20:20:57 +08:00
    好像是有点问题,我再想想
    带权的二分图可能要用 KM 算法
    karia
        8
    karia  
       2017-10-15 20:28:28 +08:00
    是的,最大流有问题,因为这条边的流量要么满,要么 0
    https://en.wikipedia.org/wiki/Hungarian_algorithm
    KM 讲的是最小化问题,不过应该一样,大不了取负权
    XDXX
        9
    XDXX  
       2017-10-15 21:57:27 +08:00
    mutelog
        10
    mutelog  
    OP
       2017-10-15 22:12:52 +08:00
    @XDXX Stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element.
    这个是说两个等大小的集合互相匹配;但是题目里只有一个集合,集合里的任意两个元素都可以相互配对。
    似乎不能用稳定结婚问题来解决
    allinwonder
        11
    allinwonder  
       2017-10-15 22:33:01 +08:00 via iPhone   ❤️ 2
    @XDXX 这个完全不是一个 matching 的问题(我自己就是做 matching 研究的)。

    要么穷举所有的配对可能然后找最大值,要么贪心算法找近似最优解。

    这里应该有高手可能给你提供更好的剪枝方法的。
    karia
        12
    karia  
       2017-10-15 23:07:28 +08:00
    @allinwonder 意识到问题了 :(
    一旦掉坑里就很容易江化,最大流解决不了 A 配 B 时 B 也一定要配 A 的约束
    等 dalao 了
    skadi
        13
    skadi  
       2017-10-16 00:09:03 +08:00
    感觉似乎可以用 01 背包来解.

    每个人只能用一次,然后有费用.
    ytmsdy
        14
    ytmsdy  
       2017-10-16 00:11:09 +08:00 via iPhone
    做一个 BFS 就可以了。
    把它简化为一个快递员要送 n 个包裹,要去 n 个地方,两两之间的耗时都给出,问你着么样的路径耗时最短?
    这个网上就一堆答案了!
    starqoq
        15
    starqoq  
       2017-10-16 03:12:29 +08:00 via Android   ❤️ 3
    一般图最优匹配 带花树算法。搜论文
    Efficient Algorithms for Finding Maximal Matching in Graphs

    @karia 二分图都不对,任意两个程序员都能匹配,而不是说男的和女的匹配。

    @ytmsdy 这不是旅行商问题
    mutelog
        16
    mutelog  
    OP
       2017-10-16 08:03:13 +08:00 via iPhone
    @starqoq 感谢 找到一个题目 http://uoj.ac/problem/81 一般图最大权匹配
    resturlaub
        17
    resturlaub  
       2017-10-16 12:54:04 +08:00
    匈牙利算法
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3842 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 10:18 · PVG 18:18 · LAX 03:18 · JFK 06:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.