我正在尝试解决一个问题,其中我有像这样的对:
A C
B F
A D
D C
F E
E B
A B
B C
E D
F D
我需要将它们分成 3 组,其中我必须从该列表中找到匹配的三角形。基本上我需要一个结果,如果它可能或不对集合进行分组。
所以可能的组是(ACD
和BFE
),或者(ABC
和DEF
)和这个集合是可分组的,因为所有字母都可以分组为 3 个一组,并且没有一个被遗漏。
我制作了一个脚本,我可以在其中实现少量输入,但对于大量输入,它变得太慢了。
我的逻辑是:
make nested loop to find first match (looping untill I find a match)
> remove 3 elements from the collection
> run again
我一直这样做,直到我没有信件。由于可能有不同的组合,我从不同的字母开始多次运行此程序,直到找到匹配项。
我可以理解,这给我的循环顺序至少为 N^N
并且可能会变得太慢。有没有更好的逻辑来解决这些问题?这里可以用二叉树吗?
最佳答案
这个问题可以建模为图 Clique cover problem .每个字母都是一个节点,每一对都是一条边,您希望将图形划分为大小为 3(三角形)的vertex-disjoint cliques。如果您希望分区具有最小基数,那么您需要一个最小团覆盖。
实际上这将是一个 k-clique 覆盖问题,因为在 clique 覆盖问题中你可以有任意/不同大小的 cliques。
关于以 3 为一组对项目进行分组的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40193648/