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] 割り当てられると、割り当てられた要素のいずれかを含むパターンの残りの部分、つまりここでは 2,5 は割り当てに使用できなくなります。または、マトリックス内の対応するパターン関連コストを非常に高い値に更新する必要があります。次の行と見なされなくなったものは、このように続行する必要があります。

最終的には、割り当てが可能な場合、対応するパターンは本質的に相互に排他的である必要があります。

誰でもこれに取り組む方法を提案できますか?

4

1 に答える 1

1

朗報:この問題を解決する方法があります。
悪いニュース:この問題を解決する簡単な方法はありません。

何が問題ですか？
いくつかの予備計算を行った後、2D コスト マトリックスとセットのリスト (コスト マトリックスの各列に 1 つずつ) が得られます。目的は、コスト マトリックスでできるだけ多くのインデックスを選択することです。

  • 2 つの選択されたインデックス (割り当て) が同じ行または列内にない。
  • 割り当ての列に関連付けられたセットが互いに素であり、
  • 割り当ての合計が最小化されます。

解決策は何ですか？
この問題は、N 次元割り当て問題のインスタンスと見なすことができます。問題の最初の 2 つの次元 (コスト マトリックスの 2 つの次元) はかなり明白です。残りの寸法はそれほど明白ではないかもしれません。

まず、他のセットのすべての値を含むスーパーセットを作成します。このスーパーセットのサイズにコスト行列の 2 つの次元を加えたものが、この N 次元の割り当て問題における N の値です。あなたの例では、スーパーセットは[1, 2, 3, 4, 5, 6]であり、N は 8 です。

この 2 次元のコスト マトリックスでは、マトリックス内の各コストを行番号と列番号で特定できます。たとえば、(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 に答える