0

在这里，我提供了我的问题的最小完整可验证示例：

考虑大小为 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 中的成本，如果成本结果为负，则将其替换为所有列值的总和（没有什么特别的，但要确保一些巨大的价值）。现在需要进行最低成本分配。我使用sudo apt-get install python-munkres安装了库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] 分配，则包含已分配元素的其余模式 ie,2,5 此处不应可用于分配，或者矩阵中相应的模式相关成本应更新为太高的值，这样那些不再考虑到下一行的人应该像这样进行。

最终意味着如果分配是可能的，则相应的模式本质上应该是互斥的。

谁能建议如何解决这个问题？

4

1 回答 1

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),
于 2015-06-10T10:33:31.060 回答