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

Для моей проблемы вы выбираете до 24 предметов из пула, возможно, 5-10 000 предметов. Другими словами, мы генерируем конфигурации.

Число 24 происходит из категорий элементов, каждый элемент связан с определенным местом установки, элемент из местоположения 1 не может быть установлен в местоположении 10, поэтому я организовал свой ассоциативный массив для организации данных в группы. Каждый элемент выглядит так:

$items[9][] = array("id" => "0", "2" => 2, "13" => 20);

Где первый параметр ( $item[9] ) сообщает вам место, в котором это разрешено. Если вы хотите, можно подумать о том, что вы не можете установить шину на месте для выхлопной трубы.

Элементы хранятся в базе данных MySQL. Пользователь может указать ограничения для решения, например, атрибут 2 должен иметь конечное значение 25 или более. Они могут иметь несколько конкурирующих ограничений. Запросы извлекают элементы, которые имеют какое-либо значение для рассматриваемых атрибутов (неопределенные атрибуты сохраняются, но мы не делаем с ними никаких расчетов). Затем PHP-скрипт исключает любые избыточные варианты (например, если элемент 1 имеет значение атрибута 3, а элемент 2 имеет значение атрибута 5, при отсутствии другого
ограничение вы бы никогда не выбрали пункт 1).

После того, как вся обработка произошла, получите ассоциативный массив, который выглядит следующим образом:

$items[10][] = array("id" => "3", "2" => 2, "13" => 100);
$items[10][] = array("id" => "4", "2" => 3, "13" => 50);
$items[9][] = array("id" => "0", "2" => 2, "13" => 20);
$items[9][] = array("id" => "1", "2" => -1, "13" => 50);

Я разместил полный пример данных на эта пастиновая ссылка. Есть основания полагать, что я могу быть более ограниченным в отношении того, что я принимаю в набор данных, но даже при ограничении в 2 элемента на вариант есть проблема.

В значении array () идентификатор является ссылкой на индекс элемента в массиве, а другие значения являются парами идентификатора атрибута и значения. Так $items[10][] = array("id" => "3", "2" => 2, "13" => 100); означает, что в местоположении 10 есть элемент с идентификатором 3, который в качестве значения 2 в атрибуте 2 и значением 100 в атрибуте 13. Если это помогает думать, что элемент идентифицируется парой, например (10,0), это элемент 0 в местоположении 10.

Я знаю, что я не конкретен, есть 61 атрибут, и я не думаю, что это меняет структуру проблемы с тем, что они представляют. Если мы хотим, мы можем рассматривать атрибут 2 как вес, а атрибут 13 как стоимость. Проблема, которую пользователь хочет решить, может заключаться в том, чтобы создать конфигурацию, в которой вес точно равен 25, а стоимость минимизирована.

На оборотной стороне математики в конверте говорится, что приблизительная оценка, если было только 2 варианта на одно местоположение, составляет 2 ^ 24 варианта x размер записи. Предполагая, что 32-разрядное целое число может быть закодировано для представления одной записи, мы рассматриваем 16,777,216 * 4 = 67,108,864 байта памяти (полностью игнорируя издержки структуры данных), и нет никаких оснований полагать, что любое из этих предположений будет быть действительным, хотя алгоритм с верхней границей памяти в области 67 мегабайт будет приемлемым объемом памяти.

Нет особой причины придерживаться этого представления, я использовал ассоциативные массивы, так как у меня есть переменное число атрибутов, которые можно использовать, и я решил, что это позволит мне избежать большого разреженного массива. Выше «2» => 2 фактически означает, что отфильтрованный атрибут с идентификатором # 2 имеет значение 2, и аналогично значение атрибута 13 равно 100. Я рад изменить свою структуру данных на нечто более компактное.

У меня была мысль, что у меня есть критерии оценки, которые я могу использовать, чтобы отбросить большинство промежуточных конфигураций. В качестве примера, я могу вычислить 75 * «значение» 2 «» + 10 * «значение» 13 «, чтобы обеспечить относительный вес решений. Другими словами, если не было никаких других ограничений для проблемы, каждое значение улучшение на 1 атрибута 2 стоит 75, а каждое значение улучшения атрибута 13 стоит 10. Продолжая идею автомобильной детали, подумайте о ней, как о покупке стандартной детали и предложении машинисту изменить ее в соответствии с нашими спецификациями.

Одна проблема, которую я вижу при отбрасывании конфигураций слишком рано, состоит в том, что весовая функция не учитывает ограничения, такие как «конечный результат должен иметь значение« 2 », которое равно ровно 25». Так что хорошо, если у меня полная конфигурация из 24 элементов, я могу пройти через цикл ограничений, отбросить решения, которые не совпадают, и, наконец, ранжировать оставшиеся решения по функции, но я не уверен, что есть действительный линия мысли, которая позволяет мне выбросить решения раньше.

У кого-нибудь есть предложения о том, как двигаться вперед? Хотя решение, не зависящее от языка, прекрасно, я реализую на PHP, если есть какая-то соответствующая языковая функция, которая может быть полезна.