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

Question

Здесь я обеспечиваю минимальный полный поддающуюся проверку Пример моей проблемы:

прямоугольная матрица размера 3 х 17 считаются: строк = [10,6,9] рассмотрено. где столбцы являются образцами каждый из которых связан со значением

example file: "patterns_list" <pattern <space> associated value> 
['2','3'] 12 
['2','1'] 11 
['2','5'] 11 
['3','4'] 10 
['3','5'] 9 
['4','1'] 9 
['4','5'] 9 
['3','6'] 8 
['4','6'] 8 
['1','5'] 8 
['2'] 7 
['1','6'] 7 
['3'] 5 
['4'] 5 
['1'] 4 
['5'] 4 
['6'] 3 

Теперь, разница между значением столбца и значением строки рассматриваются как стоимость в матрице 3 х 17, и если стоимость оказалась отрицательным это заменяется суммированием всех значений столбцов (ничего конкретного, кроме как для обеспечения огромного значения). Теперь необходимо выполнить минимальное распределение затрат. Я установил библиотеку Манкрес с помощью Суд APT-получить установку питон-Манкрес и побежал следующий код:

from munkres import Munkres, print_matrix 
import linecache 

rows=[10,6,9] 
v=[] 
diff=[] 
value=[] 
f = open("patterns_list","r") 
for line in f: 
     line=line.strip() 
     line=line.split(' ') 
     v.append(int(line[1])) 
total=sum(v) 
for i in range(0,len(rows)): 
     for j in range(0,len(v)): 
       x=v[j]-rows[i] 
       if x<0: 
         value.append(total) 
       else: 
         value.append(v[j]-rows[i]) 
     diff.append(value) 
     value=[] 

matrix=diff 

m = Munkres() 
indexes = m.compute(matrix) 
print_matrix(matrix, msg='Lowest cost through this matrix:\n') 
total = 0 
patterns=[] 
print "Allocation indices:" 
for row, column in indexes: 
    value = matrix[row][column] 
    total += value 
    print '(%d, %d) -> %d' % (row, column, value) 
    patterns.append(int(column)) 

print 'total cost: %d' % total 
print "Corresponding allocated patterns:\n" 
for i in range(0,len(patterns)): 
    line = linecache.getline("patterns_list",patterns[i]) 
    print line 

генерируется следующий вывод:

Lowest cost through this matrix: 

[ 2, 1, 1, 0, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130] 
[ 6, 5, 5, 4, 3, 3, 3, 2, 2, 2, 1, 1, 130, 130, 130, 130, 130] 
[ 3, 2, 2, 1, 0, 0, 0, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130] 
Allocation indices: 
(0, 3) -> 0 
(1, 10) -> 1 
(2, 4) -> 0 
total cost: 1 
Corresponding allocated patterns: 

['2','5'] 11 

['1','5'] 8 

['3','4'] 10 

вопросом является [2 , 5], [1,5], [3,4] являются окончательно распределенными шаблонами, которые соответствуют минимальной стоимости. Здесь шаблоны [2,5], [1,5] не являются взаимоисключающими. «5» - это общее. После того, как r1 получил [2,5], тогда остальная часть шаблонов, содержащих любой из выделенного элемента, т.е. 2,5 здесь, не должна быть доступна для распределения или соответствующие связанные с шаблоном затраты в матрице должны быть обновлены до слишком высокого значения, так что те, которые больше не рассматриваются в следующем ряду, должны действовать следующим образом.

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

Может ли кто-нибудь предложить, как решить эту проблему?

Answer 1

Хорошие новости: Существует способ решить эту проблему.
Плохие новости: Нет easy способ решить эту проблему.

В чем проблема?
После выполнения предварительных расчетов у вас есть 2D-матрица затрат и список наборов - по одному для каждого столбца в матрице затрат. Цель состоит в том, чтобы выбрать, как много индексов в матрице затрат, как это возможно, учитывая, что

