时间戳

首页 > 解决方案 > 在列表中查找元素集，元素只能使用一次 - 如何处理算法

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

问题描述

我有以下列表

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

一组可以是相同颜色但连续的牌，也可以是相同数值但不同颜色的牌

我的排序算法快要结束了，这就是我遇到麻烦的地方。

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

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

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

当我到达这么小的列表时。如何计算 AI 的最佳路径？任何帮助，将不胜感激..

标签： algorithmlistsortingrecursionset

解决方案

这是一种呈指数级增长的方法，因此它仅适用于一小部分卡片。它可能对你来说已经足够了，或者它可能指向更好的解决方案，所以我想我会写下来。

创建一个图，其节点是可以制作的集合。所以在你的情况下，节点是：

{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）。图书馆至少可以为您节省一些打字时间。实际上，你想要的是一个最大团，其中一个团的值是节点权重的总和，其中一个节点的权重是该节点对应的集合中的元素个数。派系库将为您找到最大的派系。

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

推荐阅读