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楼的内容,然后再想想是否可以先改变列后改变行。
页: 1 [2] 3
查看完整版本: 一道有趣但不难的题目