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

Question

Предположим, у нас есть таблица чисел, подобная этой (мы можем предположить, что это квадратная таблица):

20  2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11

Ваша задача - вычислить максимальную сумму из n чисел, где n - количество строкили столбцы в таблице.Выгода составляет , каждое число должно исходить из уникальной строки и столбца.

Например, выбирая числа в (0,0), (1,1), (2,2), (3,3) и (4,4) приемлемо, но (0,0), (0,1), (2,2), (3,3) и (4,4) не потому, чтопервые два числа были взяты из одной строки.

Мое (смехотворное) решение этой проблемы - перебрать все возможные перестановки строк и столбцов.Это работает для небольших сеток, но, конечно, это невероятно медленно, так как n становится большим.Он имеет O (n!) Временную сложность, если я не ошибаюсь (пример кода Python ниже).

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

Итак, мой вопрос: какой алгоритм следует использовать для решения этой проблемы?

Если это поможет, эта проблема кажется похожей на проблему рюкзак .

import itertools
import re

grid = """20    2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11"""
grid = [[int(x) for x in re.split("\s+", line)] for line in grid.split("\n")]

possible_column_indexes = itertools.permutations(range(len(grid)))
max_sum = 0
max_positions = []
for column_indexes in possible_column_indexes:
    current_sum = 0
    current_positions = []
    for row, col in enumerate(column_indexes):
        current_sum += grid[row][col]
        current_positions.append("(%d, %d)" % (row, col))
    if current_sum > max_sum:
        max_sum = current_sum
        max_positions = current_positions

print "Max sum is", max_sum
for position in max_positions:
    print position

Answer 1

Это проблема соответствия двухсторонней максимальной стоимости. Классический способ решить эту проблему - использовать венгерский алгоритм .

По сути, у вас есть двудольный граф: левый набор - строки, а правый набор - столбцы. Каждый край от строки i до столбца j имеет стоимость matrix[i, j]. Найдите соответствие, которое максимизирует затраты.

Answer 2

Для начала вы можете использовать динамическое программирование.

В вашем прямолинейном подходе вы выполняете одно и то же вычисление много, много раз.

Например, в какой-то момент вы отвечаете на вопрос: «Для последних трех столбцов с уже занятыми строками 1 и 2, как мне максимизировать сумму?» Вы вычисляете ответ на этот вопрос дважды, один раз, когда вы выбираете строку 1 из столбца 1 и строку 2 из столбца 2, и один раз, когда вы выбираете их наоборот.

Так что не делай этого. Кэшируйте ответ - а также кешируйте все похожие ответы на все подобные вопросы - и используйте их повторно.

Сейчас у меня нет времени анализировать время выполнения этого подхода. Я думаю, что это O (2 ^ n) или около того. Может быть, попозже ...