形而上学，学无止境

今天在队长的带领下，学习了马踏棋盘算法。

一、马踏棋盘算法的介绍

1.马踏棋盘算法也称为骑士周游问题。

2.将马随机放在国际象棋的8 × 8棋盘Board[0~7] [0~7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

二、马踏棋盘算法的基本思路

1.马踏棋盘问题（骑士周游世界问题）实际上是图的深度优先搜索(DFS)的应用。

2.如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了第53个，发现已经走到了尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停回溯…效率很低。

3.因此需要使用贪心算法（greedyalgorithm）进行优化。直接使用贪心算法，优化思路来解决马踏棋盘问题。

三、马踏棋盘算法的步骤

1.创建棋盘chessBoard，是一个二维数组。

2.将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList)，最多有8个位置。

3.遍历ArrayList中存在的所有位置，看看哪个可以走通；如果走通，继续，走不通，就回溯。

4.判断马儿是否完成任务了任务step和应该走的步数比较。

注意：马儿的不同走法（策略），会得到不同的结果，效率也会有影响（优化）。

学习算法，应该有打破砂锅问到底的精神，正所谓"形而上学，学无止境"。

http://www.dxsbao.com/shijian/474025.html 点此复制本页地址