【算法篇】（java语言实现）

【前言】本文部分内容引用于b站尚硅谷老师的资料，如有侵权，请及时联系作者！

hello大家好！ 我依然是你们熟悉的槿凉。那么最近呢由于躺平了几天，也没有来得及更新博客，没有办法啦！学校封的严严实实，闷在学校里真的是十分难受。好叭，难受归难受，也期待着早点期末考试，早点回家，早点出狱（哈哈哈哈哈哈）！ 好了，废话不多说，那么该卷还是得卷，今天呢我们就来说说这个马踏棋盘问题！

定义：这里也不能说是定义叭，哈哈，其实这个算法就是一个游戏，即象棋里面的马走“日”，按照这个规则来限定我们设计的棋盘，这里我们规定我们设计的棋盘里马不能走已经走过的格子，同时要求马要走完所有的格子。来我们看一下我们要设计的棋盘：

 这里我们设计一个8*8的棋盘，马儿所在的位置是第五行 第五列，马儿现在有0 1 2 3 4 5 6 7 个位置可以选择走，那么我们怎么设计这个算法来解决让马儿一次性走完所有的格子呢？

来看一段代码，我们先设计棋盘，棋盘是一个二维数组：

	private static int x;//棋盘的列数
	private static int y;//棋盘的行数
    x=8;
    y=8;

然后我们来判断马儿可以走哪些位置，走的位置是有条件的，不能越界：

 public static ArrayList next(Point curPoint){
		 ArrayList ps = new ArrayList();
		 Point p1 = new Point();
		 //表示马儿可以走5这个位置
		 if((p1.x=curPoint.x-2)>=0 && (p1.y=curPoint.y-1)>=0) {
			 ps.add(new Point(p1));
		 }
		 //表示马儿可以走6这个位置
		 if((p1.x=curPoint.x-1)>=0 && (p1.y=curPoint.y-2)>=0) {
			 ps.add(new Point(p1));
		 } 
		 //表示马儿可以走7这个位置
		 if((p1.x=curPoint.x+1)=0) {
			 ps.add(new Point(p1));
		 }
		//表示马儿可以走0这个位置
		 if((p1.x=curPoint.x+2)=0) {
			 ps.add(new Point(p1));
		 } 
		//表示马儿可以走1这个位置
		 if((p1.x=curPoint.x+2)=0 && (p1.y=curPoint.y+2)=0 && (p1.y=curPoint.y+1) 
 
 
我们定义一个ArrayList,用来存放我们走过的格子的集合，通过if语句来判断条件，注意这里的x我们表示的是棋盘的列数，y表示的棋盘的行数，p1.curPoint.x-1表示棋盘的列数减一，减一之后不能小于零，否则会越界，同理，对于y(行数）,也要保证不能越界，越界就会导致栈溢出。
 
 
        接下来我们判断马儿是否完成了任务，使用step和应该走的步数相比较
         如果没有达到数量，则表示没有完成任务，将整个棋盘置0   来看具体的代码实现：
 
	 if(step 
好了，那么到这里我们来定义一个函数，用来说明马儿的起始位置，以及下一个可以访问的位置，同时对集合进行遍历，最后看看能不能得到我们想要的结果：
 
public static void travelChessboard(int[][] chessboard,int row,int column,int step) {
		 chessboard[row][column] = step;
		 //row=4X=8,column= 4=4*8+4=36
		 visited[row*x+column] = true;//标记改为自已经被访问
		 //获取下一个可以访问的位置
		ArrayList ps = next(new Point(column,row));
		//对ps进行排序，排序的规则就是对ps的所有Point对象的下一步的位置的数目，进行非递减排序
		sort(ps);
		//遍历ps
		while(!ps.isEmpty()) {
			Point p = ps.remove(0);//取出下一个可以走的位置
			if(!visited[p.y*x+p.x]){//说明还没有被访问过
			travelChessboard(chessboard,p.y,p.x,step+1);
			}
		}
 
是不是听得有点懵呢?没有关系，多看几遍代码里面的注释就OK啦！（这里我个人感觉马踏棋盘问题还是有点难的 大家不理解的可以多看几遍哈！）
 
 
 这里我们运行第一次的输出结果：
 
 
 可以发现我们虽然运行了，但是耗时是非常的长，我这里也是等了估计40秒左右才看到运行结果，那么如何对这个算法进行优化呢？
 
这里我们使用贪心算法来优化这个问题：（贪心算法这里不做详细描述，在后面的博客里会陆续给出，可以看懂代码就可以啦）
 
//根据当前这一步的所有下一步的选择位置，进行非递减排序 减少回溯
public static void sort(ArrayList ps) {
	ps.sort(new Comparator() {
		public int compare(Point o1,Point o2) {
			int count1 = next(o1).size();//获取o1的下一步所有位置的个数
			int count2 = next(o2).size();//获取o2的下一步所有位置的个数
			if(count1 
来看一下最后的运行结果：
 
 
                 这里我们看到只用了短短的32毫秒，可以看出贪心算法是非常的实用。
 
 好了，那么今天的算法就讲到这里啦，小伙伴们有什么问题可以发在评论区，大家有什么好的想法可以一起分享讨论，之后我会持续更新算法方面的知识，想和大家一起学习，一起进步，从基础知识做起，坚持下去，一定可以的！！！感谢大家三连关注啦！！！