如何在c中实现Laplace展开算法? [英] How do I implement the Laplace expansion algorithm in c?
问题描述
由于无法弄清楚问题的中间部分，我无法找出一种使该算法起作用的方法.到目前为止，这是我的代码:
I'm having trouble figuring out a way to make this algorithm work, as I can't figure out how to do the middle part of the problem. Here's my code so far:
int det(int matrixSize, int matrix[][matrixSize]){
int determinant = 0, matrixValues[matrixSize * matrixSize], matrixFirstRowValues[matrixSize * matrixSize];
for(int i = matrixSize; i > 2; i--){
for(int row = 0; row < matrixSize; row++){
for(int col = 0; col < matrixSize; col++){
matrixFirstRowValues[row + (matrixSize - i)] = matrix[1][col + (matrixSize - i)];
//copies the first row values for an array until we have a 2x2 matrix
}
}
}
//multiply the values in matrix Values by their respective matrix without
//the row and column of these values times -1^row+col
determinant += (matrix[matrixSize-1][matrixSize-1] * matrix[matrixSize-2][matrixSize-2])
- (matrix[matrixSize-1][matrixSize-2] * matrix[matrixSize-2][matrixSize-1]);
return determinant;
}
作为矩阵，它是一个具有matrixSize大小的二维数组，我对其进行迭代，直到剩下2x2矩阵，然后将第一行的每个值复制到一个新数组中.
Being the matrix, a 2-dimensional array with the size of matrixSize, I iterate through it until I'm left with a 2x2 matrix, copying each value of the first row to a new array.
当我删除该值所在的行和列时，这些值必须乘以它剩下的矩阵.
Those values have to be multiplied by the matrix that it's left when I remove the row and column where that value is.
这是拉普拉斯扩展的原理.给我带来麻烦的部分是通过删除行和列来获取剩余的矩阵，因为我希望它可以用于nxn矩阵.
This is the principle of the laplace expansion. The part that's giving me trouble is getting those matrices that are left by removing rows and columns, as I want this to work for a nxn matrix.
然后，最后求和到2x2矩阵的总和.
Then, in the end the sum that to the det of a 2x2 matrix.
如何使用当前设置处理中间部分(注释在哪里)?
How can I do the middle part (where the comments are) with my current setup?
推荐答案
这些值必须乘以我留下的矩阵删除该值所在的行和列.
Those values have to be multiplied by the matrix that it's left when I remove the row and column where that value is.
在删除第i行和第j列时，必须乘以其因子为矩阵的行列式的辅因子矩阵.
You have to multiply with the cofactor matrix whose entries are the determinants of the matrices that are left over when removing the i-th row and j-th column.
自然，这是递归算法的设置，因为较大矩阵的行列式是用较小矩阵的行列式表示的:如果 A =(a_ {ij})是矩阵，则 det(A) = sum j = 1..n: a_{ij} * det(M_{ij})，其中 M_{ij} 是当删除固定 i 的第 i 行和第 j 列时由A产生的次矩阵.基本情况是2×2矩阵，也可能是3×3矩阵.
Naturally, this is the setup for a recursive algorithm, since the determinant of the bigger matrix is expressed in terms of the determinants of smaller matrices: if A = (a_{ij}) is the matrix, then det(A) = sum j = 1..n: a_{ij} * det(M_{ij}), where M_{ij} is the minor matrix that arises from A when removing the i-th row and j-th column where i is fixed. The base case being the 2-by-2 matrices, maybe also 3-by-3 matrices.
出现的问题是n×n矩阵产生n个矩阵M_{ij}(n-1)-(-n-1)，每一个都产生尺寸小于1的 n-1 矩阵，依此类推，直到达到基本情况为止，此时您将必须跟踪 n！/2 个矩阵.(在这一点上，很明显，拉普拉斯扩展是一种成本很高的算法，任何基于高斯消去的算法都将效率更高.但这只是一个旁听，因为我们正在讨论拉普拉斯扩展.)如果以迭代的方式进行，这必须手动完成，递归算法将具有通过堆栈框架进行簿记的隐式方式.
The problem that arises is that an n-by-n matrix produces n matrices M_{ij} of size (n-1)-by-(n-1), each of which produces n-1 matrices of size one less and so on until the base case is reached, at which point you'll have to keep track of n!/2 matrices. (It becomes apparent at this point that Laplace expansion is a rather costly algorithm, any algorithm based on Gauss elimination will be far more efficient. But that is just an aside, since we are discussing Laplace expansion.) If done in an iterative fashion, this has to be done manually, a recursive algorithm will have implicit means of bookkeeping via stack frames.
您的方法
让我们看看您提供的代码段.它使我难以理解您正在努力实现的目标.例如，最内层循环中的语句遍历 col :
Let's have a look at the piece of code that you have provided. It eludes me what precisely you are trying to achieve. Take for instance the statement in the innermost loop which iterates over col:
matrixFirstRowValues[row + (matrixSize - i)] = matrix[1][col + (matrixSize - i)];
只要最内层循环中的 col 发生变化， row 和 i 都是固定的，因此您要从(显然)在 matrix 中的第二行到 matrixFirstRowValues 中的相同条目.不仅如此，您还从超出列范围的索引范围 (matrixSize-i) .. (2*matrixSize - (i+1)) 中进行分配，除非 i == matrixSize，只有 i 的第一个值才是这种情况.
For as long as col changes in the innermost loop, both row and i are fixed, so you are assigning and reassigning from (apparently) the second row in matrix to the same entry in matrixFirstRowValues. Not only that, you assign from an index range (matrixSize-i) .. (2*matrixSize - (i+1)) which exceeds the range of the column unless i == matrixSize, which is only the case for the first value of i.
正如我之前提到的，最后，您不会仅得到一个2×2矩阵，而是 n！/2 .
As I mentioned before, in the end you do not end up with just one 2-by-2 matrix but n!/2.
正在复制除第i行和第j列
看一下删除了第 i 行和第 j 列的矩阵，最后得到四个子矩阵(其中一些可能为空).限制自己沿第一行扩展，然后您只需要处理两个子矩阵(其中一些可能仍然是空的).您可以使用两个循环，一个循环用于第 j 列左侧和右侧的矩阵-或者，如上一个答案中的建议-选择跳过 j 个列，使用 continue 循环循环而不更新目标列索引.如果 col 标记要删除的当前列(当前行始终为0)，则在所有行上迭代 r ，并在所有列上迭代 c 在 c == col 处将列循环分成两部分.假设目标矩阵称为 minor ，那么它看起来像这样:
Looking at the matrix with i-th row and j-th column removed, you end up with four submatrices (some of which may be empty). Restricting yourself to expansion along the first row, then you are dealing with just two submatrices (still some of which may be empty). You may use two loops, one for the matrix to the left of the j-th column and to the right - or, as suggested in a previous answer - choose to skip the j-th column using continue to cycle the loop without updating the target column index. If col marks the current colum to remove (the current row is always 0), iterate r over all rows, and c over all columns and break the column loop in two pieces at c == col. Let's say, the target matrix is called minor, then it would look like this:
// expand along first row
for(col = 0; col < matrix_size; col++) {
// copy into minor matrix, left side then right side
for(r = 1; r < matrix_size; r++) {
for(c = 0; c < col; c++) {
minor[r-1][c] = matrix[r][c];
}
for(c = col+1; c < matrix_size; c++) {
minor[r-1][c-1] = matrix[r][c];
}
}
// use "minor" matrix at this point to calculte
// its determinant
}
索引移位 r-1 是由于删除了第一行.
The index shift r-1 is due to the removal of the first row.
一个完整的拉普拉斯递归扩展
正如我之前提到的那样，行列式的拉普拉斯展开自然适合于递归算法.我将对您的设置进行一些更改，我将不使用堆栈分配的可变长度数组，而是使用堆分配的内存.由于扩展(如果不重新使用该空间)具有指数空间要求，因此对于中等大小的矩阵，堆栈可能很快就已耗尽.因此，我将需要一个附加参数来通过意图输出参数(我称为 is_valid .
As I mentioned before, the Laplace expansion of the determinant lends itself naturally to a recursive algorithm. I will do some changes to your setup, i will not use variable length arrays which are stack allocated, I will instead use heap allocated memory. Since the expansion, if the space is not reused, has an exponential space requirement, the stack might quickly get exhausted already for matrices of moderate size. Consequently, I will need an additional parameter to report back memory allocation failures via an intent out parameter which I call is_valid.
由于我对堆上的n×n矩阵进行运算，因此您将认识到上述矩阵复制过程，其中的名称略有不同，并附加了指针取消引用.我希望它不会引起太多混乱.
You will recognise the above matrix copy procedure with a little different names and an additional pointer dereference, since I operate with n-by-n matrices on the heap. I hope it will not lead to too much confusion.
#include <stdio.h>
#include <stdlib.h>
#define SQR(x) ((x)*(x))
int laplace_det(int matrix_size, const int (*mat)[][matrix_size], int *is_valid) {
// base cases
if(matrix_size == 1)
return (*mat)[0][0];
if(matrix_size == 2)
return (*mat)[0][0] * (*mat)[1][1] - (*mat)[1][0] * (*mat)[0][1];
// recusive case, matrix_size > 2
// expansion indiscriminately along the first row
//
// minor matrix with i-th row and j-th column
// removed for the purpose of calculating
// the minor.
// r, c row and column index variables
// col current column in expansion
// d determinant accumulator
//
int r, c, col, d = 0;
int (*minor)[matrix_size-1][matrix_size-1] = calloc(SQR(matrix_size-1), sizeof(int));
if(!minor) {
*is_valid = 0;
return 0;
}
// expand along first row
for(col = 0; col < matrix_size; col++) {
// copy into minor matrix, left side then right side
for(r = 1; r < matrix_size; r++) {
for(c = 0; c < col; c++) {
(*minor)[r-1][c] = (*mat)[r][c];
}
for(c = col+1; c < matrix_size; c++) {
(*minor)[r-1][c-1] = (*mat)[r][c];
}
}
// calculate minor
int temp_d = laplace_det(matrix_size-1, minor, is_valid);
if(!is_valid) {
free(minor);
return 0;
}
d += (col & 1 ? -1 : 1) * (*mat)[0][col] * temp_d;
}
// free resources
free(minor);
return d;
}
示例驱动程序:
int main(void) {
int is_valid = 1;
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int det_m = laplace_det(3, &matrix, &is_valid);
if(is_valid) {
printf("determinant %d\n", det_m);
}
}
迭代方法
如果要迭代地执行相同的操作，则需要为所有较小尺寸的 n-1 个子矩阵提供空间.如递归情况所示，您可以为 same 大小的所有子矩阵重用相同的空间，但是您不能将该空间用于较小大小的矩阵，因为每个矩阵都必须生成所有较小一个大小的子矩阵，每列一个.
If you wanted to do the same thing iteratively, you will need to provide space for all n-1 submatrices of smaller size. As the recursive case shows, you can reuse the same space for all submatrices of the same size, but you cannot use that space for matrices of smaller size because each matrix has to spawn all submatrices of size one smaller, one for each column.
由于事先不知道矩阵的原始大小，因此很难以一般方式遍历所有这些矩阵，并且需要大量记账，因此我们免费获得了将这些值分别保存在递归的各个堆栈框架中案件.但是我想将当前的列选择器保持在一个 matrixSize 大小的数组以及一个指向子矩阵的指针数组中，就可以迭代地重写它.
Since the original size of the matrix is not known beforehand, traversing all these matrices in a general way is difficult to realise and will require a lot of bookkeeping that we get for free keeping these values in their respective stack frames in the recursive case. But I suppose keeping the current column selector in an array of size matrixSize, as well as an array of pointers to the submatrices, it will be possible to rewrite this iteratively.
这篇关于如何在c中实现Laplace展开算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
