Как сгенерировать все возможные двоичные матрицы nxm, где сумма каждой строки равна 1
Я работаю над заданием, в котором мне нужно назначить от 1 до 10 распределительных центров для всех штатов США. Я сделал модель в excel, чтобы рассчитать все затраты, и ясно, что цель задания - найти самый дешевый способ. У меня есть 50 строк (для каждого состояния) и 10 столбцов (для всех возможных местоположений DC). Моя модель основана на этой матрице, и если я изменю матрицу, сразу отобразятся затраты. Единственным ограничением является то, что каждое состояние обеспечивается ровно 1 контроллером домена.
Понятно, что я не могу сделать все возможные комбинации вручную, я попытался перевести свою модель в программу оптимизации (AIMMS), но это займет много времени, потому что я уже вставил модель Excel. Я подумал, что если бы у меня были все возможные матрицы (сгенерированные в R, Matlab или Python, мне все равно), я мог бы просмотреть их в своей электронной таблице и позволить программе прочитать стоимость, чтобы определить лучший выбор. Теоретически все состояния можно передать по 1 DC, максимум 10, поэтому для определения наилучшей нужны все возможные матрицы 1x50, 2x50, 3x50 ... 10x50.
Короче говоря, можно ли сгенерировать каждую бинарную матрицу nxm с общей суммой 1 в каждой строке предпочтительно в R или иначе в Matlab или Python?
Так что это в основном Задача коммивояжера. Это нерешенная математическая проблема, но есть некий эвристический и вероятностный алгоритм, который может дать хороший результат.
Ответы 1
TLDR: №.
Давайте рассмотрим самый простой пример: 2 СН. Ваши возможные строки будут:
(1,0)(0,1)
Теперь вы хотите построить все возможные матрицы 2x50. Их количество 2^50 (2 возможных ряда в 50 рядах). Он равен:
1125899906842624
Предположим, что каждая матрица хранит 100 байт. Что все матрицы 2x50 будут хранить:
(2**50) * 100 / 1024 / 1024 / 1024 / 1024 = 102400 терабайт данных.
И на их обработку всех (в самых оптимистичных результатах для обычных компьютеров) уйдет время, равное:
(2**50) / 10**9 / 60 / 60 = 312 часов.
А 10х50 будет еще больше...
Я боялся чего-то подобного... спасибо за разъяснение. Думаю, мне придется изменить свой подход.
Почти все возможно с помощью языков программирования. Но я предполагаю, что это не вопрос настоящий, верно? В противном случае ответ будет просто «да». Однако это не услуга по написанию кода, мы помогаем вам решить ваши проблемы, для чего обычно требуется минимальный воспроизводимый пример. Подробнее читайте в Как спросить