本帖最后由 523066680 于 2017-08-30 10:23 编辑
回复 7# rubyish
估值。
普通的筛选法,是在每一层,在可选元素中选第一个,没有任何优化。
这种方案测完5040种情况的统计结果大致如下,平均需要猜 5.56 次:
- Times: 28024, average: 5.560317
- 1, 1
- 2, 13
- 3, 108
- 4, 596
- 5, 1668
- 6, 1768
- 7, 752
- 8, 129
- 9, 5
复制代码
如果在每一层,我们在可选数字中,做一些判断,把判断为较好的数字选为下次测试的数字,最大回合数/平均回合数就能减少。
比如百度百科提到的最大反馈指标:用子集合中的每一个元素去碰撞集合,看哪一个数字碰撞时得到更多的反馈类型
举个例子,当前缩小集合是 S = (1032,1230,1302,2031,2301,2310,3012,3201,3210)
用这些元素分别碰撞整个数组,得到不同的反馈,反馈越多的,说明下一层子集合的平均量越小。(当前总数/反馈数)
1032 - 04,22,40
1230 - 04,22,13,40
1302 - 04,13,22,40
2031 - 13,04,40,22
2301 - 04,22,40
2310 - 22,13,04,40
3012 - 04,22,13,40
3201 - 04,13,22,40
3210 - 04,22,40
按这种方案,可以选 1230,1302,2310,3012,3201 中的一个。当然,还可以进一步优化,做更准确的的评估。
以及碰撞的集合不一定是在 S集合内,可以是整个5040种排列和 S集合碰撞
使用最大反馈估值(在较高估值的结果中选第一项),测试结果是:
- Times: 27139, average: 5.384722
- 1, 1
- 2, 3
- 3, 44
- 4, 515
- 5, 2124
- 6, 2151
- 7, 202
复制代码
|