2

故事：

我们公司很快就要出去了。对于我们在度假村的住宿，我们的每两个同事将共用一个房间。我们的管理员助理已经收集了我们对与谁共享房间的偏好，现在她必须决定如何安排房间以尽量减少所需的房间数量。每个人都将被安排与他或她想要的人共享一个房间。比如只有同事，Allen想和Bob或者Chris合住一个房间，Bob想和Chris合用，Chris想和Allen合用；那么唯一的结果将是：Allen 和 Chris 共用一个房间，而 Bob 单独使用一个房间，总共需要 2 个房间。

问题：

将故事简化为算法问题（尽管这可能不是最好的简化）：我们在图中有几个节点，并且节点相互连接。我们只关心双向连接的节点，所以现在我们有一个无向图。如何将无向图中的节点分组，以便 1）任何组最多包含 2 个节点，2）如果一个组包含 2 个节点，则节点是连接的，3）最小化组的数量。

算法：

我脑海中浮现的是贪婪地解决这个问题。在排列的每一步中，只需移除一个孤立节点或两个节点，以使图中剩余的边数最大化。通过反复这样做，我们最终会找到解决方案。

请以最佳方式解决问题（我不是在寻找尝试所有组合的方法）或证明上述贪心算法是最佳的。

4

2 回答 2

3

您正在解决的问题是在图中找到最大匹配。这意味着找到不共享顶点的最大边数。在您的情况下，这些边将对应于共享房间，其余顶点将是单人房间。

可以使用Blossom 算法在多项式时间内找到最大匹配。

于 2013-04-17T14:07:45.750 回答
0

这是 Haskell 中的一些粗略的东西。函数“pairs”列出了所有具有共同偏好的配对，以及没有共同伴侣的人（与“”配对）。函数“choose”从配对列表中返回配对。如果一对中的两个人还与另一个（相同的）第三人配对，“选择”将从对列表的其余部分中删除这两个人，并且结果对清空。所需房间的数量等于最终列表的长度。

输出（最好有更多不同的例子来测试）：

*Main> choose graph
[["Chris","Allen"],["Bob","Isaak"]]

*Main> choose graph1
[["Allen","Chris"],["Bob",""],["Dave",""],["Chris","Max"]] --four rooms
  would be needed, although Chris appears in two pairs (..figured they can 
  decide later who stays where.)

*Main> choose graph2 --example given by Dante is not a Geek
[["Allen","Chris"],["Bob",""]]

代码：

import Data.List (group, sort, delete)

graph = [("Chris",["Isaak","Bob","Allen"]) --(person,preferences)
        ,("Allen",["Chris","Bob"])
        ,("Bob",["Allen","Chris","Isaak"])
        ,("Isaak",["Bob","Chris"])]

graph1 = [("Allen",["Bob","Chris"]), ("Bob",["Chris"]), ("Dave",[])
         ,("Chris",["Allen", "Max"]), ("Max", ["Chris"])]

graph2 = [("Allen",["Bob","Chris"]), ("Bob",["Chris"]), ("Chris",["Allen"])]

pairs graph = pairs' graph [] where
  pairs' []                 result = concat result
  pairs' (x@(person1,_):xs) result
    | null test = if elem [[person1, ""]] result 
                     then pairs' xs result
                     else pairs' xs ([[person1,""]]:result)
    | otherwise = 
        pairs' xs ((filter (\[x,y] -> notElem [y,x] (concat result)) test):result)
   where isMutual a b = elem (fst a) (snd b) && elem (fst b) (snd a)
         test = foldr comb [] graph
         comb a@(person2,_) b = 
           if isMutual a x then [person1,person2]:b else b

choose graph = comb paired [] where
  paired = pairs graph
  comb []             result = filter (/=["",""]) result
  comb (x@[p1,p2]:xs) result 
    | x == ["",""] = comb xs result
    | test         = 
        comb (map delete' xs) (x:map delete' result)
    | otherwise    = comb xs (x:result)
   where delete' [x,y] = if elem x [p1,p2] then ["",y]
                            else if elem y [p1,p2] then [x,""] 
                            else [x,y]
         test = if not . null . filter ((>=2) . length) . group 
                       . sort . map (delete p2 . delete p1) 
                       . filter (\y -> y /= x && (elem p1 y || elem p2 y)) $ paired
                   then True
                   else False
于 2013-04-18T05:03:46.350 回答