Найти наборы элементов в списке, элементы можно использовать только один раз - как подойти к алгоритму

Question

У меня есть следующий список

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

В наборе могут быть карты одного цвета, но последовательные или карты одного и того же значения, но другого цвета

Я достигКонец моего алгоритма сортировки и вот где у меня проблемы.

Цель - сыграть как можно больше карт.ИИ, который я создал, может найти наборы.Моя проблема здесь в том, что я не уверен, как я могу использовать алгоритм, чтобы помочь ИИ принять правильное решение.

Если он сначала сыграет самый большой 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).Библиотека, по крайней мере, сэкономит вам печатать.Фактически, вам нужна максимальная клика, где значение клики - это сумма весов узлов, где вес узла - это количество элементов в наборе, соответствующих узлу.Библиотека клик найдет для вас максимальное количество кликов.

Возможно, есть лучший способ, но это то, что у меня есть сейчас.