qinzuoyan

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

常用链接

留言簿(3)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

@空明流转

直接枚举法,你说的是对5040种排列依次猜测吗。。。?最坏情况下猜测次数可能5040次吧。或者你有更好的办法吗?
@东坡_居士

我觉得不应当考虑概率,而应当考虑在任意时刻,可行解集合里任何数都有可能是正确结果。实际上就是在一个状态转移图中,任何可行的路径都有可能沿着走下去,每选择一个数,就走进了一个分支。
@东坡_居士
上面公式还可以进一步修改一下:
t(F) = min{ t( F- conf(f) ) + 1, for all f belongs to F}, 其中conf(f)指与f冲突的集合(每一种返回结果就对应一个冲突集,所以复杂度又上升了)。
@东坡_居士
我猜测你也在考虑“动态规划”方法。
我考虑过“动态规划”算法,递推公式: t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是当前可行集,t(F)为该可行集 F 条件下猜出结果的次数,f 为 F 中的一个可行排列。
但是我没有编程实现,因为担心复杂度太高运行不完。但是可以保证这样能得到最优解。
贪心算法得到的应当不是最优解,但是近似最优解,而且也是可以接受的。
@东坡_居士
最好最坏就是说:每一行求最大(最坏),然后对所有行的最大值中取最小(最好)。所以计算过程还是 O(M^2) 的。
@东坡_居士


回复东坡_居士:你的算法“如果这个“提问”得到的“答案”种类越多,每个答案下面的可能数字就越少”,实际上可以通过对Clever1Palyer的进行修改实现:
34 int all_max = 0;
35 int all_max_index;
36 for (int i=0; i<M; i++) {
37 // 对于每一个可行排列 Ri
38 if (_cand[i]) { // 这一行也可以去掉
41 // cur_max 记录该当前行可行排列的关系的种数
42 int cur_max = 0;
43 for (int j=0; j<=MATCH; j++)
44 res_count[j] = 0;
45 for (int j=0; j<M; j++) {
46 if (_cand[j])
47 res_count[ (int)table[i][j] ]++;
48 }
49 for (int j=0; j<=MATCH; j++) // 求种类数
50 if (res_count[j] > 0)
51 cur_max ++;
52 // 如果 cur_max 小于全局 all_max,则更新 all_max,并记录下当前排列的序号
53 // 这样能找到种类数最多的情况
54 if (cur_max > all_max) {
55 all_max = cur_max;
56 all_max_index = i;
57 }
58 }
59 }

所以我的假设是最坏假设,你的假设是等概率假设。呵呵,你把裁判想得比较善良。
@东坡_居士

当前Clever1Player时间复杂度为 (M*M*Time) ,其中Time为猜测次数。考虑次数总小于10,所以时间复杂度为 (M^2)。

我曾经做过优化,即使用一个数组保存可行排列序号,这样在 Clever1Player 的 36 和 45 行就只需要扫描数组,而不需要每次都扫描 M 次了。当然总的时间复杂度依然是 (M^2)。

Clever2Player 与 Clever1Player 的唯一区别在于 “去掉了Clever1Player 的第 38 行”,使得“下一次猜测的排列不局限于可行排列”。
基于的考虑是:
-------------
假设正确结果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下来不能猜 4567 ,因为 4567 不在可行集中(已经排除)。
但是Clever2Player 则有可能会猜 4567 得到 0A1B,直观上说,猜测范围就缩小到 01234567 中了,搜索空间减小很多。实际上我们人脑使用逻辑推理的时候通常就是这么考虑的,而且我们肯定是不会使用这种搜索算法的。
至于逻辑推理法与搜索法之间有什么联系,我也不清楚。
-------------

另外,该算法的关注点在于猜测次数,即在于效果而不是效率。所以为了使算法看起来清晰,我没有过多优化。

NaivePlayer 算法执行时间最快,大约1分钟跑完所有,Clever1Player大约5分钟,Clever2Player大约10分钟。