1

ガウス消去法のバージョンをプログラムして、一連のバイナリ ベクトルの線形独立性を検証しました。評価して返す行列 (mxn) を入力します。

  • True (線形独立): ゼロ行は見つかりませんでした。
  • False (線形依存): 最後の行がゼロの場合。

常に、または少なくともほとんどうまく機能しているようです。行列の最後の行に2 つの重複したベクトルがある場合、機能しないことがわかりました。

std::vector<std::vector<int>> A = {
    {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1 },
    {0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 },
    {0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 },
    {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},   // <---- duplicated
    {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},}; // <---- duplicated
gaussianElimination_binary(A);

この関数は、行列が「線形独立」であることを示しています。これは、ゼロ行が見つからず、結果に実際に存在するためです。しかし、デバッグすると、ある時点で行がゼロになることがわかりましたが、その後、いくつかの行操作の後、「通常」に戻ります。

私はコードを再確認しましたが、それを機能させる唯一の方法は、プロセスの終了前、より正確には行操作中に「ゼロ行」が見つかった場合にも「false」を返すことでした:

// perform XOR in "k-th" row against "row-th" row
    for (int k = 0; k <= max_row; ++k) //k=col_pivot?
    {
        if ( (k != row)   )
        {
            int check_zero_row = 0; // <---- APPLIED PATCH
            for (std::size_t j = 0; j <= max_col; j++) {
                B[k][j] = B[k][j] ^ B[row][j];
                check_zero_row = check_zero_row | B[k][j];
            }
            if (check_zero_row == 0 ) // <---- APPLIED PATCH
            {
                return false;
            }
        }
    }

これが正しいのか、それとも悪いコードに「パッチを当てている」だけなのか知りたいです。

ありがとうございました！

以下の完全なコード:

#include vector
bool gaussianElimination_binary(std::vector<std::vector<int>> &A) {
std::vector<std::vector<int>> B = A;
std::size_t max_col = B[0].size() - 1;      //cols
std::size_t max_row = B.size() -1 ;     //rows
std::size_t col_pivot = 0;

//perform "gaussian" elimination
for (std::size_t row = 0; row <= max_row; ++row) //for every column
{
    if (col_pivot > max_col)
        break;

    // Search for first row having "1" in column "lead"
    std::size_t i = row; //Start searching from row "i"=row
    while (B[i][col_pivot] == 0)
    {
        ++i;
        if (i > max_row) // no "1" was found across rows
        {
            i = row;        // set "i" back to "row"
            ++col_pivot;    // move to next column
            if (col_pivot > max_col) //if no more columns
                break;
        }
    }

    // swap "i" and "row" rows
    if ((0 <= i) && (i <= max_row) && (0 <= row) && (row <= max_row)) {
        for (std::size_t col = 0; col <= max_col; ++col) {
            std::swap(B[i][col], B[row][col]);
        }
    }

    // perform XOR in "k-th" row against "row-th" row
    for (int k = 0; k <= max_row; ++k) //k=col_pivot?
    {
        if ( (k != row)   )
        {
            int check_zero_row = 0;
            for (std::size_t j = 0; j <= max_col; j++) {
                B[k][j] = B[k][j] ^ B[row][j];
                check_zero_row = check_zero_row | B[k][j];
            }
            if (check_zero_row == 0 )
            {
                return false;
            }
        }
    }
}

return true;
}
4

0 に答える 0