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

Question

Здесь я предоставляю Минимальный Полный Проверяемый Пример моей проблемы:

Рассматривается прямоугольная матрица размером 3 X 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 X 17, и если стоимость оказалась отрицательной, она заменяется суммированием всех значений столбца (ничего конкретного, кроме обеспечения некоторого огромного значения). Теперь минимальное распределение затрат должно быть сделано. Я установил библиотеку munkres с помощью sudo apt-get install python-munkres и запустил следующий код:

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

Хорошая новость: есть способ решить эту проблему.
Плохая новость: не существует простого способа решить эту проблему.

В чем проблема?
После некоторых предварительных вычислений у вас есть 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-мерного массива даст вам нужный ответ. Однако, насколько мне известно, кода для многомерного решения задач присваивания не существует. Вам придется кодировать это самостоятельно.

PS: Я немного почистил ваш оригинальный код.

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),