半瓶墨水 - 任中方

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

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

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

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

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

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

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

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

十一月 22nd, 2009 | 分类: 原创精选, 编程随笔 | 阅读(1637) | | (给个分吧)  Loading ...