找回密码
 欢迎注册
楼主: lyg_wangyushi

[讨论] 一道有趣但不难的题目

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

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-13 15:09 , Processed in 0.027317 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表