• нет двух выбранных индексов (задания) лежат в одной и той же строке или столбце,
• множества связанных со столбцами заданий являются непересекающимися, а
• сумма заданий минимизирована.

Какое решение?
Эта проблема может быть рассмотрена как экземпляр проблемы N-мерного присвоения. Первые два измерения проблемы (два измерения матрицы затрат) достаточно очевидны. Остальные размеры могут быть не столь очевидными.

Во-первых, мы хотим создать супермножество, содержащее все значения из других наборов.Размер этого надмножества - плюс два измерения стоимостной матрицы - это значение N в этой задаче N-мерного присваивания. В нашем примере наш суперсет [1, 2, 3, 4, 5, 6], и наш N таким образом 8.

В нашей двумерной матрице затрат каждая стоимость матрицы может быть расположена по номерам строк и столбцов. Например, стоимость в (1, 3) равна 4. Для 8-мерной матрицы затрат каждая стоимость будет располагаться с использованием 8 номеров позиций. К счастью, мы можем вычислить эти номера позиций итеративно.

rows = [10,6,9] 

import ast 
from munkres import print_matrix 

listOfSets = [] 
v = [] 
with open("patterns_list","r") as file: 
    for line in file: 
     listOfSets.append(ast.literal_eval(line.strip().replace("'","").split(" ")[0])) 
     v.append(int(line.strip().split(" ")[1])) 

total = sum(v) 
matrix = [] 
for row in rows: 
    values = [] 
    for num in v: 
     x = num-row 
     values.append(total if x<0 else x) 
    matrix.append(values) 

superset = list(set().union(*listOfSets)) 
counter = [1] * len(superset) 
newMatrix = [] 
for row in range(0, len(rows)): 
    for column in range(0, len(v)): 
     if matrix[row][column] == total: 
      break 
     temp = [matrix[row][column], row, column] 
     for n in range(0, len(superset)): 
      if superset[n] in listOfSets[column]: 
       temp.append(0) 
      else: 
       temp.append(counter[n]) 
       counter[n] += 1 
     newMatrix.append(temp) 

print_matrix(newMatrix, msg="New Matrix = [ value, row, column, dimension1position, dimension2position...]") 

Теперь у нас есть список, содержащий все значения из матрицы 2D затрат (это не фиктивное значение) и связанное с ним положение в нашей новой N-мерной матрицы. Я решил сделать это таким образом, вместо того чтобы фактически сделать полную N-мерную матрицу, поскольку полная N-мерная матрица была бы очень большой и в основном заполнялась фиктивными значениями. Тем не менее, полная N-мерная матрица может быть легко создана из этого списка, если это необходимо. Запуск многомерного решения задачи задания на этом N-мерном массиве даст вам ответ, который вы хотите. Однако, насколько мне известно, кода для многомерного решения задачи присваивания не существует. Вы должны будете сами это закодировать.

 

пс: Я очистил свой исходный код немного.

rows=[10,6,9] 

from munkres import Munkres, print_matrix 
import linecache 

v=[] 
with open("patterns_list","r") as file: 
    for line in file: 
     v.append(int(line.strip().split(" ")[1])) 

total=sum(v) 
matrix=[] 
for row in rows: 
    values=[] 
    for num in v: 
     x=num-row 
     values.append(total if x<0 else x) 
    matrix.append(values) 

print_matrix(matrix, msg="Cost Matrix:") 

indices = Munkres().compute(matrix) 
total = 0 
patterns=[] 
print "\nAllocated Indices:" 
for row, column in indices: 
    value = matrix[row][column] 
    total += value 
    print "(%d, %d) -> %d" % (row, column, value) 
    patterns.append(column) 

print "Total Cost: %d" % total 

print "\nCorresponding Allocated Patterns:" 
for pattern in patterns: 
    print linecache.getline("patterns_list",pattern),