Как объединить некоторые матрицы в одну? - PullRequest
Новая
       23

Как объединить некоторые матрицы в одну?

0 голосов
/ 25 марта 2019

Я пытаюсь сделать матричное умножение с делением и завоеванием. Итак, я думаю, у меня уже есть часть декомпозиции в подзадачи (рекурсивный случай и базовый случай).

Таким образом, у меня есть четыре квадранта (левый верхний, левый нижний, правый верхний, правый нижний), и я думаю о том, как объединить их в матрицу результатов, и у меня нет идеи.

Я работаю с Java, поэтому у меня есть matrixA и matrixB, и у меня есть некоторые индексы, такие как matrixRowsA, matrixColumnsA, matrixRowsB, matrixColumnsB

Таким образом, я избегаю создания новой матрицы и всего такого, что только удорожает решение проблемы.

Итак, основной вопрос: как объединить 4 подматрицы в заполненную?

Таким образом, метод является вызовом divAndConquer: 

private static int[][] divideAndConquer(int[][]matrixA, int beginRowsA, int endRowsA, int beginColumnsA,
                                        int endColumnsA, int[][]matrixB, int beginRowsB, int endRowsB,
                                        int beginColumnsB, int endColumnsB)
{
    // Base case
    if(lengthOfBothMatrix()==1)
    {
        return multiplyMatrix(matrixA,matrixB);
    }
    }
    else
    {
        int middleRowsA = obtainMiddleRowsB();
        int middleColumnsA = obtainMiddleColumnsA();
        int middleRowsB = obtainMiddleRowsB();
        int middleColumnsB = obtainMiddleColumnsB();

        int[][] leftSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA, matrixB, beginRowsB,
                middleRowsB, beginColumnsB, middleColumnsB),
                divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
        int[][] leftInferiorQuadrant = matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB,middleRowsB, beginColumnsB, middleColumnsB),
                divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));

        int[][] rightSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
                divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
        int[][] rightInferiorQuadrant =matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
                divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));

Я тестирую с двумя матрицами вроде: 

1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 

1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 |

Ответы [ 2 ]

1 голос
/ 25 марта 2019

Я все еще хотел:

  • чтобы указать, что деление в разделяй и властвуй должно быть вдоль линий "разрыва" (умножения) алгоритма;
  • чтобы упомянуть хороший массив класс.

Выполнение разумного деления , самое ленивое усилие, важно. Для умножения матриц более подходящим является разделение на две части:

Очень схематично: 

A: (3x5)      B: (5x3)    A x B: (3x3)
a a b b b     c c c       ... ac ... bd ...
a a b b b     c c c      
a a b b b     d d d      
              d d d
              d d d

Как видите, вы можете разделить задачу на Aa x Bc и Ab x Bd, а затем аккуратно объединить результаты.

Это достаточно сложно, а также легко понять.

Другой совет - использовать более математические короткие имена для удобства чтения. Хотя обычно следует использовать достаточно длинные имена, а курс может потребовать иного. 

int[][] multiply(int[][] a, int[][] b) {
    int rows = a.length;
    int cols = b[0].length;
    int terms = b.length:
    if (terms != a[0].length) {
        throw new IllegalArgumentException(
            "Dimensions do not match: " + a[0].length + " != " + terms);
    }
    int[][] product = new int[rows][cols];
    if (terms < 2) { // Cannot divide
        if (terms == 1) {
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    product[i][j] = a[i][0] * b[0][j];
                }
            }
        }
    } else {
        int half = terms/2;

        int[][] aLeft = new int[rows][half];
        int[][] bTop = new int[half][cols];
        ... fill using Arrays.copyOfRange ...
        int[][] prodLT = multiply(aLeft, bTop);

        int[][] aRight = new int[rows][terms - half];
        int[][] bBottom = new int[terms - half][cols];
        ... fill using Arrays.copyOfRange ...
        int[][] prodRB = multiply(aRight, bBottom);

        ... add prodLT to prodRB into product
    }
    return product;
}
1 голос
/ 25 марта 2019

Во-первых, вы можете вертикально объединить левые матрицы (leftSuperiorQuadrant & leftInferiorQuadrant) и правые матрицы (rightSuperiorQuadrant & rightInferiorQuadrant) в матрицы новых столбцов с System.arraycopy () : 

    int leftSuperiorQuadrant [][] = {{1, 2}, {3, 4}};
    int rightSuperiorQuadrant [][] = {{5, 6}, {7, 8}};
    int leftInferiorQuadrant [][] = {{9, 10}, {11, 12}};
    int rightInferiorQuadrant [][] = {{13, 14}, {15, 16}};

    int m_intermediate_left[][] = new int[leftSuperiorQuadrant.length+leftInferiorQuadrant.length][];
    int m_intermediate_right[][] = new int[rightSuperiorQuadrant.length+rightInferiorQuadrant.length][];

    // Concat leftSuperiorQuadrant and leftInferiorQuadrant in column
    System.arraycopy(leftSuperiorQuadrant, 0, m_intermediate_left, 0, leftSuperiorQuadrant.length);
    System.arraycopy(leftInferiorQuadrant, 0, m_intermediate_left, leftSuperiorQuadrant.length, leftInferiorQuadrant.length);

    // Concat rightSuperiorQuadrant and rightInferiorQuadrant in column
    System.arraycopy(rightSuperiorQuadrant, 0, m_intermediate_right, 0, rightSuperiorQuadrant.length);
    System.arraycopy(rightInferiorQuadrant, 0, m_intermediate_right, rightSuperiorQuadrant.length, rightInferiorQuadrant.length);

    System.out.println(Arrays.deepToString(m_intermediate_left));
    System.out.println(Arrays.deepToString(m_intermediate_right));

Возвращает:

[[1, 2], [3, 4], [9, 10], [11, 12]] 

1  | 2
3  | 4
9  | 10
11 | 12

[[5, 6], [7, 8], [13, 14], [15, 16]] 

5  | 6   
7  | 8  
13 | 14 
15 | 16

Затем вы можете вручную объединить получающиеся матрицы по горизонтали: 

    int m_final[][] = new int[m_intermediate_left.length][m_intermediate_left[0].length+m_intermediate_right[0].length];

    // For each row of the final matrix
    for(int i = 0; i < m_final.length; i++) {
      // For each column of the final matrix     
      for (int j = 0; j < m_final[0].length; j++) {
        // If j corresponds to the left columns, add left matrix values 
        if (j < m_intermediate_left[0].length) {
            m_final[i][j] = m_intermediate_left[i][j];
        }
        // If j corresponds to the right columns, add the right matrix values
        else {
            m_final[i][j] = m_intermediate_right[i][j - m_intermediate_left[0].length];
        }
      }
    }

    System.out.println(Arrays.deepToString(m_final));

Возвращает матрицу ваших желаний:

[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]] 

1  | 2   | 5  | 6 
3  | 4   | 7  | 8
9  | 10  | 13 | 14
11 | 12  | 15 | 16

Обратите внимание, что это не будет работать, если ваши квадранты имеют разные размеры.

Best

...