Вот несколько идей для размышления:
1) Предположим, вы записали матрицу затрат с n столбцами и m строками. Если n больше, чем m, вы добавляете строки заполнения с постоянной большой стоимостью, чтобы сделать его квадратным. При назначении минимальной стоимости строк и столбцов некоторые столбцы теперь будут отбрасываться путем сопоставления их со строками заполнения. Предположим, теперь вы добавили столбец заполнения с очень низкой стоимостью для обычных строк и постоянной большой стоимостью для столбцов заполнения. Теперь решение будет сопоставлять одну из правильных строк с этим столбцом, чтобы воспользоваться очень низкой стоимостью. Это уменьшает количество строк, которые соответствуют чему-то разумному. Я думаю, что если вы добавите m-k таких столбцов, вы получите соответствие минимальной стоимости, которое действительно назначает только k строк.
Here is an example of pairing 3 with 3 in 5x5, assuming ?
marks problem-specific values > 0 but < 100 (you may
need more extreme values than 0 and 100 to force the sort of
solution you want depending on what your data values are).
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
100 100 100 100 100 100 100
100 100 100 100 100 100 100
Я ожидаю, что оптимальное решение будет использовать
два 0 с далекого
справа и две сотки от нижних рядов. Оставшиеся клетки
совпадение 3 x 3 в квадрате? s
ОК - вот доказательство того, что добавление столбцов, а затем строк, как указано выше, дает требуемый вид соответствия:
Предположим, что вы берете матрицу затрат со значениями 0
Возможно ли, что в растворе ассигмента выбраны какие-либо ячейки в правой нижней области s x s? Рассмотрим любое такое назначение. Чтобы доказать, что должна быть выбрана хотя бы одна ячейка в верхней левой области, предположим, что ни одна не выбрана. Затем мы должны каким-то образом выбрать ячейку из каждой из верхних n строк, предположительно, выбирая ячейки из верхней правой области. Каждая такая ячейка должна находиться в отдельном столбце, но в верхней правой области есть только s столбцов, чего будет недостаточно, потому что нам нужен только один столбец для каждого соответствия, которое мы хотим пропустить, и мы использовали один столбец в этом область уже заполнить ячейку в нижней правой области. Итак, предположим, что решение выбирает, по крайней мере, одну ячейку в исходной верхней левой области и, по крайней мере, одну ячейку в нижней правой области. Выберите две другие клетки, которые превращают это в четыре угла квадрата. Эти клетки не могут быть выбраны. Если мы выберем те ячейки вместо двух, которые выбраны в настоящее время, мы получим другое решение. Две новые ячейки - это ячейка 0 сверху справа и ячейка 100 снизу слева. Они заменят ячейку 100 снизу справа и ячейку со значением больше нуля в основной матрице. Так что это сделало бы наше предполагаемое решение лучше, поэтому любое решение, содержащее ячейку в правой нижней области, не является лучшим решением, и алгоритм присваивания не вернет его нам.
Таким образом, эта хитрость добавления столбцов с нулями, а затем строк с большими значениями создаст решение алгоритма присваивания, которое исключает одно совпадение из исходного решения для каждого добавленного (строка, столбец).
2) Проблема присвоения является частным случаем http://en.wikipedia.org/wiki/Minimum-cost_flow_problem. Я думаю, что вам нужен минимальный поток затрат, который переносит k единиц из строк в столбцы, поэтому вы можете попробовать решить эту проблему следующим образом.
3) Задача о потере минимальных затрат является частным случаем линейного программирования. Я думаю, что вы могли бы записать линейную программу для присвоения чисел в диапазоне [0,1] ячейкам матрицы таким образом, чтобы каждая строка и каждый столбец суммировали не более 1, а сумма всех ячеек составляла k. Тогда целевой функцией является число в каждой ячейке, умноженное на ее стоимость.