問題タブ [submatrix]

0〜1000の範囲の数値のN * N行列（N = 2〜10000）があります。同じ数値で構成される最大の（長方形の）部分行列を見つけるにはどうすればよいですか？

例：

出力は、部分行列の領域の後に、左上の要素の1ベースの座標が続く必要があります。この例では、列2、行1に(6, 2, 1)6つのが配置されているためです。9

入力：正と負の要素を持つ2次元配列NxN-行列-。

出力：可能なすべての部分行列の中でその合計が最大になるような任意のサイズの部分行列。

要件：アルゴリズムの複雑さはO（N ^ 3）である必要があります

歴史： Algorithmist、Larry、およびKadaneのAlgorithmの修正の助けを借りて、私は問題を部分的に解決することができました。これは、以下のJavaでの合計のみを決定することです。マトリックスの境界、つまり左上隅、右下隅、つまり下のRubyを決定するという、残りの問題を解決することができたErnesto
に 感謝します。

サブマトリックスのコレクションを収集したい大きなマトリックスがあります。行列がNxNで、部分行列のサイズがMxMの場合、部分I=(N - M + 1)^2行列を収集します。言い換えると、元の行列の要素ごとに1つのMxM部分行列が必要であり、そのような行列の左上隅に配置できます。

これが私が持っているコードです：

a）間違っている場合、およびb）big_mat(x:x+M-1, y:y+M-1)2つのforループを必要とせずに、必要なものを取得できる式に何かがあることを意味する場合の出力。どんな助けでも大歓迎です

私は非常に基本的なユーザーであり、Cで使用されるコマンドについてはあまり詳しくないので、ご容赦ください...非常に複雑なコードは使用できません。stdio.hおよびctype.hライブラリについてはある程度の知識がありますが、それだけです。txtファイルにマトリックスがあり、行と列の数の入力に基づいてマトリックスをロードしたい

たとえば、ファイルに5x5のマトリックスがあります。特定の2x2の部分行列を抽出したいのですが、どうすればよいですか？

を使用してネストされたループを作成しました：

悲しいことに、コードは機能しません..私がこのマトリックスを持っている場合：

そして、行に3、列に3を入力すると、次のようになります。

これは2x2のサブマトリックスではないだけでなく、最初の3行と最初の3列が必要な場合でも、正しく印刷されません。

行3と列3から始めて、2行2列の部分行列を取る必要があります。

私はで終わったはずです：

これを実現するためにfgetsとsscanfを使用できると聞きました。これが私のトライアルコードです：

しかし、これも機能しません:(

私は何を間違っているのですか？

助けてください。ありがとう ！

MxN マトリックスを指定すると、最大の合計数を持つ (連続した) サブマトリックスを見つけるプログラムを Java で作成しようとしています。次に、プログラムは部分行列の左上隅の座標と右下隅の座標を返す必要があります。行列には負の数を含めることができ、行列と部分行列の両方が正方形である必要はありません。

これがここで議論されているのを見ました:最大合計で部分行列を取得しますか? そして解決策はO（n ^ 3）のようです。私の友人は、かつてこの問題を O(n^2) で解くことができたと言っていました。ここでも提案。それは可能ですか？

この問題を最も効率的に解決できるコードはありますか?

私はopencvにかなり慣れていません。大きな (~1000 x ~1000) マトリックスの小さな (9x9) サブマトリックスで何らかの処理を行うループを作成しようとしています。いくつかのマスク マトリックスに基づいて、大きなマトリックスの特定のポイントで 9x9 を処理するかどうかを決定しました。私が読んだドキュメントに基づいて、このコード行をループ内に入れようとしています:

i と j は、より大きな行列の行、列のインデックスです。次に、tempROI を処理する関数があります。ただし、ROI のサイズが i と j とともに増加していることがわかります。私はダンプしました：

ループに入ってデバッグします。ROI が大幅に向上していることがわかります。たとえば、これはランダム ダンプです。

ROI のサイズ = 191, 9. IDX の場合 = 4, 186

明らかに何かが適切に機能していません。誤りは、より大きな部分行列から部分行列を適切に選択する方法についての私の理解にあるというのは公正な仮定だと思います。誰かがこれを行うための最良の方法についてアドバイスできますか?

関連する注意事項として、ループの反復ごとに実際に行列ヘッダーを作成するのではなく、ポインターを使用することを本当に望んでいました。

要するに、私がやろうとしていることを行う正しい方法は何ですか? どうもありがとう。

R で行列を使用する場合:

行が列 3 = 11 の部分行列を抽出したいとします。つまり、次のようになります。

ループせずにこれを行いたいです。私は R を初めて使用するので、これはおそらく非常に明白ですが、ドキュメントはしばしばやや簡潔です。

scipy.sparse パッケージから lil_matrix (A) をスライスするときの次の動作を理解するために、助けていただければ幸いです。

実際には、行と列の両方の任意のインデックス リストに基づいて部分行列を抽出したいと考えています。

この2行のコードを使用したとき：

すべてが順調で、適切な部分行列を抽出できました。

これを一行でやろうとしたところ、失敗しました（返される行列は空でした）

これはなぜですか？全体として、私はmatlabで同様のコマンドを使用しましたが、そこで動作します。では、機能するので、最初のものを使用しないのはなぜですか? かなり手間がかかりそうです。大量のエントリを通過する必要があるため、単一のコマンドで高速化したいと考えています。間違った疎行列タイプを使用している可能性があります...何か考えはありますか?

特定のサブマトリックスでサブマトリックスを見つけるためのアルゴリズムを作成しようとしています。この問題を解決するために、次のコードを書きました。

このコードは正常に動作していますが、それが問題の正確な解決策なのか、単なる回避策なのかはわかりません。専門家のコメントをお寄せください。前もって感謝します。

マトリックスの最後まで列1〜3、7〜9、13〜15を抽出したいデータセットがあります。

例として、標準のマジック関数を使用してマトリックスを作成しました

A = magic（10）

A =

次のコマンドを使用して、3の間隔で1から始まる単一の列を抽出できることを知っています。

Aex = a（：、1：3：終了）

Aex =

代わりに、列のグループを抽出したいとします（たとえば、列1-3、7-9など）。

すべての列番号を手動で指摘することなくこれを行う方法はありますか？

ご協力いただきありがとうございます！ラスムス