上传者: 45928096
|
上传时间: 2022-06-04 19:52:10
|
文件大小: 13KB
|
文件类型: CPP
本资源代码可以直接运行,有详细注释。
15数码问题同八数码问题,是人工智能中一个很典型的智力问题。15数码问题是在4×4方格盘上,放有15个数码,剩下一个位置为空(方便起见,用0表示空),每一空格其上下左右的数码可移至空格。本问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。
状态转换的规则:空格四周的数移向空格,我们可以看作是空格移动,它最多可以有4个方向的移动,即上、下、左、右。问题的求解方法,就是从给定的初始状态出发,不断地将空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。
本报告利用A*算法,给出了15数码问题的C++算法实现。
A*算法是一种预测算法,主要用于寻路等,根据当前状态和目标状态之间的差异,预测到达目标需要多少开销,根据这个开销来判断下一次选择以那个状态开始。这个开销在八数码问题中可以以路程为标准。