cluster-analysis - "Frenemies"，或如何让青少年在生日聚会上开心

Question

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

假设我有一个即将满 16 岁的儿子。他邀请所有 friend 参加他的生日聚会，但并非所有 friend 都彼此喜欢。事实上，我儿子的每个 friend 都至少有一个他们不喜欢的人，有的甚至更多。如果一个或多个发誓的“敌对”坐在同一张 table 上，这些“敌对”就拒绝坐在同一张 table 上。我儿子给我提供了他所有受邀 friend 的名单，还有谁不喜欢谁。这个信息是对称的(如果 friend ​​A 不喜欢 friend B， friend B 不喜欢 friend A)，但它不是可传递的(如果 friend ​​A 不喜欢 friend B，但喜欢 friend C， friend C 仍然是自由喜欢或不喜欢 friend B)。我的问题是:如何确定满足没有两个“敌人”坐在同一张 table 上的条件的最小 table 数量？

Answer 1

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

其实是一个着色问题:创建图形G ，其中每个顶点对应一个人。一条边(u, v)当两个人存在时 u和 v不喜欢对方。您现在要的是最小的 k使得 G是 k -可着色。上色c(v)告诉你哪个表的人v是坐在。

现在你只需要pick an algorithm .