当前位置: 首页 > 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;它们分别表示模型的预测结果…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...