Python玩转游戏之马踏棋盘问题

Python玩转游戏系列还有另外两篇文章：

今天是最后一篇文章。

这3类问题都是状态空间搜索问题，百度解释状态空间搜索是：

状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。

总结的很抽象，解释的很合理。

这一类问题可以用一个特殊的数据结构——栈，来解决。栈是一种仅允许在表的一端加入元素和删除元素的结构，也就是先入后出结构（First in last out ,FILO），元素进入（push）和元素弹出（out）在一端进行。幸运的是python的list结构可以直接当栈来使用，list的append方法和pop方法就已经实现了元素尾端压入和弹出。

递归（recursion）也可以解决，要支持递归的实现，需要一个栈来保存递归函数执行的每层调用的局部信息，留待函数调用返回后继续使用。也需要用栈，只是在源代码上看不到而已。

国际象棋的马和中国象棋的马走法一样，走日字形，假设在8*8的棋盘中有一匹马，它在棋盘中自由自在的行走，可否有一种算法，让马不重复的走完8*8的所有64个方格，每个方格只能进入一次。

定义方向，如上图所示，依次定义

定义是否可行函数：

使用深度优先搜索找路径的函数

源代码就这样，欢迎运行，只是由于需要前进和后退的次数太多，使得计算时间太长了，我计算了8*8的不知道运行了好久，也没有出结果，退而求其次，计算6*6的，如下

找到了

6*6的花了将近10秒的时间计算出结果。

7*7的大约花了一炷香（要看是那种香，不是蚊香）的时间才计算出来，足以说明，这样的计算方式是不太合理的。

下图是8*8的马踏棋盘，使用回溯（就是深度优先搜索）在10秒内，能走多少就走多少的结果：

开始位置（2,2），一开始，一马平川，马儿在棋盘上开心的奔跑着，发现前面没有路了，马上换另一条路，继续的奔跑，到了后期，已经走过的地方越来越多，马儿真的无从下脚，走到了第53个，坐标（1,0），发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯……

那有没有更科学一点的算法，答案当然是有的，就是在深度优先搜索的基础上，加上选择策略，而不是从所有落脚点上，按照逆时针顺序依次选择。这就是贪心算法。

贪心算法（greedyalgorithm）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，如何制定贪心策略？这是又一个需要解决的问题，请在草稿本上拿起纸和笔，画出一个棋盘，让我们大脑模拟一下马踏棋盘，多试几次，贪心策略一目了然，那就是：

选择，下一步能走的所有下脚点最少的点

换句话说，选择眼前认为最优的点。这里什么是最优的点，就是选择后续节点最少的那一个，哪一个点的下一步少，就选哪一个。

根据草稿本上悟出来的战略和网上的提示，代码如下：

函数howmany返回下一步nextp处所有可以走的点的数目，如果nexp本身不可走，返回0，就是探查nextp所有可走的情况。

函数chocie并不做出选择，而是返回一个list,所有点按照好坏排序，第一个点就是下一步能走的最少的点，这个list将会和pos一起入栈，做为保存搜索路径的第二个参数，也就是没有探查的未知点。

把贪心策略加入到深度优先搜索中，改造的函数如下：

在这里我详细解释一下为什么len(st)==num*num-2就退出循环并返回结果，是这样的，当走了第num*num-2步的时候，使用choice函数，下一步（num*num-1）只有一个点可以走，再下一步（num*num）已经走到终点了。当走到num*num-1步的时候，choice函数会返回啥？答案是[]，代表无路可走了！怎么办，如果不退出那就继续回溯下去……

所以len(st)最大值只能是num*num-2。那么最后一个点位置保存在哪里？其实保存在num*num-2步中choice返回的list里面。

画出结果，如下：

（完）

看完本文有收获？请转发分享给更多人

关注「Python那些事」，做全栈开发工程师