文章目录
第1关:A*搜索求解8数码问题
任务描述
相关知识
评估函数
贪婪最佳优先搜索
A*搜索:缩小总评估代价
求解思路
编程要求
测试说明
解题思路
算法伪代码
实验结果分析
总结
实验源码
第1关:A*搜索求解8数码问题
任务描述
本关任务:八数码问题是在一个3×3的棋盘上有1−8位数字随机分布,以及一个空格,与空格相连的棋子可以滑动到空格中,问题的解是通过空格滑动,使得棋盘转化为目标状态,如下图所示。
为了简化问题的输入,首先将空格用数字0表示,然后将3×3的棋盘用9位长的字符串表示,则上图的初始状态为724506831,目标状态为012345678,本关卡所有目标状态均为012345678,也保证初始状态到目标状态有解。
对于上图的初始状态,将数字2移动到空格,称之为u操作(空格上移),将数字3移动到空格,称之为d操作(空格下移),将数字5移动到空格,称之为l操作(空格左移),将数字6移动到空格,称之为r操作(空格右移),则一个合法移动路径为lurdrdllurrdllurrulldrrull。
724 724 024 204 254 ... 012
506 056 756 756 706 ... 345
|