当前位置: 首页 > news >正文

36.骑士周游算法及其基于贪心算法的优化

概述

骑士周游算法,叫做“马踏棋盘算法”或许更加直观。在国际象棋8x8的棋盘中,马也是走“日字”进行移动,相应的产生了一个问题:“如果要求马 在每个方格只能进入一次,走遍全部的64个方格需要如何行进?”这就是著名的 骑士周游算法的由来。
在这里插入图片描述

思路

相信大家看到这个问题首先想到就是回溯
马踏棋盘问题(骑士周游问题) 实际上是图的深度优先搜索(DFS)的应用。
如果使用回溯(就是深度优先搜索) 来解决,假如马儿踏了53个点,走到了第53个,坐标(1,0),发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就
在棋盘上不停的回溯

基于回溯的解决方案

  1. 创建棋盘chessBoard,是一个二维数组;
  2. 将当前位置设置为已经访问,然后根据当前位置,计算马还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走一步,就使用step+1;
  3. 遍历arrayList中存放的所有位置,看看哪个可以走通;
  4. 判断马儿是否完成了任务,使用step和应该走的步数(即棋盘格子数-1)比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0;
    注:马 不同的走法(策略),会得到不同的结果,效率也会有影响(优化)。

代码实现

public class HorseChessBoard {private static int X;//棋盘的列数private static int Y;//棋盘的行数//创建一个数组, 标记棋盘的各个位置是否被访问过private static boolean visited[];//试用一个属性,标记是否棋盘的所有位置都被访问过了private static boolean finished;//如果为true,表示成功public static void main(String[] args) {System.out.println("开始执行骑士周游算法~");//测试X = 8;Y = 8;int row = 1;//马儿初始位置的行,从1开始编号int column = 1;//马儿初始位置的列,从1开始编号//创建棋盘int[][] chessboard = new int[X][Y];visited = new boolean[X*Y];//初始值都是false//测试一下耗时long start = System.currentTimeMillis();traversalCheessBoard(chessboard,row-1,column-1,1);long end = System.currentTimeMillis();System.out.println("共耗时"+(end - start)+"ms");//输出棋盘的最终状况for (int[] rows : chessboard) {for (int step : rows) {System.out.print(step+"\t");}System.out.println();}System.out.println("骑士周游算法结束");}/*** 骑士周游问题算法* @param chessBoard 棋盘* @param row 马儿当前位置的行 从0开始* @param column 马儿当前位置的列 从0开始* @param step 是第几步,初始位置是第1步*/public static void traversalCheessBoard(int[][] chessBoard,int row,int column,int step){chessBoard[row][column] = step;//row = 4; X=8; column=4; 4*8+4=36;visited[row*X+column] = true;//标记该位置已经访问//获取当前位置可以走的下一个位置的集合ArrayList<Point> ps = next(new Point(column, row));//遍历pswhile (!ps.isEmpty()){Point p = ps.remove(0);//取出下一个可以走的位置//判断该点是否已经访问过if(!visited[p.y*X+p.x]){//说明还没访问过traversalCheessBoard(chessBoard,p.y,p.x,step+1);}}//判断马儿是否完成了任务,使用step和应该走的步数(即棋盘格子数-1)比较,//如果没有达到数量,则表示没有完成任务,将整个棋盘置0;//说明: step<X*Y成立的情况有两种//1.棋盘到目前位置,仍然没有走完//2.棋盘处于回溯过程if (step<X*Y&&!finished){chessBoard[row][column]=0;visited[row * X + column] = false;}else {finished = true;}}/*** 根据当前位置(Point) ,计算马儿还能走哪些位置(Point),并放入到一个集合中(ArrayList),最多有八个位置* @param curPoint* @return*/public static ArrayList<Point> next(Point curPoint){//创建一个ArrayListArrayList<Point> ps = new ArrayList<>();//创建一个PointPoint p1 = new Point();//判断马儿下一步是否可以走,若可以,将这个位置放入集合//判断马儿是否可以走  位置5if ((p1.x=curPoint.x-2)>=0 && (p1.y = curPoint.y-1)>=0){ps.add(new Point(p1));}//判断马儿是否可以走  位置6if ((p1.x=curPoint.x-1)>=0 && (p1.y = curPoint.y-2)>=0){ps.add(new Point(p1));}//判断马儿是否可以走  位置7if ((p1.x=curPoint.x+1) < X && (p1.y = curPoint.y-2)>=0){ps.add(new Point(p1));}//判断马儿是否可以走  位置0if ((p1.x=curPoint.x+2) < X && (p1.y = curPoint.y-1)>=0){ps.add(new Point(p1));}//判断马儿是否可以走  位置1if ((p1.x=curPoint.x+2) < X && (p1.y = curPoint.y+1)< Y){ps.add(new Point(p1));}//判断马儿是否可以走  位置2if ((p1.x=curPoint.x+1)<X && (p1.y = curPoint.y+2)<Y){ps.add(new Point(p1));}//判断马儿是否可以走  位置3if ((p1.x=curPoint.x-1)>=0 && (p1.y = curPoint.y+2)<Y){ps.add(new Point(p1));}//判断马儿是否可以走  位置4if ((p1.x=curPoint.x-2)>=0 && (p1.y = curPoint.y+1)<Y){ps.add(new Point(p1));}return ps;}
}

