【Java学习笔记】75 - 算法优化入门 - 马踏棋盘问题

一、意义

1.算法是程序的灵魂,为什么有些程序可以在海量数据计算时,依然保持高速计算?

2.拿老韩实际工作经历来说,在Unix下开发服务器程序,功能是要支持上千万人同时在线,在上线前, 做内测,一切OK,可上线后,服务器就支撑不住了,公司的CTO对代码进行优化,再次上线,坚如磐石。那一瞬间,你就能感受到程序是有灵魂的,就是算法。

3.编程中算法很多,比如八大排序算法(冒泡、选择、插入、快排、归并、希尔、基数、堆排序、查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法

4.老韩以骑士周游问题为例,让小伙伴体验用算法去优化程序的意义,让大家直观的感受到算法的威力

二、经典算法问题 - 骑士周游问题

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

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

3.游戏演示:https://u.ali213.net/games/horsesun/index.html?game_ code= 403

4.会使用到图的遍历算法(DFS) +贪心算法优化

算法介绍

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

2.如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,如图:走到了第53个,坐标(1,0),发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的..... ,思路分析+代码实现

3.先用基本方式来解决,然后使用贪心算法(greedyalgorithm) 进行优化。解决马踏棋盘问题,体会到不同的算法对程序效率的影响

4.使用前面的游戏来验证算法是否正确
 

解决步骤和思路分析

1.创建棋盘chessBoard,是二维数组,

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

3.遍历ArrayList中存放的所有位置,看看那个可以走,如果可以走通,就继续,走不通,就回溯

4.判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘设置为0

注意:马儿走的策略不同,则得到的结果也不一样,效率也不一样.

多想想 很巧妙的思路

public class HorseChessBoard {private static int X = 6; //colprivate static int Y = 6; //rowprivate 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) + "ms");for(int[] rows : chessBoard){for (int step : rows){ //step表示该位置是马儿走的第几步System.out.print(step + "\t");}System.out.println();}}//编写核心算法 遍历棋盘 如果遍历成功 就把finished设置为true;public static void traversalChessBoard(int[][] chessBoard, int row,int col,int step){//先把step 记录到chessBoardchessBoard[row][col] = step;//把这个位置设置为已访问visited[row * X + col] = true;//这个索引计算能计算行列在一维数组的对应的下标//获取当前位置可以走的下一个位置有哪些ArrayList<Point> ps = next(new Point(col, row));//col - X,row - Y//遍历while (!ps.isEmpty()){//取出一个位置(点) 取出当前这个ps的第一个点Point p = ps.remove(0);if(!visited[p.y * X + p.x]){//如果这个取出点没有走过//递归遍历traversalChessBoard(chessBoard,p.y,p.x,step + 1);}}//当退出while 看看是否遍历成功,如果没有成功,就重置相应的值,然后进行回溯if(step < X * Y && !finished){//重置chessBoard[row][col] = 0;visited[row * X + col] = false;}else{finished = true;}}public static ArrayList<Point> next(Point curPoint){//创建一个ArrayListArrayList<Point> ps = new ArrayList<>();//创建一个Point对象(点/位置),准备放入到psPoint p1 = new Point();//判断在curPoint是否可以走如下位置,如果可以走,就将该点(Point)放入到ps//判断是否可以走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) < X && (p1.y = curPoint.y - 2) >= 0){ps.add(new Point(p1));//避免一个点重复放}//判断是否可以走0位置if((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >=0){ps.add(new Point(p1));//避免一个点重复放}//判断是否可以走1位置if((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y){ps.add(new Point(p1));//避免一个点重复放}//判断是否可以走2位置if((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y){ps.add(new Point(p1));//避免一个点重复放}//判断是否可以走3位置if((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y){ps.add(new Point(p1));//避免一个点重复放}//判断是否可以走4位置if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y){ps.add(new Point(p1));//避免一个点重复放}return ps;}
}

 

对代码使用贪心算法,进行优化,提高速度

分析
1.我们现在走的下一个位置,是按照我们的顺时针来挑选位置,因此选择的这个点的下-一个可以走的位置的个数是不确定的.

2.优化思路是:我们应该选择下一个的下一个可以走的位置较少的点,开始走,这样可以减少回溯的此时

3.代码:对我们的ps集合按照可以走的下一个位置的次数进行排序,升序排序.

//写一个方法,对ps的各个位置,可以走的下一个位置的次数进行排序,把可能走的下一个位置从小到大排序public static void sort(ArrayList<Point> ps){ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {return next(o1).size() - next(o2).size();}});}

仅仅只是对该存放的可能点进行最小可能点排序 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/206214.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

常用服务注册中心与发现(Eurake、zookeeper、Nacos)笔记(一)基础概念

基础概念 注册中心 在服务治理框架中&#xff0c;通常都会构建一个注册中心&#xff0c;每个服务单元向注册中心登记自己提供的服务&#xff0c;将主机与端口号、版本号、通信协议等一些附加信息告知注册中心&#xff0c;注册中心按照服务名分类组织服务清单&#xff0c;服务…

OpenGL之Mesa3D编译for Ubuntu20.04(三十六)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…

vue3中的Fragment、Teleport、Suspense新组件

Fragment组件 在Vue2中: 组件必须有一个根标签 在Vue3中: 组件可以没有根标签, 内部会将多个标签包含在一个Fragment虚拟元素中 好处: 减少标签层级, 减小内存占用 <template><div style"font-size: 14px;"><p> 组件可以没有根标签</p&g…

大数据技术之数据安全与网络安全——CMS靶场(文章管理系统)实训

大数据技术之数据安全与网络安全——CMS靶场(文章管理系统)实训 在当今数字化时代&#xff0c;大数据技术的迅猛发展带来了前所未有的数据增长&#xff0c;同时也催生了对数据安全和网络安全的更为迫切的需求。本篇博客将聚焦于大数据技术背景下的数据安全与网络安全&#xff…

Cascader 级联选择器动态加载数据的回显

如果后端没有只返回第三级的id,而是同时把第三级的名字一起返回了&#xff0c;那么就可以通过下面的方法来实现 1.在级联选择器里面加上这句代码 placeholder"请选择" 2.注册一个字符串 pleasett:"" 3.赋值 如过后端返回的有第三级的选项名 直接进行赋…

解密Kafka主题的分区策略:提升实时数据处理的关键

目录 一、Kafka主题的分区策略概述1.1 什么是Kafka主题的分区策略&#xff1f;1.2 为什么分区策略重要&#xff1f; 二、Kafka默认分区策略2.1 Round-Robin分区策略 三、自定义分区策略3.1 编写自定义分区器3.2 最佳实践&#xff1a;如何选择分区策略 四、分区策略的性能考量4.…

【JS Promise, Promise.all 与 async/await用法详解】

目录 PromisePromise基本使用Promise可进行连续回调Promise回调可接受入参1.工作原理 async/await总结参考文档&#xff1a; 异步 let a 0setTimeout(() > {a 1}, 1000)console.log(a) // 0此时这个延迟就成为异步执行的了&#xff0c;a值还没有变1就被使用输出&#xff0…

element table滚动到底部加载数据(vue3)

效果图 使用插件el-table-infinite-scroll npm install --save el-table-infinite-scroll局部导入 <template><div class"projectTableClass"><el-table v-el-table-infinite-scroll"load"></el-table></div> </temp…

C#,《小白学程序》第二十七课:大数四则运算之“运算符重载”的算法及源程序

1 文本格式 using System; using System.Text; using System.Collections; using System.Collections.Generic; /// <summary> /// 大数的四则&#xff08;加减乘除&#xff09;运算 /// 及其运算符重载&#xff08;取余数&#xff09; /// </summary> public cl…

海外热门:香港服务器和美国服务器的成本较量

​  提到 2023 年海外热门服务器&#xff0c;在整个 IDC 站长圈中&#xff0c;要数香港服务器和美国服务器的关注度一直居高不下。其实也正常&#xff0c;毕竟这两种海外服务器相较成熟。不过&#xff0c;在实际使用中&#xff0c;两者也会被拿来对比&#xff0c;最显而易见的…

WordPress安装AWS插件实现文本转语音功能

适用于 WordPress 的 AWS 插件示例演示了内容创建者如何轻松地为所有书面内容添加文本转语音功能。随着语音搜索的不断增加&#xff0c;以音频格式提供更多网站内容变得至关重要。通过添加语音功能&#xff0c;网站访客可以通过在线音频播放器和播客应用程序等新渠道使用您的内…

Dubbo3使用Zookeeper作为注册中心的方案讨论!详解DubboAdmin与PrettyZoo来监控服务的优劣!

文章目录 一&#xff1a;Dubbo注册中心的基本使用 二&#xff1a;Zookeeper注册中心的使用 1&#xff1a;依赖引入 2&#xff1a;实际开发 三&#xff1a;Zookeeper作为注册中心的使用展示 1&#xff1a;启动注册Zookeeper服务 2&#xff1a;引入注册中心 (一)&#xf…

【开源】基于JAVA的天然气工程运维系统

项目编号&#xff1a; S 022 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S022&#xff0c;文末获取源码。} 项目编号&#xff1a;S022&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统角色分类2.2 核心功能2.2.1 流程…

ESP32-Web-Server编程- 使用SSE 实时更新设备信息

ESP32-Web-Server编程- 使用SSE 实时更新设备信息 概述 如前所述&#xff0c;传统 HTTP 通信协议基于 Request-Apply&#xff08;请求-响应&#xff09;机制&#xff0c;浏览器&#xff08;客户端&#xff09;只能单向地向服务器发起请求&#xff0c;服务器无法主动向浏览器推…

2023亚太杯数学建模A题思路分析 - 采果机器人的图像识别技术

1 赛题 问题A 采果机器人的图像识别技术 中国是世界上最大的苹果生产国&#xff0c;年产量约为3500万吨。与此同时&#xff0c;中国也是世 界上最大的苹果出口国&#xff0c;全球每两个苹果中就有一个&#xff0c;全球超过六分之一的苹果出口 自中国。中国提出了一带一路倡议…

智安网络|发现未知风险,探索渗透测试的奥秘与技巧

在当今信息时代&#xff0c;网络安全已成为组织和个人面临的重大挑战。为了保护网络系统的安全&#xff0c;渗透测试成为一种重要的手段。 一、渗透测试的基本原理 渗透测试是通过模拟黑客攻击的方式&#xff0c;对目标系统进行安全评估。其基本原理是模拟真实攻击者的思维和行…

稳定的音频来了 — 使用人工智能创作音乐(for free)

今天&#xff0c;以稳定扩散&#xff08;Stable Diffusion&#xff09;和StableLM等开源AI工具和模型而闻名的Stability AI公司推出了其首个音乐和声音生成AI产品——StableAudio。音乐产业以其难以打入而闻名。即使您拥有才华和动力&#xff0c;您仍然需要创作和制作音乐所需的…

ESP32单片机案例

工具&#xff1a;VScode PlatformIO IDE 注&#xff1a;B站视频学习笔记。 1、继电器 1&#xff09;硬件电路 2&#xff09;程序 #include <Arduino.h> #define RELAY_PIN 15//初始化定时器 hw_timer_t *timer NULL;void timer_interrupt(){digitalWrite(RELAY_PIN…

C++设计模式——原型 (克隆)模式

一、什么是原型模式 Prototype模式说简单点&#xff0c;就是提供了一个clone, 通过已存在对象进行新对象创建。clone&#xff08;&#xff09;实现和具体的实现语言相关&#xff0c;在C中我们通过拷贝构造函数实现。 那为啥要写clone的接口来实现这个目的呢&#xff1f;直接使…

如何在本地安装部署WinSCP,并实现公网远程本地服务器

可视化文件编辑与SSH传输神器WinSCP如何公网远程本地服务器 文章目录 可视化文件编辑与SSH传输神器WinSCP如何公网远程本地服务器1. 简介2. 软件下载安装&#xff1a;3. SSH链接服务器4. WinSCP使用公网TCP地址链接本地服务器5. WinSCP使用固定公网TCP地址访问服务器 1. 简介 …