4

我有一个我正在努力解决的组合优化问题。这个问题的技术细节很麻烦，所以我把事情翻译成一个虚构的甜蜜 16 岁生日派对。显然，青少年是 NP 困难的，但这与我试图解决的实际问题是分开的。

假设我有一个即将满 16 岁的儿子。他邀请所有朋友参加他的生日聚会，但并非所有朋友都彼此喜欢。事实上，我儿子的每个朋友都至少有一个不喜欢的人，有些人还有更多。如果一个或多个宣誓的“友敌”坐在同一张桌子上，这些“友敌”拒绝坐在同一张桌子上。我儿子向我提供了他所有邀请朋友的名单，还有谁不喜欢谁。这个信息是对称的（如果朋友 ​​A 不喜欢朋友 B，朋友 B 不喜欢朋友 A），但它不是传递的（如果朋友 ​​A 不喜欢朋友 B，但喜欢朋友 C，朋友 C 仍然是随意喜欢或不喜欢朋友 B)。我的问题是：如何确定满足没有两个“友敌”的条件的最小表数

4

2 回答 2

1

这是一个组合优化问题，而不是机器学习问题。

实际上，这是一个着色问题：创建一个图G，其中每个顶点对应一个人。(u, v)如果两个人彼此不喜欢u，则存在优势。v您现在要求的是最小的k-colorable 。着色告诉您坐在哪张桌子上。Gkc(v)v

现在你只需要选择一个算法。

于 2013-04-11T20:15:19.017 回答
0

对我来说，这听起来更像是一个受约束的优化问题，而不是机器学习问题。我将建模如下。

  • 每个朋友一个变量，值是表格，
  • 表格的附加约束（根据列表）friendX !- friendY表示这两个不能坐在同一张桌子上。

这是您可以使用您选择的约束求解器解决的基本模型（我推荐Minion）。您可以最小化最大表数（这将需要一些额外的约束），或者只是尝试找到具有给定表数（即变量域中的值）的解决方案，直到找到不存在解决方案的解决方案.

根据问题的大小（即朋友和桌子的数量），这可能有效，也可能无效。您可能需要考虑的是问题中的对称性（即 A 表上的人可以移动到 B 表，反之亦然，这仍然是一个解决方案），这可能会因额外的约束而被打破。

于 2013-04-11T19:23:52.843 回答