位置: IT常识 - 正文

day53-马踏棋盘(马踏棋盘游戏规则)

编辑:rootadmin
马踏棋盘 1.算法优化的意义 算法是程序的灵魂,为什么有些程序可以在海量数据计算时,依旧保持高速计算? 编程中算法很多,比如八大排序算法(冒泡、选择、插入、快排、归并、希尔、基数、堆排序)、查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普利姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算 ... 马踏棋盘1.算法优化的意义算法是程序的灵魂,为什么有些程序可以在海量数据计算时,依旧保持高速计算?编程中算法很多,比如八大排序算法(冒泡、选择、插入、快排、归并、希尔、基数、堆排序)、查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普利姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法下面以骑士周游问题为例,体验算法优化程序的意义,感受算法的威力2.骑士周游问题马踏棋盘算法介绍和游戏演示马踏棋盘算法也被称为骑士周游问题将马随机放在国际象棋的8*8棋盘Board[0-7][0-7]的某个方格中,马按走棋规则移动(马只能走日字)。要求每个方格只进入一次,走遍棋盘上全部64个方格会使用到图的遍历算法(DFS)+贪心算法优化

推荐整理分享day53-马踏棋盘(马踏棋盘游戏规则),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:马踏棋盘需求分析,马踏棋盘的算法复杂度是多少,马踏棋盘需求分析,马踏棋盘8x8所有结果,马踏棋盘游戏规则,马踏棋盘图论解法,马踏棋盘多少种走法,马踏棋盘游戏规则,内容如对您有帮助,希望把文章链接给更多的朋友!

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

使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,如图,走到了第53个,坐标为(1,0),发现已经走到了尽头,没办法,那就只能回退了,查看其它的路径,就在棋盘上不停地回溯……

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

3.思路分析day53-马踏棋盘(马踏棋盘游戏规则)

创建一个棋盘chessBoard,是一个二维数组将马儿当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),每一个位置的下一步最多有8个方向,每走一步,就使用step+1遍历ArrayList中存放的所有位置,看看哪个可以走,如果可以走通,就继续,走不通,就回溯判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘设置为0

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

