Нахождение оптимального выбора в 2D матрице с заданными ограничениями

Question

Постановка задачи

Учитывая матрицу m x n , где m <= n </strong>, вы должны выбрать записи так, чтобы их сумма была максимальной.

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

Пример * * тысяча двадцать-одна Допустимые значения: Неверный выбор: (одна запись на строку и не более одной на столбец) Мои подходы

1. Выберите лучшую из k случайных перестановок

   A = createRandomMatrix(m,n)
   selections = list()
   
   for try in range(k):
     cols = createRandomIndexPermutation(m) # with no dublicates
     for row in range(m):
       sum += A[row, cols[row]]
       selections.append(sum)
   
   result = max(selections)
   

   Этот подход работает плохо, когда n значительно больше, чем m

2. Лучший из возможных (еще не занятых) столбцов в строке

   A = createRandomMatrix(m,n)
   takenCols = set()
   
   result = 0
   for row in range(m):
     col = getMaxColPossible(row, takenCols, A)
     result += A[row, col]
     takenCols.add(col)
   

   Этот подход всегда оценивает строки (или столбцы) выше, которые были обнаружены первыми, что может привести к худшим, чем в среднем, результатам

Answer 1

Это звучит в точности как прямоугольное линейное задание (RLAP). Эта проблема может быть эффективно (с точки зрения асимптотической сложности; примерно в кубическом времени) решена (до глобального оптимума), и доступно большое количество программного обеспечения.

Основными подходами являются LAP + фиктивные переменные, LAP-модификации или более общие алгоритмы, такие как сетевые потоки (минимальная стоимость, максимальный поток).

Вы можете начать с ( pdf ):

Bijsterbosch, J. и A. Volgenant. «Решение проблемы прямоугольных назначений и приложений». Анналы исследования операций 181.1 (2010): 443-462.

Небольшой пример Python с использованием общего научного стека Python:

Редактировать: , как упоминалось в комментариях, отрицание матрицы затрат (что я и сделал, мотивировано описанием LP) - это не то, что сделано в литературе по методам Мункре / Венгерский. Стратегия состоит в том, чтобы построить матрицу прибыли из матрицы затрат, что теперь отражено в примере. Этот подход приведет к неотрицательной матрице затрат (иногда предполагает, что, если это важно, зависит от реализации). Более подробная информация доступна в этот вопрос .

код

import numpy as np
import scipy.optimize as sopt    # RLAP solver
import matplotlib.pyplot as plt  # visualizatiion
import seaborn as sns            # """
np.random.seed(1)

# Example data from
# https://matplotlib.org/gallery/images_contours_and_fields/image_annotated_heatmap.html
# removed a row; will be shuffled to make it more interesting!
harvest = np.array([[0.8, 2.4, 2.5, 3.9, 0.0, 4.0, 0.0],
                    [2.4, 0.0, 4.0, 1.0, 2.7, 0.0, 0.0],
                    [1.1, 2.4, 0.8, 4.3, 1.9, 4.4, 0.0],
                    [0.6, 0.0, 0.3, 0.0, 3.1, 0.0, 0.0],
                    [0.7, 1.7, 0.6, 2.6, 2.2, 6.2, 0.0],
                    [1.3, 1.2, 0.0, 0.0, 0.0, 3.2, 5.1]],)
harvest = harvest[:, np.random.permutation(harvest.shape[1])]

# scipy: linear_sum_assignment -> able to take rectangular-problem!
# assumption: minimize -> cost-matrix to profit-matrix:
#                         remove original cost from maximum-costs
#                         Kuhn, Harold W.:
#                         "Variants of the Hungarian method for assignment problems."
max_cost = np.amax(harvest)
harvest_profit = max_cost - harvest

row_ind, col_ind = sopt.linear_sum_assignment(harvest_profit)
sol_map = np.zeros(harvest.shape, dtype=bool)
sol_map[row_ind, col_ind] = True

# Visualize
f, ax = plt.subplots(2, figsize=(9, 6))
sns.heatmap(harvest, annot=True, linewidths=.5, ax=ax[0], cbar=False,
            linecolor='black', cmap="YlGnBu")
sns.heatmap(harvest, annot=True, mask=~sol_map, linewidths=.5, ax=ax[1],
            linecolor='black', cbar=False, cmap="YlGnBu")
plt.tight_layout()
plt.show()

выход