位置: 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织梦获取栏目(分类)的文章数量的方法(织梦使用教程)

  • 税捷财税官网
  • 促销费用计入销售费用哪个科目
  • 缴纳以前年度所得税在今年汇算清缴怎么填报
  • 劳务费个人所得税怎样计算
  • 营业外收入汇算清缴需要调整吗
  • 收外汇必须报关吗
  • 报销用专票
  • 无票收入应该怎么做
  • 员工预支薪金怎么记账
  • 财务单子包括哪些
  • 销售材料应确认的损益是什么意思
  • 网络公司可以开展什么业务
  • 出口退税新旧申报
  • 旧公司库存如何管理
  • 担保费和评审费计入什么科目
  • 限制性股票科目
  • 一般存款账户可以转账给个人吗
  • 委托代理合同后果的承担
  • 电费发票可以抵扣进项吗
  • 固定资产进项税额转出怎么做账务处理
  • 租赁类专票不含增值税吗
  • 百旺金赋服务费280元发票在哪里开
  • 公司减少注册资本的程序
  • 土地补偿款属于专项资金吗
  • 外来原始凭证是指企业财会部门从外部购入的原始凭证
  • 租赁发票多少点
  • 0元收购股份
  • 出租车收税吗
  • 现金流量表怎么编制
  • 社保参保退费需要多久
  • uniapp微信小程序支付流程
  • 怎么提升电脑速度
  • 电商新公司值得去吗
  • drvmgr.exe
  • 鹤望兰的养殖方法和注意事项浇水
  • 源码阅读技巧
  • uniapp相关面试题
  • controller 层
  • php和mysql的联合使用
  • 杭州西湖古风
  • python基本功
  • HTTP 协议
  • swatch of
  • Uncaught SyntaxError: Unexpected token '<' (at 报错
  • 装修费入账科目
  • 连带责任担保会被拘留吗
  • 小规模纳税人货款怎么算
  • 长期借款利息是流动负债吗
  • 借款单属于外来单据吗
  • 国税实名认证手机号如何解绑
  • 什么企业进项多
  • 一次性发放年终奖金怎么扣除个人所得税144000有何意义
  • 对于投资者而言购买债券型理财产品面临的最大风险来自
  • 实收资本库存现金凭证怎么开
  • 雇佣临时工需要交个人所得税吗
  • 经营性罚款在会计中怎么处理
  • 以前年度漏扣个税怎么处理
  • 增值税出口退税款缴纳企业所得税吗
  • 收到损坏物品赔偿金如何入账
  • 投资收益的账务怎么处理
  • 安全生产费计提和使用的账务怎么处理
  • 对公账户 发票
  • mysql一闪而退
  • ktpcntr.exe
  • linux中sed详细用法
  • linux进程运行的两种方式
  • ubuntu14.04.6安装教程
  • Jquery ajax 同步阻塞引起的UI线程阻塞问题
  • jquery图片轮播无缝连接
  • 浅谈一下新冠的好处
  • unity接入安卓sdk
  • [置顶]bilinovel
  • 安装下载应用
  • jquery mobile demo
  • 拟录用人员公示后还会递补吗
  • 国家税务四川税务总局APP
  • 三方协议暂不支持缴款
  • 深圳国税地税怎么申报
  • 承租房变更承租人申请怎么写
  • 预缴的税额可以用留底抵扣吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设