1

ここに C# の興味深い問題があります。私はそれを解決するためのより良い方法を探しています:

一致の行列 M (必ずしも正方ではない) が与えられた場合、最適な一致要素を見つけます。要素 i は、値 M(i,j) によって elem j に一致します。M(i,j) != M(j,i)。

#rows != #columns なので、最適な最小 (#rows,#columns) の一致するペア (i,j) を見つけます。

基本的に問題は、行/列が2回選択されないように、各行/列から最大値を選択することです。

例：

     1  2  3 
  +---------
a | 10  3  1
b | 12  99 2
c | 20  5  3
d |  5  7  4

この行列の最大値は 99 であるため、最適な一致は (b,2) です。次の選択では、行 b と列 2 は使用できません。それらを切り取るようなものです。

     1  2  3  or, if you prefer,       1   3
  +---------  a smaller matrix:      +------
a | 10 ||  1                       a | 10  1
b | ===++===                       c | 20  3
c | 20 ||  3                       d | 5   4
d |  5 ||  4

最大値は 20 になり、一致は (c, 1) になります。残りの行列には 1 列しかありません。別のピックの後、マッチ = 4 のマッチ (d, 3) を取得します。

結局、"a" は一致しません。

私の現在の実装では、2 つの配列を使用して、既に一致した行/列を格納し、一致ごとにマトリックス全体を調べて、一致しない行/列に属する最初の最大値を選択します。

PS: 同じ値を持つ値が複数一致する場合は、そのうちの 1 つを選択してください。 PS2: 配列は次のように格納されます。int [,]

より最適で美しい方法でこの問題にどのように取り組みますか?

4

2 に答える 2

3

各行と各列から正確に 1 つのセルが選択されるように、選択したセルの合計を最大化しようとしている場合、これはhttp://en.wikipedia.org/wiki/Assignment_problemです。マトリックスが正方形でない場合は、行または列を追加して正方形にすることができます。新しいセルの値は、ソリューションを埋める方法が他にない限り選択されないことを意味します。

(合計を最大化していない場合は、選択した値のどの関数を最大化しているかを示す必要があります。(1,3) は (2,2) よりも優れていますか?) そうでない場合は、http://en.wikipedia. org/wiki/Multi-objective_optimization、可能ですが、より複雑です)。

于 2012-06-15T04:15:15.167 に答える
1

最初にマトリックスのすべてのエントリを降順で並べ替えてから、並べ替えられたリストを処理できます。既に選択されている行/列にないエントリが表示される場合は常に、エントリを選択する必要があることを意味するため、対応する行/列をマークし、すべての行またはすべての列が選択されるまでリストをさらに下に進みます.

于 2012-06-15T04:14:32.017 に答える