我有一个我正在努力解决的组合优化问题。问题的技术细节比较繁琐，所以我把事情翻译成一个虚构的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 数量？
最佳答案
这是一个组合优化问题，而不是机器学习问题。
实际上，这是一个着色问题:创建一个图 G ，其中每个顶点对应一个人。如果两个人 (u, v) 和 u 彼此不喜欢，则存在边 v。您现在要求最小的 k 使得 G 是 k -colorable。着色 c(v) 告诉您 v 坐在哪张 table 上。
现在你只需要 pick an algorithm 。
关于cluster-analysis - "Frenemies"，或如何让青少年在生日聚会上开心，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15956728/