0

ブルート フォース アルゴリズムを使用して 2 次元配列のすべての可能な組み合わせを作成し、そのすべてのコストから最適なものを見つけるというタスクが与えられました。

たとえば、配列のサイズが 4 X 3 で、コンテンツがある場合は、次のようにします。

1  2  3
4  5  6
7  8  9
10 11 12

可能な組み合わせの1つは

1
4
7
10

同様に

1
4
7
11

...

1
4
7
12

...

1
4
8
10

...

1
4
8
11

...

など、したがって、そのようなすべての組み合わせです。上記の組み合わせが 2 次元配列に格納され、数字のない場所に " - " が挿入されたことを思い出してください。例えば:

1 - -
4 - -
7 - -
10 - -

2次元配列なので「 - 」を格納することはできないので、そのまま表示されるだけです。これで、すべての組み合わせに対してランダムに生成されたコストが発生します。総当たりのように、まずすべての組み合わせを見つけてから、その中から最適な組み合わせを選択します。たとえば、私の配列が 10 X 5 の場合、多くの時間がかかりました。

次に、5^10 の組み合わせを作成する必要があります。これは膨大な量であり、時間がかかります。私は実際に、動的プログラミングを通じてそれを代替するのを誰かに手伝ってもらいたいと思っています。配列のサイズは nxm で、m は最大 2 または 3、n は最大 1000 です。よろしくお願いします。

4

2 に答える 2

1

1 - - / - - 6 / - - 9 / - - 12 は有効ですか? あなたが尋ねているかもしれない問題は、標準の動的プログラミングの問題である、このマトリックスを通る最も安価なパスは何かだと思います。 http://en.wikipedia.org/wiki/Dynamic_programming#Checkerboardを参照してください。

それ以外の場合、問題が単に最大合計を意味する場合は、行ごとに 1 つの要素しか持てないため、各行で max を実行するだけです。

于 2013-03-15T20:54:24.200 に答える
0

この問題に対する再帰的な (ブルート フォース ソリューション) は、次のようになります。

private static void combinations(int[][] matrix, int output[],int row, int col,int index,int n) {

    // base case
    if(row==n)
    {
        printArray(output,row);
        return;
    }

    for(int j=0;j<col;j++)
    {
        output[index] = matrix[row][j];
        combinations(matrix,output, row+1, col,index+1,n);
    }
    return;
}

private static void printArray(int[] output, int row) {
    for(int i=0;i<row;i++)
    {
        System.out.print(output[i]+ ", ");
    }
    System.out.println();
}

この場合、関数の組み合わせは、列の数だけ呼び出されます。列の組み合わせごとに、出力配列が出力されます。この問題の最適化についてはよくわかりません。誰かがより最適化されたアルゴリズムを知っている場合は、共有してください。

于 2014-04-26T11:01:15.837 に答える