启发式搜索1. 介绍八数码问题也称为九宫问题。在33的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2. 使用启发式搜索算法求解8数码问题。1) A ，A星算法采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。2) 宽度搜索采用f(i)为i的深度，深度搜索采用f(i)为i的深度的倒数。3. 算法流程 把起始节点S放到OPEN表中，并计算节点S的； 如果OPEN是空表，则失败退出，无解； 从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个
