lyg_wangyushi
发表于 2008-1-14 14:47:44
那如果改变列的状态,对应这样的情况该怎么办?
[ 本帖最后由 lyg_wangyushi 于 2008-1-14 14:50 编辑 ]
mathe
发表于 2008-1-14 15:00:44
任意改变行列的顺序都是可以交换的,交换它们不改变结果。
同样,对于同一行或列改变两次以上也没有意义,改变两次等于不改变。
所以最终我们只需要判断:
某些列需要改变和某些行需要改变。
而所有列是否改变总共构成2^9=512种情况,我们对这512种情况都计算最优结果就可以了
对于每种情况,就都只牵涉到行变换,非常简单
lyg_wangyushi
发表于 2008-1-14 15:31:23
啊,我理解了mathe得意思了,但这样是不是开销太大了一点
lyg_wangyushi
发表于 2008-1-14 15:46:36
to mathe
希望以后能够多多得到您的指教。真高兴认识您这样一位算法这么强,人品又这么好的人。
mathe
发表于 2008-1-14 16:52:19
512倍对于现在的计算机应该没有问题。
而对于给定列变换的情况,求解非常简单,只要查看每行朝上多还是朝下多
也就是时间复杂独为O(m*2^n),其中m为行数目,n为列数目
lyg_wangyushi
发表于 2008-1-14 17:25:31
看样,枚举还真是个好方法。谢谢mathe
lijeki
发表于 2008-1-14 19:20:16
我觉得O(m*2^n)里面的m还可以排列一下,应该为O(m!*2^n)
lyg_wangyushi
发表于 2008-1-15 08:25:40
每一种控制行不变,只改变列的情况,只要检查每一行是否反面多于正面就可以了。
也就是对应确定的先改变列的状况,只要检查所有的行,所以不用对行进行排列。
lijekk
发表于 2008-1-15 09:49:19
嗯,先改变列反面较多,再改变行,是不错
但是改变行之后,列又发生变化,然后改变列,再改变行,一直循环
这样复杂度为n+m+n+m+............
不过如果反过来首先改变行再改变列的话,得到的结果可能会跟上面的不同,也就是说上面得到的不一定是最优解
还可以先把反面的聚集到几个行或几个列再统一翻转
要完全遍历的话恐怕得 2^m * 2^n才行
mathe
发表于 2008-1-15 10:10:13
lijekk可以先仔细阅读一下我在12楼的内容,然后再想想是否可以先改变列后改变行。