如何最有效地分配房间？

Question

故事：

我们公司即将开业。对于我们住在度假村，我们每两个同事将共用一个房间。我们的管理员助理收集了我们与谁共用房间的偏好，现在她必须决定如何安排房间以尽量减少所需的房间数量。每个人都将被安排与他或她想要的人分享一个房间。例如，只有同事，艾伦想与鲍勃或克里斯分享一个房间，鲍勃想与克里斯分享，克里斯想与艾伦分享;那么唯一的结果就是：艾伦和克里斯分享一个房间，而鲍勃单独使用一个房间，总共需要2个房间。

问：

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

算法：

什么是我的头是贪婪地解决问题。在每个安排步骤中，只需删除一个孤立节点或两个节点，以使图中边缘的数量最大化。通过反复这样做，我们将最终找到解决方案。

请以最佳方式解决问题（并且我不想尝试所有组合）或者证明上述贪婪算法是最优的。

Answer 1

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

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

Answer 2

这是Haskell中粗糙的东西。函数“对”列出所有具有相互偏好的对，以及没有相互伙伴的人（与“”配对）。函数“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