2

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

public class SubMatTry {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int a[][] = { { 2, 3, 5, 7 }, { 5, 8, 3, 5 }, { 7, 6, 9, 2 },
            { 3, 8, 5, 9 } };
    int b[][] = { { 9, 2 }, { 5, 9 } };
    int k = 0;
    int l = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            System.out.println("Element of a= " + a[i][j]);
            if (b[k][l] == a[i][j]) {
                System.out.println(b[k][l] + " = " + a[i][j]);
                if (b[k][l + 1] == a[i][j + 1]) {
                    System.out.println(b[k][l + 1] + " = " + a[i][j + 1]);
                    if (b[k + 1][l] == a[i + 1][j]) {
                        System.out.println(b[k + 1][l] + " = "
                                + a[i + 1][j]);
                        if (b[k + 1][l + 1] == a[i + 1][j + 1]) {
                            System.out.println(b[k + 1][l + 1] + " = "
                                    + a[i + 1][j + 1]);
                            System.out.println("Array found at" + i + " ,"
                                    + j);
                            System.exit(0);
                        }
                    }
                }
            }
        }

    }

}}

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

4

4 に答える 4

10

アルゴリズムは、4×4 マトリックスと 2×2 サブマトリックス用にハードコーディングされています。それ以外の場合は、ブルート フォース アルゴリズムとして問題ないように見えます。

私はそれを次のように表現したでしょう：

outerRow:
for (int or = 0; or <= a.length - b.length; or++) {
    outerCol:
    for (int oc = 0; oc <= a[or].length - b[0].length; oc++) {
        for (int ir = 0; ir < b.length; ir++)
            for (int ic = 0; ic < b[ir].length; ic++)
                if (a[or + ir][oc + ic] != b[ir][ic])
                    continue outerCol;
        System.out.println("Submatrix found at row " + or + ", col " + oc);
        break outerRow;
    }
}

より効率的なものが必要な場合は、次のようにフラット化することをお勧めします。

{ 2,3,5,7, 5,8,3,5, 7,6,9,2, 3,8,5,9 }

このシーケンスで次のパターンを検索します。

{ 9,2, _, _, 5, 9}

Aho-CorasickやKnuth-Morris-Pratt アルゴリズムなどの標準的な部分文字列検索手法を使用します。(シーケンスの途中に新しい行がある場合の誤検出を避けるために、いくつかのインデックスをスキップする必要があることに注意してください。)

于 2012-03-27T07:42:07.953 に答える
1

まず、iとjは3まで反復しないでください（a [3] [3]を使用している場合は、部分行列の開始にはなれないことがわかっているので、基本的には行列の最後にいることになります） 。

次に、4のように固定数を使用しないでください-代わりにa.lengthを使用してください（これにより、配列の長さa-列の数が得られますが、a [0] .lengthは最初の列の長さを示します-事実上、行）。

第三に、次のように、4倍if（原文のまま）をforkとlの2回の反復に変更します。

for (int i = 0; i < a.length - b.length + 1; i++) {
        for (int j = 0; j < a[0].length - b[0].length + 1; j++) {
            boolean submatrix = true; // at start we assume we have a submatrix
            for (int k = 0; k < b.length; ++k) {
                for (int l = 0; l < b[0].length; ++l) {
                    if (a[i + k][j + l] == b[k][l]) {
                        System.out.println("a[" + (i + k) + "][" + (j + l) + "] = b[" + k + "][" + l + "]");
                    } else {
                        submatrix = false; // we found inequality, so it's not a submatrix
                    }
                }
            }
            if (submatrix) {
                System.out.println("Found subatrix at " + i + "," + j + ".");
            }
        }
    }

（それが正確に機能するかどうかわからない、コンパイラーに通さなかった;））

それ以外に、Javaを使用する場合は、オブジェクト、クラス、およびメソッド（メソッドMatrixを持つクラスboolean isSubmatrix(Matrix b)）に慣れるようにする必要がありますが、初心者の場合はそうする必要があります。

私の答えがお役に立てば幸いです。

于 2012-03-27T07:46:47.923 に答える