1. 算法优化意义 904
1.算法是程序的灵魂，为什么有些程序可以在海量数据计算时，依然保持高速计算?
2.在Unix下开发服务器程序，功能是要支持上千万人同时在线，在上线前，做内测，一切OK，可上线后，服务器就支撑不住了，公司的CTO对代码进行优化，再次上线，坚如磐石。那
一瞬间,你就能感受到程序是有灵魂的，就是算法。
3.编程中算法很多，比如八大排序算法(冒泡、选择、插入、快排、归井，希尔、基数、堆排序)、查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法
4.以骑士周游问题为例，让小伙伴体验用算法去优化程序的意义，让大家直观的感受到算法的威力
2. 经典算法面试题-骑士周游问题 904
2.1 马踏棋盘算法介绍和游戏演示
1.马踏棋盘算法也被称为骑士周游问题
2.将马随机放在国际象棋的8 x 8棋盘Board[0 ~ 7][0 ~ 7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格
3.游戏演示:
https://u.ali213.net/games/horsesun/index.html?game code=403
4. 会使用到图的遍历算法(DFS) +贪心算法优化
2.2 马踏棋盘算法介绍和游戏演示
1. 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
2. 如果使用回溯(就是深度优先搜索)来解决，假如马儿踏了53个点，如图:走到了第53个，坐标(1,0) ,发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回.... ,思路分析+代码实现
3. 先用基本方式来解决，然后使用贪心算法(greedyalgorithm) 进行优化。解决马踏棋盘问题，体会到不同的算法对程序效率的影响
4. 使用前面的游戏来验证算法是否正确
3. 代码实现 普通方法 906
3.1 思路分析 905
骑士周游问题的解决步骤和思路分析
1.创建棋盘chessBoard,是二维数组
2.将当前位置设置为已经访问,然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList),最多有8个，每走一步，使用step + 1
3.遍历ArrayList中存放的所有位置，看看那个可以走，如果可以走通，就继续，走不通，就回溯
4.判断马儿是否完成了任务，使用step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘设置为0
代码在com.stulzl.horse_chessboard
HorseChessBoard
package com.stulzl.horse_chessboard;
import java.awt.*;
import java.util.ArrayList;
//马踏棋盘 906
public class HorseChessBoard {
//定义属性
private static int X = 6;//表示列col就是横坐标
private static int Y = 6;//表示行row就是纵坐标
private static int[][] chessBoard = new int[Y][X];//二位定义数组棋盘
private static boolean[] visited = new boolean[X*Y];//记录某个位置是否走过
private static boolean finished = false;//记录马儿是否遍历完棋盘
public static void main(String[] args) {
//测试
//起始坐标，只要起始坐标不变结果就不变
int row = 5;
int col = 5;
long start = System.currentTimeMillis();
traversalChessBoard(chessBoard,row-1,col-1,1);
long end = System.currentTimeMillis();
System.out.println("遍历耗时="+(end-start));
//输出当前这个棋盘的情况
//增强for,解释，把二维数组当成几个一维数组，即每行是一个一维数组，然后遍历一维数组
for(int[] rows : chessBoard){
for (int step : rows){
System.out.print(step+"\t");
}
System.out.println();
}
//普通for
// for (int i = 0; i < chessBoard.length; i++) {
// for (int j=0;j
// System.out.print(chessBoard[i][j]+"\t");
// }
// System.out.println();
// }
}
//编写最核心的算法，遍历棋盘，如果成功遍历，就把finished设置位true，并且 907
//将马儿走的每一步step，记录到chessBoard二维数组中
public static void traversalChessBoard(int[][] chessBoard,int row,int col,int step){
//先把step记录到chessBoard中
chessBoard[row][col] = step;
//把这个位置设置为已经访问，就是走过了，可以走通，但是走过了，就不用再走了
visited[row*X+col] = true;
//获取当前这个位置可以走的下一个位置有哪些
ArrayList ps = next(new Point(col, row));//注意col是纵坐标即Y,row是横坐标即X
//遍历
while(!ps.isEmpty()){//如果集合不为空，就进入循环，然后取出集合里的点
//解释：取出这个ps集合中的第一个位置(点)(因为remove(0) 0就代表当前集合的第一个元素的索引)
// ，这里我们取出的点是用的remove删除(解释为什么边取边删除，因为边取边删我们的ps集合将
// 会越来越小，意思是删掉原来的第一个元素 即索引0对应的元素，后面的第二个元素就变成了第一个元素，
// 就好像集合往前走了一样的感觉，这样边取边删就可以取出集合中的所有元素，还因为我们不知道集合中
// 到底有多少个元素，(因为下一步是否合法不确定)就不能用具体的0，1，2……等为索引取出相关数据，
// 而边取边删就可以，因为删完就结束了)，
// 因为进入循环是用的判断集合是否空作为条件，当我们将当前点的下一步位置的集合边取边删完后
// ，这个点的集合就不用在进入循环判断了
Point p = ps.remove(0);//从集合中取出一个点，边取边删的返回值就是这个被删除的点的数据
//判断该位置是否走过，如果没有走过，我们就让该点递归遍历
//解释p.y对应row横坐标，p.x对应col纵坐标
if(!visited[p.y*X+p.x]){//如果不等于true，即false，false就是没有走过
//该点没走过,就将该点作为当前点(因为我们这个点是从集合中取出来的，就是“下一位合法点”，
// 要进入递归，就将该点作为当前点) 进入递归
traversalChessBoard(chessBoard,p.y,p.x,step+1);
}
}
//当推出while循环后，看看是否遍历成功，如果没有成功，就重置相应的值，然后进行回溯
//解释!finished及为true,因为我们的finished初始值为false，而finished表示游戏结束，我们将
//!finished及为true就表示游戏还没结束
if(step<X*Y && !finished){//表示游戏没结束可进入循环
//重置
//既然走不通将回溯到该点(注意该点并不一定值起始点，也有可能是递归中的某个分支点)
chessBoard[row][col] = 0;
visited[row*X+col] = false;//置为false就当该点没走过
}else{
finished = true;//成功结束游戏
}
}
//编写一个方法，可以获取当前位置，可以返回下一步所有合法点位置(Point表示x,y) 906
public static ArrayList next(Point curPoint){//curPoint当前位置
//创建一个ArrayList，用来盛放当前坐标curPoint，周围下一步符合合法规则的点(最多8个点)
ArrayList ps = new ArrayList<>();
//创建一个Point对象(点/位置),如果该点坐标合法符合规则，放入到ps集合
Point p1 = new Point();//这个p1就是curPoint下一步的合法点
//判断在curPoint是否可以走如下位置，如果可以走即合法，就将该点(Point)放入到ps
//判断是否可以走5位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走6位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走7位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走0位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走1位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走2位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走3位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走4位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
return ps;
}
}4. 代码实现 贪心算法 908
4.1 思路分析 908
1.我们现在走的下一个位置，是按照我们的顺时针来挑选位置，因此选择的这个点的下一个可以走的位置的个数是不确定的.
2.优化思路是:我们应该选择下一个的下一个可以走的位置较少的点，开始走，这样可以减少回溯的此时
3.代码:对我们的ps集合按照可以走的下一个位置的次数进行排序，升序排序
代码在com.stulzl.horse_chessboard_pro 908
HorseChessBoardPro
package com.stulzl.horse_chessboard_pro;
import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
//马踏棋盘 贪心算法版 908
public class HorseChessBoardPro {
//定义属性
private static int X = 6;//表示列col就是横坐标
private static int Y = 6;//表示行row就是纵坐标
private static int[][] chessBoard = new int[Y][X];//二位定义数组棋盘
private static boolean[] visited = new boolean[X*Y];//记录某个位置是否走过
private static boolean finished = false;//记录马儿是否遍历完棋盘
public static void main(String[] args) {
//测试
//起始坐标，只要起始坐标不变结果就不变
int row = 2;
int col = 2;
long start = System.currentTimeMillis();
traversalChessBoard(chessBoard,row-1,col-1,1);
long end = System.currentTimeMillis();
System.out.println("遍历耗时="+(end-start));
//输出当前这个棋盘的情况
//增强for,解释，把二维数组当成几个一维数组，即每行是一个一维数组，然后遍历一维数组
for(int[] rows : chessBoard){
for (int step : rows){
System.out.print(step+"\t");
}
System.out.println();
}
//普通for
// for (int i = 0; i < chessBoard.length; i++) {
// for (int j=0;j
// System.out.print(chessBoard[i][j]+"\t");
// }
// System.out.println();
// }
}
//写一个方法，对ps的各个位置，可以走的下一个位置的次数进行排序, 把可能走的下一个位置从小到大排序 908
public static void sort(ArrayList ps) {
ps.sort(new Comparator() {//这块别纠结了
@Override
public int compare(Point o1, Point o2) {
return next(o1).size()-next(o2).size();
}
});
}
//编写最核心的算法，遍历棋盘，如果成功遍历，就把finished设置位true，并且 907
//将马儿走的每一步step，记录到chessBoard二维数组中
public static void traversalChessBoard(int[][] chessBoard,int row,int col,int step){
//先把step记录到chessBoard中
chessBoard[row][col] = step;
//把这个位置设置为已经访问，就是走过了，可以走通，但是走过了，就不用再走了
visited[row*X+col] = true;
//获取当前这个位置可以走的下一个位置有哪些
ArrayList ps = next(new Point(col, row));//注意col是纵坐标即Y,row是横坐标即X
sort(ps);//排序后 908
//遍历
while(!ps.isEmpty()){//如果集合不为空，就进入循环，然后取出集合里的点
//解释：取出这个ps集合中的第一个位置(点)(因为remove(0) 0就代表当前集合的第一个元素的索引)
// ，这里我们取出的点是用的remove删除(解释为什么边取边删除，因为边取边删我们的ps集合将
// 会越来越小，意思是删掉原来的第一个元素 即索引0对应的元素，后面的第二个元素就变成了第一个元素，
// 就好像集合往前走了一样的感觉，这样边取边删就可以取出集合中的所有元素，还因为我们不知道集合中
// 到底有多少个元素，(因为下一步是否合法不确定)就不能用具体的0，1，2……等为索引取出相关数据，
// 而边取边删就可以，因为删完就结束了)，
// 因为进入循环是用的判断集合是否空作为条件，当我们将当前点的下一步位置的集合边取边删完后
// ，这个点的集合就不用在进入循环判断了
Point p = ps.remove(0);//从集合中取出一个点，边取边删的返回值就是这个被删除的点的数据
//判断该位置是否走过，如果没有走过，我们就让该点递归遍历
//解释p.y对应row横坐标，p.x对应col纵坐标
if(!visited[p.y*X+p.x]){//如果不等于true，即false，false就是没有走过
//该点没走过,就将该点作为当前点(因为我们这个点是从集合中取出来的，就是“下一位合法点”，
// 要进入递归，就将该点作为当前点) 进入递归
traversalChessBoard(chessBoard,p.y,p.x,step+1);
}
}
//当推出while循环后，看看是否遍历成功，如果没有成功，就重置相应的值，然后进行回溯
//解释!finished及为true,因为我们的finished初始值为false，而finished表示游戏结束，我们将
//!finished及为true就表示游戏还没结束
if(step<X*Y && !finished){//表示游戏没结束可进入循环
//重置
//既然走不通将回溯到该点(注意该点并不一定值起始点，也有可能是递归中的某个分支点)
chessBoard[row][col] = 0;
visited[row*X+col] = false;//置为false就当该点没走过
}else{
finished = true;//成功结束游戏
}
}
//编写一个方法，可以获取当前位置，可以返回下一步所有合法点位置(Point表示x,y) 906
public static ArrayList next(Point curPoint){//curPoint当前位置
//创建一个ArrayList，用来盛放当前坐标curPoint，周围下一步符合合法规则的点(最多8个点)
ArrayList ps = new ArrayList<>();
//创建一个Point对象(点/位置),如果该点坐标合法符合规则，放入到ps集合
Point p1 = new Point();//这个p1就是curPoint下一步的合法点
//判断在curPoint是否可以走如下位置，如果可以走即合法，就将该点(Point)放入到ps
//判断是否可以走5位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走6位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走7位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走0位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走1位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走2位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走3位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
//判断是否可以走4位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1)); //这里一定要new Point
}
return ps;
}
}