Блог

Это мой первый вопрос по обмену стеками. Я работаю над проблемой, в которой мне нужно найти распределение неотрицательных целых чисел в матрице, где каждая строка и каждый столбец составляют целевую сумму. Я уверен, что есть алгоритм, который может это сделать (или теория, которая говорит, когда это возможно, а когда нет), но мне не очень повезло найти это в Интернете.

В прикрепленном изображении (Изображение) У меня есть пример решения, которое я нашел для конкретного экземпляра проблемы, но в нем не было определенного алгоритма. Серые итоги — это целевые итоги для каждого столбца и строки, а светло-синие итоги — это итоги для текущего показанного распределения. В начале алгоритма предоставляются только итоговые значения, поэтому я начинаю с пустой матрицы.

Не мог бы кто-нибудь указать мне на ресурс / решение этой проблемы?

Спасибо

Это выглядит как сложная задача (вероятно, np-сложная).

Ваш лучший выбор (игнорирование высоконастроенных алгоритмов, зависящих от домена) — это классические подходы к комбинаторной оптимизации:

• Метаэвристика (табу-поиск, имитация отжига и др.)
  • Требуется некоторая настройка / определение окрестностей…
• SAT-решатели
  • Требуется раздражающая эмуляция сумматоров
  • завершить (может доказать, что решения нет)
• Ограничение-программирование
  • Легко сформулировать
  • Можно настроить
  • завершить
• Целочисленное программирование
  • Легко сформулировать, как показано ниже
  • Доступны очень хорошие коммерческие решатели
  • завершите Я представлю простую версию последнего (что, вероятно, является наихудшим подходом из них; по крайней мере, для этой проблемы!)

Он реализован в python и использует инструменты с открытым исходным кодом cvxpy (формулировка) и cbc (MIP-решатель).

Код

Обновление: исправьте некоторые значения элементов априори!

 from cvxpy import *

targets_X = [17, 45, 7, 6]
targets_Y = [3 for i in range(11)]   [2 for i in range(21)]
fixed_elements_indices_x, fixed_elements_indices_y = [0, 1, 2], [0, 1, 2]
fixed_elements_values = [3, 3, 3]
dim_x, dim_y = len(targets_X), len(targets_Y)

# Vars
T = Int(dim_x, dim_y)

# Constraints
constraints = []
constraints.append(T >= 0)
constraints.append(sum_entries(T, axis=1) == targets_X)
constraints.append(sum_entries(T, axis=0).T == targets_Y)
constraints.append(T[fixed_elements_indices_x, fixed_elements_indices_y] == fixed_elements_values)
problem = Problem(Minimize(0), constraints)
problem.solve(CBC, verbose=True)

print(T.value.T)
  

Вывод

 Clp0006I 0  Obj 0 Primal inf 159 (39)
Clp0006I 36  Obj 0 Primal inf 98.999998 (19)
Clp0006I 69  Obj 0
Clp0006I 69  Obj 0
Clp0000I Optimal - objective value 0
Cbc0045I No integer variables out of 128 objects (128 integer) have costs
Cbc0045I branch on satisfied N create fake objective Y random cost Y
Clp0000I Optimal - objective value 0
Node 0 depth 0 unsatisfied 0 sum 0 obj 0 guess 0 branching on -1
Clp0000I Optimal - objective value 0
Cbc0004I Integer solution of 0 found after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective 0, took 0 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Clp0000I Optimal - objective value 0
Clp0000I Optimal - objective value 0
[[ 3.  0.  0.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  0.  3.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  0.  3.  0.]
 [ 0.  0.  0.  3.]
 [ 0.  0.  0.  3.]
 [ 0.  2.  1.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 0.  2.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]
 [ 2.  0.  0.  0.]]
  

Вы можете решить это за полиномиальное время, используя алгоритм максимального потока.

Настройте исходный узел, узел для каждой строки, узел для каждого столбца и узел назначения.

Ребра от источника до узла строки должны иметь емкость, равную заданной сумме строк.

Ребра от узла col до dest должны иметь емкость, равную заданной сумме столбцов.

Ребра от узла строки до узла столбца должны иметь емкость в соответствии с допустимыми значениями в вашей матрице. (например, если запись в строке x, столбец y матрицы должен быть равен нулю, затем установите емкость равной 0 для ребра от узла строки x до узла столбца y .)

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

Сложность равна O (n ^ 3) для решения матрицы nxn.