效率分析

采用回溯的方案思路上自然是可行的,那么它的效率究竟如何呢?可以说很不乐观!测算下来差不多要40秒左右,优化的空间很大。
在这里插入图片描述

回溯分析与贪心优化

我们思考可以在此思考一下上面解决方案的是否有可以优化的地方?能否用贪心算法进行优化呢?

  1. 我们获取当前位置,可以走的下一个位置的集合:
    ArrayList ps = next(new Point(column,row));
  2. 需要对ps中所有Point 下一步的所有集合数目进行非递减排序;
    a. 递减是:9,7,6,5,4…
    b. 递增排序:4,5,6,7,8…
    c. 非递减排序: 1,2,2,3,3,4,4,4,4,4,4,4,5,8,10…
    d. 非递增排序: 9,9,9,8,7,5,3…
  3. 如果下一步的选择越少,意味着回溯时的步骤越少,相应的效率也会越高,所以我们应该采用非递减排序,使得回溯的代价尽可能的低。

核心优化代码

我们不妨编写一个方法,根据当前这一步的所有下一步的选择位置,进行非递减排序,以求减少回溯的次数

public static void sort(ArrayList<Point> ps){ps.sort(new Comparator<Point>(){@Overridepublic int compare(Point o1, Point o2) {//获取到o1的下一步的所有位置个数int count1 = next(o1).size();//获取到o2的下一步的所有位置个数int count2 = next(o2).size();if (count1<count2){return -1;}else if (count1==count2){return 0;}else {return 1;}}});}

这样,在上面的回溯算法中,我们可以先对ps进行排序处理,再进行后面的测算

		//获取当前位置可以走的下一个位置的集合ArrayList<Point> ps = next(new Point(column, row));//对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置数目进行非递减排序sort(ps);//遍历pswhile (!ps.isEmpty()){Point p = ps.remove(0);//取出下一个可以走的位置//判断该点是否已经访问过if(!visited[p.y*X+p.x]){//说明还没访问过traversalCheessBoard(chessBoard,p.y,p.x,step+1);}}

效率分析

经过贪心算法的优化后,相同的配置下,测算时间直接降到了50ms,效率比之前提升600倍。还是很可观的提升的。
在这里插入图片描述

小结

本节,先是采用回溯算法对骑士周游问题进行了拆解,而后利用贪心算法对回溯算法进行了优化解决了骑士周游问题。相信借此我们对贪心算法的应用应该都有了更深层次的理解,算法千万条,应用第一条,只有在合适的场景才能发挥出其最大的作用。


关注我,共同进步,每周至少一更。——Wayne

相关文章:

36.骑士周游算法及其基于贪心算法的优化

概述 骑士周游算法&#xff0c;叫做“马踏棋盘算法”或许更加直观。在国际象棋8x8的棋盘中&#xff0c;马也是走“日字”进行移动&#xff0c;相应的产生了一个问题&#xff1a;“如果要求马 在每个方格只能进入一次&#xff0c;走遍全部的64个方格需要如何行进&#xff1f;”…...

win安装vscode

一&#xff0c;下载 链接如下&#xff08;64位的&#xff09;&#xff1a;https://az764295.vo.msecnd.net/stable/abd2f3db4bdb28f9e95536dfa84d8479f1eb312d/VSCodeSetup-x64-1.82.2.exe &#xff08;其他版本看&#xff1a;Download Visual Studio Code - Mac, Linux, Win…...

【图像分割】图像检测(分割、特征提取)、各种特征(面积等)的测量和过滤(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Linux内核存在缺陷发行陷困境

导读Linux内核已经修复了本地特权esclation缺陷&#xff0c;但是几个上游分发版本例如Red Hat&#xff0c;Canonical和Debian发行版尚未发布更新。管理员应计划减轻Linux服务器和工作站本身的漏洞&#xff0c;并监控其更新计划的发布。 内核缺陷仍存在 在Linux内核4.10.1(CVE-…...

通过java向jar写入新文件

文章目录 原始需求分析实施步骤引入依赖核心编码运行效果 原始需求 有网友提问&#xff1a; 我想在程序中动态地向同一个jar包中添加文件&#xff0c;比如&#xff0c;我的可执行jar包是test.jar,我要在它运行时生成一些xml文件并将这些文件添加到test.jar中,请问如何实现&…...

uni-app_消息推送_华为厂商_unipush离线消息推送

文章目录 一、创建项目二、生成签名证书三、开通 unipush 推送服务四、客户端集成四、制作自定义调试基座五、开发者中心后台Web页面推送&#xff08;仅支持在线推送&#xff09;六、离线消息推送1、创建华为开发者账号2、开通推送服务3、创建项目4、添加应用5、添加SHA256证书…...

单元测试框架-Pytest(简单学习)

单元测试框架-Pytest Pytest是基于Python语言的单元测试框架&#xff0c;也是一个命令行的工具&#xff0c;比 unittest 测试框架更灵活。具有以下特点&#xff1a; 入门简单&#xff0c;易上手&#xff0c;官方文档丰富而且使用广泛&#xff0c;有大量的参数例子。 unittest…...

毛玻璃态卡片悬停效果

效果展示 页面结构组成 页面的组成部分主要是卡片。其中卡片的组成部分主要是包括了图片和详情。 卡片的动效是鼠标悬停在卡片上时&#xff0c;图片会移动到左侧&#xff0c;并且图片是毛玻璃效果。所以我们在布局的时候图片会采用绝对布局。而详情则是基础布局。 CSS3 知识…...

【面试经典150 | 数组】除自身以外数组的乘积

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;记录左右乘积空间优化 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到…...

uboot启动流程-涉及s_init汇编函数

一. uboot启动涉及函数 本文简单分析uboot启动流程中&#xff0c;涉及的汇编函数&#xff1a; lowlevel_init函数调用的函数&#xff1a;s_init 函数 save_boot_params_ret函数调用的函数&#xff1a; _main 函数 本文继上一篇文章的学习&#xff0c;地址如下&#xff1a;…...

单例模式详解及5种实现方式 (设计模式 一)

基本概念 在软件开发中&#xff0c;单例模式是一种常见的设计模式&#xff0c;用于确保一个类只有一个实例&#xff0c;并提供全局访问点。单例模式在需要确保只有一个对象实例存在的场景中非常有用&#xff0c;例如数据库连接、线程池、日志记录器等。 单例模式的核心思想是通…...

面试系列 - Java常见算法(一)

目录 一、排序算法 1、冒泡排序&#xff08;Bubble Sort&#xff09;&#xff1a; 2、快速排序&#xff08;Quick Sort&#xff09;&#xff1a; 二、查找算法 1、二分查找&#xff08;Binary Search&#xff09;&#xff1a; 三、 图算法 1、深度优先搜索&#xff08;De…...

Sentinel学习(1)——CAP理论,微服务中的雪崩问题,和Hystix的解决方案 Sentinel的相关概念 + 下载运行

前言 Sentinel 是面向分布式、多语言异构化服务架构的流量治理组件&#xff0c;主要以流量为切入点&#xff0c;从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、热点流量防护等多个维度来帮助开发者保障微服务的稳定性。 本篇博客介绍CAP理论&#xff0c;微…...

C#学习 - 表达式、语句

表达式 定义 算法逻辑的最基本单元&#xff0c;表达一定的算法意图是由一个或多个操作数和零个或多个操作符组成的序列表达式功能是求值&#xff0c;得到的结果可能是一个值、对象、方法或名称空间因为操作符有优先级&#xff0c;所以表达式也有优先级 分类 一个值。表达式…...

VirtualBox 进入虚拟机后,鼠标出不来了

VirtualBox 进入虚拟机后&#xff0c;鼠标出不来了。 一般情况下&#xff0c;VirtualBox默认的鼠标切换快捷键是右边的Ctrl键。 如果按住右Ctrl键还是没有用&#xff0c;那应该是没有设置主机键。 设置方法&#xff1a; 打开VirtualBox的全局设定&#xff0c;找到热键&#xff…...

030-从零搭建微服务-消息队列(二)

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;mingyue: &#x1f389; 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...

Docker从认识到实践再到底层原理(九)|Docker Compose 容器编排

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...

操作EXCEL计算3万条数据的NDVI并填入

Python操作EXCEL&#xff0c;计算3万条数据的NDVI并填入 问题描述 现在是有构建好了的查找表&#xff0c;不过构建了3万条数据&#xff0c;在excel中手动计算每行的NDVI值太麻烦了&#xff0c;也不会操作。 就试试python吧&#xff0c;毕竟python自动处理大型EXCEL数据很方便…...

Linux服务器安装Anaconda 配置远程jupyter lab使用虚拟环境

参考的博客&#xff1a; Linux服务器安装Anaconda 并配置远程jupyter lab anaconda配置远程访问jupyter&#xff0c;并创建虚拟环境 理解和创建&#xff1a;Anaconda、Jupyterlab、虚拟环境、Kernel 下边是正文了。 https://www.anaconda.com/download是官网网址&#xff0c;可…...

R语言实现随机生存森林(3)

常见问题解答 1、计算C指数 1-Error rate&#xff0c;或者 rsf.err <- get.cindex(yvar$Survival_months,yvar$OS,predictedrf.grow$predicted) 2、模型中predicted和predicted.oob区别 predicted和predicted.oob是两个不同的属性&#xff0c;它们分别表示模型的预测结果…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...