Вот решение, написанное на python на основе взвешенного двустороннего сопоставления (или изоморфной c задачи потока минимальной стоимости.)
#!/usr/bin/python
"""
filename: mcf_matrix_assign.py
purpose: demonstrate the use of weighted bipartite matching (isomorphic to MCF
with a suitable transform) to solve a matrix assignment problem with
certain conditions and optimization goals.
"""
import networkx as nx
N = 5
K = N # ensure K is large enough to satisfy flow, N <= K <= N*N
# setting K larger simply means a longer runtime
G = nx.DiGraph()
total_demand = 0
for i in range(N*N):
# assert a row-major linear indexing of the matrix
row, col = i / N, i % N
if row >= col:
continue # symmetry fix certain values
total_demand += 1
G.add_node('s'+str(i),demand=-1);
G.add_edge('s'+str(i), 'v'+str(row), weight = 0, capacity = 1)
G.add_edge('s'+str(i), 'v'+str(col), weight = 0, capacity = 1)
G.add_node('sink', demand = total_demand)
# attach each 'value' to the sink with incrementally larger weight
for i in range(N):
for j in range(K):
dummy_node = 'v'+str(i)+'w'+str(j)
G.add_edge('v'+str(i), dummy_node, weight = j, capacity = 1)
G.add_edge(dummy_node, 'sink', weight = 0, capacity = 1)
flow_dict = nx.min_cost_flow(G)
# decode the solution to get the matrix assignment reported by the MCF (or
# equivalently weighted bipartite matching)
solution = [ -1 for i in range(N*N) ]
for i in range(N*N):
# assert a row-major linear indexing of the matrix
row, col = i / N, i % N
if row == col:
solution[i] = row
continue # symmetry fix certain values
if row > col:
solution[i] = solution[col*N+row]
continue # symmetry fix certain values
adjacency = flow_dict['s'+str(i)]
solution[i] = row if adjacency['v'+str(row)] == 1 else col;
# print the solution
for row in range(N):
print ''.join(['-' for _ in range(4*N+1)])
print '|',
for col in range(N):
print str(solution[row*N+col]+1) + ' |',
print '\n',
print ''.join(['-' for _ in range(4*N+1)])
print 'Histogram summary:'
counts = [ (i+1, sum([ 0 if s != i else 1 for s in solution ])) for i in range(N) ]
for value, count in counts:
print ' Value ', value, " appears ", count, " times."
Это дает решение:
---------------------
| 1 | 1 | 3 | 1 | 5 |
---------------------
| 1 | 2 | 2 | 4 | 2 |
---------------------
| 3 | 2 | 3 | 4 | 3 |
---------------------
| 1 | 4 | 4 | 4 | 5 |
---------------------
| 5 | 2 | 3 | 5 | 5 |
---------------------
Histogram summary:
Value 1 appears 5 times.
Value 2 appears 5 times.
Value 3 appears 5 times.
Value 4 appears 5 times.
Value 5 appears 5 times.
И вот решение, когда N=4 в скрипте.
-----------------
| 1 | 2 | 1 | 4 |
-----------------
| 2 | 2 | 3 | 4 |
-----------------
| 1 | 3 | 3 | 3 |
-----------------
| 4 | 4 | 3 | 4 |
-----------------
Histogram summary:
Value 1 appears 3 times.
Value 2 appears 3 times.
Value 3 appears 5 times.
Value 4 appears 5 times.
Довольно легко доказать, что это всегда найдет оптимальный ответ за полиномиальное время.
Объяснение
Вероятно, проще всего объяснить происходящее, описав построение графа для небольшого случая. Для этого обсуждения исправьте N=3.
В этом случае у нас есть назначение матрицы с переменными
X s0 s1
X X s2
X X X
, где X обозначает фиксированное значение, а sk обозначает k -й слот в массиве для заполнения.
В этом случае у нас также есть 3 доступных назначения значений [1,2,3] для каждого из слотов sk. (Здесь легко внести изменения в «разрешенные» значения для любых sk.)
Если мы построим двудольный граф между слотами sk и присвоениями значений v1,v2,v3 в Таким образом, ребра емкости 1 и нулевого веса используются для соединения sk с каждым допустимым назначением vi, мы можем легко решить эту проблему с помощью MCF.
Для иллюстрации соответствующий график для N=3 показано ниже: График, используемый в MCF для случая N = 3.
После вычисления потока минимальной стоимости мы можем декодировать назначение, проверив, какие ребра используются в решении.
Примечание по производительности
networkx было используется здесь в python исключительно для удобства, он ни в коем случае не эффективен в любом смысле этого слова. Качество реализации алгоритма MCF в networkx довольно низкое, и я бы не рекомендовал пытаться его масштабировать.
Для серьезных приложений я бы вместо этого рекомендовал лимонную библиотеку MCF (в частности, алгоритм масштабирования затрат является конкурентоспособным) или вы можете использовать реализацию Эндрю Голдберга масштабирования затрат (которую трудно найти, но она существует) и, вероятно, также довольно эффективна.