我有一个由元素组成的方阵 1
或 0。第 i 行切换会切换所有第 i 行元素（1
变为 0，反之亦然）并且第 j 列切换切换所有
第 j 列元素。我有另一个方阵
大小相似。我想将初始矩阵更改为
使用最少切换次数的最终矩阵。例如
|0 0 1|
|1 1 1|
|1 0 1|
to
|1 1 1|
|1 1 0|
|1 0 0|
需要切换第一行和最后一行
柱子。
正确的算法是什么？
一般来说，问题不会有解决方案。要看到这一点，请注意，将矩阵 A 转换为矩阵 B 相当于将矩阵 A - B（使用二进制算术计算，因此 0 - 1 = 1）转换为零矩阵。查看矩阵 A - B，并应用列切换（如有必要），以便第一行变为全 0 或全 1。此时，您已完成列切换 - 如果您切换一列，则必须切换所有列才能使第一行正确。如果此时哪怕一行是 0 和 1 的混合，则问题无法解决。如果现在每一行都是全 0 或全 1，则可以通过切换适当的行以达到零矩阵来解决该问题。
要获得最小值，请比较第一行变为 0 与 1 时所需的切换次数。在OP的示例中，候选人将切换第3列和第1行，或者切换第1列和第2列以及第2行和第3行。事实上，您可以通过查看第一个解决方案并查看切换次数是否较小或来简化此操作大于 N——如果大于 N，则切换相反的行和列。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