package li;import java.awt.*;import java.util.ArrayList;/** * @author 李 * @version 1.0 * 马踏棋盘 */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 = 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 (int[] rows : chessBoard) { for (int step : rows) {//step表示 这个位置是马儿应该走的第几步 System.out.print(step + "\t"); } System.out.println(); } } //最核心的算法,遍历棋盘,如果遍历成功,就将finished的值设置为true, //并且将马儿走的每一步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;//就是将二维数组的下标对应到一位数组下标,按行的顺序存放(注意下标从0开始) //获取当前位置可以走的下一个位置有哪些 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; } } //编写方法,可以获取当前位置 可以走的下一步 的所有位置(Point表示x,y) public static ArrayList<Point> next(Point curPoint) {//curPoint表示当前点 //先创建一个ArrayList ArrayList<Point> ps = new ArrayList<>(); //创建一个Point对象,表示一个位置/点,准备放入到 ps集合中 Point p1 = new Point(); //判断在curPoint位置,是否可以走如下位置,如果可以走,就将该点(p1)放入到集合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) {//注意索引的范围是:0到X-1 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; }}

4.优化

根据上面的代码,当前点走的下一个位置,是按照我们的顺时针方向来挑选位置的,因此,所选择的点的下一个可以走的位置的个数是不确定的优化的思路是:我们应该优先选择的下一个位置,这个位置的再下一个位置应该尽可能少,这样就可以减少回溯的次数代码:对ps集合按照可以走的下一个位置的次数进行升序排序(从小到大排序)

修改:

编写方法//写一个方法,对ps集合的各个位置,可以走的下一个位置的次数进行排序,把可能走的下一个位置从小到大进行排序public static void sort(ArrayList<Point> ps){ ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return next(o1).size()-next(o2).size(); } });}在递归中调用该方法,对ps集合按照可以走的下一个位置的次数进行升序排序(从小到大排序)

优化结果:

本文链接地址:https://www.jiuchutong.com/zhishi/312992.html 转载请保留说明!

上一篇:织梦中英文站点英文分页修改的方法(织梦58符老师亲测)(织梦网站怎么改logo)

下一篇:dedecms织梦获取栏目(分类)的文章数量的方法(织梦使用教程)

  • 全民k歌的本地录音在哪(全民K歌的本地录音)

    全民k歌的本地录音在哪(全民K歌的本地录音)

  • 华为电脑怎么改账户名字(华为电脑怎么改开机密码)

    华为电脑怎么改账户名字(华为电脑怎么改开机密码)

  • 如何升级windows11系统(如何升级window7系统)

    如何升级windows11系统(如何升级window7系统)

  • 华为nova7pro显示屏上hd如何取消(华为nova7pro显示2G)

    华为nova7pro显示屏上hd如何取消(华为nova7pro显示2G)

  • 华为nova5pro支持960fps吗(华为nova5Pro支持双卡双待吗)

    华为nova5pro支持960fps吗(华为nova5Pro支持双卡双待吗)

  • 黑解的iphone可以升级ios13吗(黑解的iphone可以扩容吗)

    黑解的iphone可以升级ios13吗(黑解的iphone可以扩容吗)

  • 华为手机睡眠模式在哪(华为手机睡眠模式怎样设置)

    华为手机睡眠模式在哪(华为手机睡眠模式怎样设置)

  •   qq头像换了没反应(qq头像换了之后别人多久可以看到)

      qq头像换了没反应(qq头像换了之后别人多久可以看到)

  • 华为手机锁屏图片怎么关闭(华为手机锁屏图片怎么设置自选图片)

    华为手机锁屏图片怎么关闭(华为手机锁屏图片怎么设置自选图片)

  • qq群视频上限人数(qq群视频最多几个人参与)

    qq群视频上限人数(qq群视频最多几个人参与)

  • qq的黑名单在哪里设置(qq的黑名单在哪里找)

    qq的黑名单在哪里设置(qq的黑名单在哪里找)

  • qq空间的相片占手机内存吗(qq空间的相片占内存吗)

    qq空间的相片占手机内存吗(qq空间的相片占内存吗)

  • unix操作系统是(unix操作系统属于)

    unix操作系统是(unix操作系统属于)

  • 三星a9080是什么型号(三星a9080什么时候上市的)

    三星a9080是什么型号(三星a9080什么时候上市的)

  • 华为jatal00是什么型号(华为jat—al00)

    华为jatal00是什么型号(华为jat—al00)

  • 手机qq空间背景怎么自定义(手机QQ空间背景图尺寸)

    手机qq空间背景怎么自定义(手机QQ空间背景图尺寸)

  • 爱奇艺看电视频道在哪(爱奇艺看电视频道没反应)

    爱奇艺看电视频道在哪(爱奇艺看电视频道没反应)

  • 小米手环检测心率原理(小米手环检测心率异常)

    小米手环检测心率原理(小米手环检测心率异常)

  • 快狗打车如何申请发票(快狗打车怎么注册司机,需要什么条件)

    快狗打车如何申请发票(快狗打车怎么注册司机,需要什么条件)

  • carplay华为可以使用吗(carplay华为可以用吗)

    carplay华为可以使用吗(carplay华为可以用吗)

  • 美版ipad和国版有什么区别(美版ipad和国行区别)

    美版ipad和国版有什么区别(美版ipad和国行区别)

  • 手机微博怎么发三角号音乐(手机微博怎么发头条文章)

    手机微博怎么发三角号音乐(手机微博怎么发头条文章)

  • 苹果电影商店不可用是怎么回事(苹果电影商店为什么不可用)

    苹果电影商店不可用是怎么回事(苹果电影商店为什么不可用)

  • 共享单车停车点满了怎么办(附近哪里有共享单车停车点)

    共享单车停车点满了怎么办(附近哪里有共享单车停车点)

  • 淘宝购买东西怎么让好友代付(淘宝购买东西怎么备注)

    淘宝购买东西怎么让好友代付(淘宝购买东西怎么备注)

  • x是什么屏幕(苹果14promax是什么屏幕)

    x是什么屏幕(苹果14promax是什么屏幕)

  • 笔记本外接显示器掉帧(笔记本外接显示器没反应)

    笔记本外接显示器掉帧(笔记本外接显示器没反应)

  • python动量交易策略的四个步骤(什么叫动量交易)

    python动量交易策略的四个步骤(什么叫动量交易)

  • 税务机关代开的增值税发票要加盖发票专用章吗?
  • 农民专业合作社章程模板
  • 印花税缴纳方式一经选择1年之内不得修改
  • 济南非税是什么意思
  • 商品类别发票能抵扣吗
  • 洒水车计提折旧会计分录
  • 科技公司增值税率是多少
  • 肉联厂销售模式
  • 汇票和支票的区别是什么
  • 不动产折旧费计算公式
  • 商贸企业销售商品结转成本是手工算吗
  • 房屋租赁发票可以抵扣增值税吗
  • 海关进口增值税计算公式
  • 企业购买的预付卡赠送客户怎么入账
  • 购销合同印花税税率2023
  • 个人生产经营所得
  • 一般纳税人有哪些费用
  • 想要避免虚开发票,你就要注意以下行为
  • 资产负债表写错数字怎么改
  • 工资薪金中的误餐补助,征收个人所得税
  • 试用期内进一步使用
  • 华为手机屏幕碎了照片
  • 收到办公室桶装水开的普票怎样入账?
  • 固定资产不入账是谁的责任
  • 销售返点怎么做分录
  • 代垫费用的进项税怎么算
  • 建筑单位没有资质可以承包项目吗
  • 银行的抵债资产有几种处置办法
  • 克拉莫16首
  • 转出固定资产账务处理
  • 商铺出租各类收据怎么写
  • PHP:mcrypt_generic_init()的用法_Mcrypt函数
  • 代码怎么用?
  • 瓜纳华托大学世界排名
  • 移民美国怎样加入医疗保险
  • php分页页码动态的实现
  • 融资租入的机器设备属于什么科目
  • vue3的
  • 基于MATLAB的车牌识别
  • php实现有序数组的数据
  • PHP中spl_autoload_register()函数用法实例详解
  • php代码加密方式
  • 外贸出口退税操作流程
  • 财务章和公章下面数字一样吗
  • 发票 技术服务
  • 电子发票是正规发票吗能报销吗
  • 营业执照如何申请移出异常
  • python的用途
  • 非货币性资产交换
  • 政府补助 项目资本金
  • 财务软件怎么做红冲分录
  • 工程用车折旧年限
  • 已申报营业税未开发票
  • 国税局网上申报
  • linux系统中mysql数据库的导入和导出
  • 企业购买随时准备出售的债券
  • 购建固定资产属于投资活动吗
  • 没签劳动合同的后果
  • 没收到发票怎么入账
  • 什么是四大行业
  • 公司购买垃圾袋可以抵扣吗
  • 房地产开发企业开发成本包括哪些项目
  • mysql的函数
  • window7 aero
  • ubuntu系统防火墙状态
  • linux操作系统安装方法有哪几种
  • win7怎么多分出一个盘
  • windows屏幕上有多个窗口时
  • ubuntu20.04.1安装
  • 新款apple macbook air
  • win7开机chkdsk
  • Android游戏开发教程
  • python num怎么用
  • jquery使用教程
  • 安卓中textview
  • js中splice方法
  • 国家税务总局全国增值税发票官网
  • 国税局云南省税务局
  • 进口柴油消费税是多少
  • 应缴财政专户款属于资产类吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设