java - Null 行列への反復還元

Question

問題は次のとおりです。次のような行列が与えられます

入力：

1 1 1
1 1 1
1 1 1

各ステップで、同じ行または列に 2 つの 1 がない 1 と 0 の「2 番目の」行列を見つける必要があります。次に、元の行列から 2 番目の行列を引きます。すべてが 0 の行列が得られるまで、このプロセスを繰り返します。さらに、可能な限り少ない数のステップを実行する必要があります。

すべての「秒」行列を O(n) 時間で出力する必要があります。上記の例では、次の 3 つの行列を順番に減算することで、3 つの手順で null 行列を取得できます。

期待される出力:

最初の最大値を見つけ、その値のインデックスに基づいて 2 番目の行列を作成する試みをコーディングしました。しかし、上記の入力に対して、4 つの出力行列が得られますが、これは間違っています。

私の出力：

私のソリューションはほとんどのテストケースで機能しますが、上記のテストケースでは失敗します。続行する方法について誰かが私にいくつかの指針を与えることができますか、または最適性を保証するアルゴリズムを見つけることができますか?

動作するテストケース:

入力：

0 2 1
0 0 0
3 0 0

出力

score 1 · Accepted Answer

各行/列を合計し、それらの合計の最大値を取得すると、ヌル行列に減らすために必要な行列減算の最適な数が得られます。

例えば：

1 2 4 0 = 7
2 2 0 1 = 5
0 0 1 0 = 1
3 0 2 1 = 6
= = = =
6 4 7 2

これは、この行列が空になるまで 7 回の最適な減算を行うことを意味します。

これから逆算し、その値で列/行から削除すると問題が解決すると思います(これらを選択する効率的な方法がわかりません-ブルートフォース?)。
前の方法を使用して余分な要素を削除することもできます。

たとえば（上記のマトリックスを使用）。

ステップ 7:行 1 と列 3 から減算する必要があり
ます。

これを解決したので、以前の方法を使用して「ボーナス」要素を削除できます。

各行/列の合計を再度適用し、次のステップに進みます。

ステップ 6:

1 2 3 0 = 6
1 2 0 1 = 4
0 0 1 0 = 1
3 0 2 0 = 5
= = = =
5 4 6 1

次の引き算:

等々。

注:これは、すべての行と列から 1 を選択するという問題に行き詰まるため、「すべて 1」の行列ではうまく機能しません (例で行ったのと同じ)。

しかし、誰かが私のソリューションを拡張できるかもしれません。

score 0 · Accepted Answer

これがあなたが求めているものであるかどうかは完全にはわかりませんが、使用可能な列のリストを作成し、各反復で使用されるものとしてマークを付けることができます。

例えば：

repeat until an empty matrix
  mark all columns as available
  for each row
    find the maximum value in all available columns and store it's coordinates
    mark that column as unavailable
  print, decrement and clear the list of stored coordinates

これは機能しませんが、user1459032が使用しているアルゴリズムを示しています。

score 0 · Accepted Answer

行数 = 列数 = N とする

for iteration=1:N
  for row=1:N
      cell(row,(row+iteration)%N) := 0

反復回数は N です。反復ごとに、N 個の 1 が 0 に変更されます

score 0 · Accepted Answer

1) If all you want to do is iterate through all the elements in your matrix...

2) then all you have to do is loop for (int i=0; i < rows*cols; i++) {} ...

3) And such a loop is ALREADY O(n) (i.e. it increases LINEARLY with the #/elements in your matrix)

score 0 · Accepted Answer

これは、NP完全であることが知られている正確なカバー問題の一種であると確信しています。提案されたアルゴリズムは、単純な貪欲なソリューションです。貪欲な解決策の問題点は、貪欲さが良いことであるとあなたに納得させるのに十分なほどうまく機能し、その後、突然、より良い解決策を求めてあなたを無気力にさせてしまうことです. （たとえば、世界経済を考えてみてください。）とにかく、Knuth のDancing Linksテクニックは、問題を解決する標準的な方法です（世界経済ではなく、正確なセットカバー）。

java - Null 行列への反復還元

5 に答える 5

Related

Reference