Матричная математика - Максимизация

Question

У меня есть фреймворк с указателем магических c имен карт. Столбцы имеют один и тот же индекс, в результате получается фрейм данных 1081 x 1081 для каждой карты в моей коллекции в паре с каждой другой картой в моей коллекции.

У меня есть код, который идентифицирует комбинации карт, которые go хорошо вместе. Например, «Каждый раз, когда вы берете карту» хорошо сочетается с картами «Взять карту». Я нахожу соединение этих двух карт и увеличиваю его значение на 1.

Теперь мне нужно найти максимальное значение для 36 карт.

Но как?

Случайный выбор карт бесполезен, есть 1,717391336 E + 74 потенциальных комбинаций. Я пробовал выбирать самые низкие значения, и это сокращает набор потенциальных комбинаций, но даже на 100 картах вы говорите о 1,977204582 E + 27 потенциалах.

Это должно было быть решено кем-то более умным, чем я - можешь указать мне правильное направление?

Answer 1

Как вы уже отметили, комбинаторика здесь не на вашей стороне. Есть 1081 выбор из 36 возможных наборов (биномиальный коэффициент), поэтому не может быть и речи о том, чтобы проверить все из них.

Я не знаю какого-либо практического решения, чтобы найти оптимальный набор для общего , то есть без знания матрицы 1081x1081.

Для приблизительного решения общей проблемы вы можете попробовать жадный подход, сохраняя историю n наборов после каждого шага, например, n = 1000.

Итак, вы должны начать с просмотра всех наборов с двумя картами, что составляет 1081 * 1080/2 комбинаций, найти значение в матрице для каждой и выбрать максимальное количество n.

На втором этапе для каждого из n сохраненных наборов, go через все возможные комбинации с третьей картой (и проверка на наличие повторяющихся наборов), т.е. проверка n * 1079 наборов и сохранение n максимальных наборов.

На третьем этапе проверьте n * 1078 наборов с четвертой картой и т. Д., И т. Д.

Конечно, это не даст вам оптимального решения для поколения Обычный случай, но, возможно, этого достаточно для вашей ситуации. Вы также можете взглянуть на историю, чтобы понять, как часто бывает, что лучший набор с шага x догоняет другой набор на шаге y> x. В зависимости от вашей матрицы это может происходить не так часто или даже никогда.