关于25马问题的思考

作者:半瓶墨水   链接:http://www.2maomao.com/blog/puzzle-of-25-horses/

题酷发芽网上的一个题目 “25匹赛马血拼Top5”:

有25匹马,共5个跑道,不用任何工具,请问

  1. 用几场比赛可分出前3名?
  2. 几场比赛可以分出前5名?
  3. 几场比赛可以给所有赛马排名?

Solrex Yang同学写了一篇文章比较全面的分析了这个问题,虽然后面有人指出其推理过程中的问题,但是可以看出主要的思想还是正确的,那就是尽量利用已经存在的信息。

今天无意间翻信翻到这个问题,突然想到,这其实是个可以编程求解的问题,而且跟我已经搞定的猜数字游戏求解过程很像

几点零星的想法,等到有时间再来细化:

1. 几次赛马以后,实际上生成了一个逻辑排序的图,每一次赛马,都要尽可能的把这个图变成一条**线**
2. 贪心的标准可以是:消除尽量多的分支
3. 每一步采用贪心算法,不一定能做到全盘最优 – 我求解猜数字游戏的时候就遇到过,贪心总是会有3、4个需要8步的,而全局最优却可以做到都在7步以内
4. 如果只是前三名,或许贪心算法得到的结果跟全局最优是一致的
5. 全局最优的算法,粗略一想,需要25!的计算量。要尽量减少计算的话,就要考虑做一些cache,滤掉重复性的计算,或许需要用到动态规划
6. 如果只是要求前三名,全盘最优应该很容易做到

先写这么多,等有时间再来写程序验证。。。

留下回复