a是具有多个“类别”(b)的对象,例如a1具有三个类别b1、b2和b3。 问题在于将类别的数量(可能会变得相当大)减少到总是一起出现的组中。这是一个“最大公共子集”的问题。
例如,给定以下数据集:
a1{ b1,b2,b3 }
a2{ b2,b3 }
a3{ b1,b4 }
我们可以发现b2和b3总是一起出现。
b23 = {b2,b3}
..我们可以将类别集合减少到这个:
a1{ b1, b23 }
a2{ b23 }
a3{ b1,b4 }
所以,我的问题是找到一些算法来解决这个问题。我已经开始研究最长公共子序列问题,这可能是一个解决办法。例如,像这样重复地对类别进行分组:b' = LCS(set_of_As)
,直到遍历完所有类别。然而,这还不够完整。我必须以某种方式限制输入域,以使其成为可能。
我是否错过了一些显而易见的东西?你能指出任何问题领域的提示吗?有人认识到其他解决此类问题的方法吗?