Доброго времени суток!
После прогонки бинарной матрицы через метод гаусса получаем конечную матрицу.
Вопрос такой: как из этой матрицы получить все наборы векторов-решений?
Как это сделать вручную - знаю. Но вопрос чисто в программной реализации.
Заранее спасибо!
P.S. матрица над кольцом вычетов по модулю 2.
1 ответ
Собственно, в итоге получаем приведенный ниже код.
Ответ - набор базисных решений.
Если необходимы все решения, то
"для каждого набора значений свободных переменных полученное решение есть линейная комбинация базисных с коэффициентами, равными значениям этих самых свободных переменных."
std::vector< boost::dynamic_bitset<> > Matrix(row,boost::dynamic_bitset<>(col,0));
...
//метод гаусса
std::vector<int> where(col,-1); int used_row=0;
for(int c=0,r=0;c<col && r<row;c++){
for(int i=r;i<row;i++)
if(Matrix[i][c]){
swap(Matrix[i],Matrix[r]);
break;
}
if(! Matrix[r][c]) continue;
where[c]=r; used_row++;
for(int i=0;i<row;i++)
if(i!=r && Matrix[i][c])
Matrix[i]^=Matrix[r];
r++;
}
//удаляем нулевые строки
Matrix.erase(Matrix.begin()+used_row,Matrix.begin()+row-1);
row=used_row;
//находим номера свободных и базисных переменных
std::vector<int> free;
std::vector<int> base;
int ans_num=0;
for(int i=0;i<col;i++)
if(where[i]==-1){
free.push_back(i);
ans_num++;
}
else
base.push_back(i);
//заполняем вектора ответов
std::vector< boost::dynamic_bitset<> > ans(ans_num,boost::dynamic_bitset<>(col,0));
for(int i=0;i<ans_num;i++){
ans[i][free[i]]=1;
for(int j=0;j<col-ans_num;j++)
ans[i][base[j]]=Matrix[j][base[j]]*Matrix[j][free[i]];
}
на самом деле, можно уменьшить количество прохождений по массиву, для этого мы не будем удалять нулевые строки(мы уже использовали эту память и совсем скоро ее вовсе освободим), а так же искать базисные и свободны переменные и их количество во время преобразования матрицы к ступенчатому виду:
std::vector< boost::dynamic_bitset<> > Matrix(row,boost::dynamic_bitset<>(col,0));
...
//метод гаусса
std::vector<int> base; //базисные переменные
std::vector<int> free; //свободные переменные
int ans_num=0;//количество векторов ответов, равное количеству свободных переменных
for(int c=0,r=0;c<col && r<row;c++){
for(int i=r;i<row;i++)
if(Matrix[i][c]){
swap(Matrix[i],Matrix[r]);
break;
}
if(! Matrix[r][c]){
free.push_back(c);
ans_num++;
continue;
}
base.push_back(c);
for(int i=0;i<row;i++)
if(i!=r && Matrix[i][c])
Matrix[i]^=Matrix[r];
r++;
}
//заполняем вектора ответов
std::vector< boost::dynamic_bitset<> > ans(ans_num,boost::dynamic_bitset<>(col,0));
for(int i=0;i<ans_num;i++){
ans[i][free[i]]=1;
for(int j=0;j<col-ans_num;j++)
ans[i][base[j]]=Matrix[j][base[j]]*Matrix[j][free[i]];
}
Большое спасибо VladD за помощь
-
1Для большей читаемости кода я бы разбил его на процедуры. Отдельно прямой ход, отдельно обратный, отдельно заполнение ответа. Ещё можно выделить процедуру умножения вектора-строки на вектор-столбец. Возможно, нужны ещё соответствующие классы и операции над ними. Кода станет больше, но выглядеть будет проще и более читаемо. И ещё класс «решатель СЛАУ», не передавать же всякие штуки типа количества ненулевых строк через параметры во внутренние процедуры?– VladD7 авг 2013 в 10:42
r
базисными, а остальные свободными. 2) Не забываем обратный ход. Наша матрица должна стать единичной, если рассматривать только базисные элементы. 3) К-во решений равно к-ву свободных переменных. Выписываем вектора решений: в i-ом векторе i-ая свободная переменная равна 1, ...j
-ая координата получается изj
-ого уравнения (видите?) и равна просто b_j - a_ij x_i (т.к. остальные свободные переменные равны нулю). 4) Получив все вектора решений, переставляем в них координаты по таблице из пункта 1) Вроде получается несложно. Выкладывайте код по кусочкам, подчистим, сделаем как надо. PS: Ваша картинка лучше смотрится с музыкой (только сделайте звук потише, я предупредил).