18

今天有个朋友问我一个关于作业问题的问题。我找到了一个非常简单的解决方案，但我觉得它可以变得更简单和更快。您的帮助将不胜感激。

问题：假设我有N个人，我需要将他们分配到M个建筑物中，每个建筑物可以容纳K个人。不是所有的人都愿意住在一起，所以我有一个 N*N 单元格的矩阵和一个 1 来标记愿意住在一起的人。如果一个单元格包含 1，则意味着 I 和 J 可以住在一起。显然，矩阵围绕主对角线对称。

我的解决方案如下（伪代码）：

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
    int[] freePeople = findFreePeople(people);
    if(freePeople) = 0 
    {
        return people;
    }

    foreach(int person in freePeople)
    {
        for(int buildingIndex=0 to numBuildings)
        {
            if( CheckIfPersonFitsInBuilding(...) )
            {
                int[] tempPeople = people.Copy();
                tempPeople[person] = buildingIndex;
                int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
                if(result != null)
                {
                    return result;
                }
            }
        }
    }
    return null;
}

我只是使用递归涵盖了所有可能的安排。我觉得这可以大大优化，我不是在谈论启发式方法，而是一种复杂性要低得多的解决方案。

  1. 是否存在与此类似的正式众所周知的问题？
  2. 有更好的算法吗？

我认为这可能与稳定的婚姻问题有关，但我不确定。

4

3 回答 3

25

通过将图分解为团的 NP 完全问题（团覆盖问题）的简化，这个问题被称为 NP-hard 。

首先，一些术语和讨论。图中的集团是一组 k 个不同的节点，使得每个节点都连接到集团中的其他节点。图中的独立集是一组 k 个不同的节点，使得没有两个节点相互连接。如果您获取任何图 G，然后在缺少一条边时引入边并删除以前存在的所有边，您将获得原始图的补图。这意味着在初始图中找到一个团的问题等价于在补图中找到一个独立集。

这很有趣的原因是，在你描述的问题中，你得到了一张人的图表，其中每条边都表示“这两个人不能住在一起”。因此，您可以将您描述的问题视为试图找到一种方法将图分解为 k 个子图，每个子图都是一个独立的集合。如果你构建这个图的补集，你会得到所有可以被放在一起的人的图。在这种情况下，您希望将组分解为 k 个组，这些组都是派系。

已知以下问题是 NP 完全问题：

给定一个图和一个数 k，你能把图中的节点分成 k 个团吗？

我们可以在多项式时间内将此问题简化为您的问题，表明您的问题是 NP 难的。构造很简单——给定初始图 G 和数 k，首先构造 G 的补集。这意味着如果你可以将补集分解为 k 个独立集合，那么原始图 G 可以分解为 k 个团（因为派系和独立集之间的对偶性）。现在，获取这个新图并将其转换为一组人，每个节点一个人，如果他们的节点在原始图中连接，则两个人不能被放置在同一个房间中。现在，有一种方法可以将这些人分配到 k 个房子中，如果 G 的补集可以分解为 k 个独立集，如果 G 可以分解为 k 个派系。最后，集团覆盖的已知 NP 完全问题可以在多项式时间内简化为您的问题，因此您的问题是 NP 难的。为了确保任何独立的集合都可以放入一个房子，只需将每个房间的最大容量设置为 n，即图中的节点数。这允许任何独立的装置被安置在任何房间中。

由于您的问题是 NP 难题，因此除非 P = NP，否则不能有多项式时间解决方案。因此，众所周知，它没有多项式时间算法，您的回溯递归很可能是最佳解决方案。

希望这可以帮助！

于 2012-06-23T20:45:57.777 回答
13

templatetypedef很好地证明了为什么这个问题是 NP-hard 并且没有（已知的）多项式时间解。

然而，与许多 NP-hard 问题一样，这并不意味着您无法在实践中有效地解决它，或者您无法改进暴力解决方案。

特别是，您应该研究约束满足问题。它们是一类更一般的问题，准确地描述了您要解决的问题：给定一组约束，满足所有约束的值是什么？

AIMA一书有一个非常好的章节，介绍了如何解决这些类型的问题。我建议你阅读一下，因为那里有很多很好的信息，而且很容易获得，因为这本书是为本科生设计的。我会在这里给你一些重要的想法：

主要问题是：

  • 在你的递归中下一个应该分配哪个学生？
  • 应该以什么顺序为该学生考虑建筑物？

这里有两个启发式方法：

  • 最小剩余值(MRV) 启发式：在递归中选择下一个分配给建筑物的学生时，选择剩下的选择最少的学生。
  • 最小约束值(LCV) 启发式：在决定要看什么学生后，分配排除其余学生选择最少的建筑物

对于 MRV 启发式，通过选择对其他学生有最大限制的学生来打破联系。这些启发式方法背后的想法是您希望选择最有可能成功的搜索路径 (LCV)。但是给定一个特定的搜索路径，您希望尽早失败，以减少在该路径上花费的时间 (MRV)。

此外，您应该使用更高级的搜索算法（如AC-3），而不是使用基本的前向检查来进行简单递归。

鉴于约束满足问题在许多软件工程应用程序中如此普遍，因此已经有大量的开放库可以有效地解决这些问题。当然，这是因为您要解决的问题是针对现实世界的应用程序，而不是某种家庭作业。

于 2012-06-27T20:25:11.953 回答
4

解决这些问题的一个好方法是使用有限域的约束求解器。

例如，使用 GNU-Prolog：

solve(Out):-
    People = [Jon, Mary, Alice, Smith, Dick, George, Betty, Lucy],
    fd_domain(People, 0, 3),    % people lives in buildings 0 to 3.
    fd_atmost(4, People, 0),    % at most, 4 people may live in building 0
    fd_atmost(3, People, 1),    % at most, 3 people may live in building 1
    fd_atmost(2, People, 2),    % etc.
    fd_atmost(1, People, 3),
    Jon   #\= Mary,             % Jon hates Mary
    Alice #\= Smith,            % etc.
    Betty #\= Lucy,
    Jon   #\= Alice,
    Dick  #\= George,
    fd_labeling(People),        % iterate until an acceptable combination is found.
    People = Out.

:- solve(O), write(O), nl.

从复杂性的角度来看，这仍然是 NP 完全的。但是约束求解器可能会重新排序在标记步骤上执行分配的方式，以便尽早发现死角，从而导致更小的搜索树。

于 2012-06-24T00:41:29.627 回答