今天在队长的带领下,学习了马踏棋盘算法。
一、马踏棋盘算法的介绍
1.马踏棋盘算法也称为骑士周游问题。
2.将马随机放在国际象棋的8 × 8棋盘Board[0~7] [0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。
二、马踏棋盘算法的基本思路
1.马踏棋盘问题(骑士周游世界问题)实际上是图的深度优先搜索(DFS)的应用。
2.如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了第53个,发现已经走到了尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停回溯…效率很低。
3.因此需要使用贪心算法(greedyalgorithm)进行优化。直接使用贪心算法,优化思路来解决马踏棋盘问题。
三、马踏棋盘算法的步骤
1.创建棋盘chessBoard,是一个二维数组。
2.将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置。
3.遍历ArrayList中存在的所有位置,看看哪个可以走通;如果走通,继续,走不通,就回溯。
4.判断马儿是否完成任务了任务step和应该走的步数比较。
注意:马儿的不同走法(策略),会得到不同的结果,效率也会有影响(优化)。
学习算法,应该有打破砂锅问到底的精神,正所谓"形而上学,学无止境"。
http://www.dxsbao.com/shijian/474025.html
点此复制本页地址
为深入培养嵌入式设计领域的高素质人才,进一步激发学生的创新思维与内在潜力,山东理工大学电气与电子工程学院于6月16日上午,在7号实验楼隆重举行“2024年山东理工大学嵌入式芯片与系统设……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为了增强同学们对中华优秀传统文化的认同与热爱之情,有力地保护和发扬文化遗产,深切感悟中华优秀传统文化的独特魅力。自动控制协会于六月五号至十号这一时间段,在线上精心组织开展了……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
一场别开生面的趣味建模知识竞赛在我校成功举办。本次竞赛旨在通过趣味性的方式,激发学生对数学建模的兴趣,提升他们的团队协作能力和创新思维。竞赛于6月2日下午在学校的四体拉开帷幕。……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为吸引更多人走进建模的魅力世界,用数学建模知识解决实际问题。一场别开生面的电工建模竞赛——电工杯校级比赛于2024年5月14号到5月16号在7号实验楼717和721顺利举行。据悉,本次比赛吸引了全……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为培养电子设计人才,提升同学们电子系统设计能力,同时选拔参加“2024年山东省大学生电子设计竞赛”的优秀队伍,5月19日上午,电气与电子工程学院电子爱好者协会于7号实验楼举行“2024年山……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为深入贯彻志愿服务精神,增强青年学子的社会责任感与奉献精神,电气与电子工程学院益启爱心社于5月17日开始“益启课堂,梦想启航”活动,并于5月23日前往周村特殊教育中心。据悉,活动过……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为深入弘扬中华茶文化,培养青年学生的音乐情操和文化素养,茗香茶艺社于五月十一日晚在三餐东思源石旁精心策划了一场别开生面的“茶韵音澜,乐茗雅集”活动。活动伊始,茗香茶艺社的工……
电气社联 山东理工大学电气与电子工程学院查看全文 >>
为了丰富同学们的课余生活,营造积极健康的校园运动氛围,同时让大家更深入了解建模的魅力,电工建模协会于2024年4月21日在第四体育场举办了“以球会友”趣味建模知识竞赛。据悉,此次竞赛……
电气社联 山东理工大学电气与电子工程学院查看全文 >>