algorithm - 在列表中查找元素集，元素只能使用一次 - 如何处理算法

Question

我有以下列表

Cards: [B1 G1 O1 R1 G2 G3 R4]
Sets:  [G1 G2 G3]
Sets:  [B1 G1 O1 R1]

一组可以是相同颜色的卡片，但顺序或值(value)相同但颜色不同的卡片

我的排序算法即将结束，这就是我遇到问题的地方。

目标是打出尽可能多的牌。我创建的 AI 可以找到集合。我的问题是我不确定如何使用算法来帮助 AI 做出正确的决定。

如果它首先播放最大的 Set[B1 G1 O1 R1]，那么它将无法播放 Set[G1 G2 G3]。

当然如果它先播放set[G1 G2 G3]，那么它就能播放[B1 O1 R1]

当我到达这么小的列表时。我怎样才能计算出人工智能的最佳路径？任何帮助将不胜感激..

Answer 1

这是一种呈指数增长的方法，因此它只适用于一小部分卡片。它可能对您来说足够了，或者它可能指出了更好的解决方案，所以我想我应该把它写下来。

创建一个图，其节点是可以组成的集合。所以在你的情况下，节点是:

{G1,G2,G3} {G1,G2} {G2,G3} {B1,G1,O1,R1} {B1,G1,O1} {B1,G1,R1}, {B1,O1,R1} {G1,O1,R1} {B1,G1} {B1,O1} {B1,R1} {G1,O1} {G1,R1} {O1,R1}

现在，如果这两个集合是兼容的选择，即它们没有交集，则将两个节点与一条边连接起来。所以你图中的边是

{G1,G2,G3} -- {B1,O1,R1} 
{G1,G2,G3} -- {B1,O1}
{G1,G2,G3} -- {B1,R1}
{G1,G2,G3} -- {O1,R1}
{G1,G2} -- {B1,O1,R1}
{G1,G2} -- {B1,O1}
{G1,G2} -- {B1,R1}
{G1,G2} -- {O1,R1}
{G2,G3} -- everything after it
{B1,G1,O1,R1} -- nothing after it 
same for all the 3 element subsets from there on 
{B1,G1} -- {O1,R1} 
{B1,O1} -- {G1,R1} 
{B1,R1} -- {G1,O1}

您现在的目标是在该图中找到最大的派系，其中派系是相互兼容的集合……派系中的每对节点之间都有一条边。您可以使用一些库来查找最大派系，但它或多或少归结为蛮力搜索(CLIQUE 是 NP-hard)。图书馆至少会为您节省一些打字时间。其实你要的是最大clique，clique的值是节点权值的总和，其中一个节点的权值是该节点对应的集合中元素的个数。派系库将为您找到最多的派系。

可能有更好的方法，但这就是我现在所拥有的。