十步万度的另一种解法:遗传算法+贪心

不一样的五四，从玩游戏开始。

闲逛Tap时偶遇这个游戏，刚好最近学校学了遗传算法，感觉遗传算法灰常神器啊，就尝试用它来玩十步万度。

会代码的可以转站CSDN博客，不会代码往下看也能看懂。最后会展示所有关卡的解。

简单介绍遗传算法:

从名字来看，遗传算法借用了生物学里达尔文的进化理论：”适者生存，不适者淘汰“。

这样不断让种群玩游戏，分数高者易存活，一代代下去会不断逼近分数高的解。

简单介绍贪心:

贪心策略：玩家非常贪心，每次点击前都会预判所有情况，从中选出得分最高的，每步都是当前看来最好的选择。(局部最优)

但显然次次局部最优不一定能达到全局最优。

大概过程就是先用遗传算法得到解，再对解贪心一次，可以保证这次贪心是当前解的最优选择。

详细过程见上面的博客链接。

不再啰嗦，直接来看所有关卡的最优解吧。

但首先要能看懂解啊，很简单。

对关卡里的指针从0开始，从左到右，从上到下编码:

对指针编码后就能用一个数表示玩家点击的是哪个指针了。

再把那些数按顺序存储，就能表示玩家的操作了。

如图，玩家先点0号指针五次，再点3号指针5次。

终于可以看各关卡的最高分和解了:

注意:指针编码是从0开始，别数错了！

20000关以后的会随机改变指针初状态要手动修改代码就没运算了。

可能有些关卡运算的很粗略，再多点时间说不定还能得到更优解。

达到这些分数的解不止一种，例如第一关能达到2070的就算出2万多个不重复的解，而且还在不断得到新的解。

在后面难度高的关卡有的感觉已经不能再得到更高的分数了，开始怀疑是不是作者也没有解出来

算法更详细的缺陷见上面的博客链接。

一句话总结解法:不断让种群玩游戏，分数高者易存活，一代代下去不断逼近分数高的解，最后贪心遍历一下。

最后，期待看到十步万度更多更好的解法。