(无法使 sigma 符号在浏览器上看起来不错)。
对于整数n，我们将F_n标记为单射函数群
f:{1,2,3…,n}→{1,2,3…,n}
对于 nXn 阶非负值的给定矩阵 A，我们将标记:
P(A)=∑_(f∈F_n)▒〖A_(1,f(1))*A_(2,f(2)) 〗…*A_(1,f(1) )*A_(n,f(n))
设计一个多项式算法来确定是否 P(A)=0。
我正在考虑在矩阵中寻找 n^2-n+1 零，然后在任何排列中，乘积中都会有零，然后总和将为零，这就是 O 的运行时间(n^2)。不确定解决方案。
有什么想法吗？
谢谢
例子:
最佳答案
你的问题是“有没有办法将 N 只车放在 NxN 的棋盘上，这样它们就不能互相攻击，同时避开标记的(零)方格。”的补充。
例如，如果一行或一列全为零，那么它是不可能的并且 P(A) = 0，因此寻找 n^2 - n + 1 个零并不能解决问题。
然而，这里有一个答案，它给出了这个问题的一个可爱的多项式时间解决方案:https://cs.stackexchange.com/questions/28413/how-hard-is-this-constrained-n-rooks-problem
关于algorithm - 矩阵置换的多项式算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49113272/