人工智能之启发式搜索算法

任务描述

本关任务：八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。

        为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678，本关卡所有目标状态均为012345678，也保证初始状态到目标状态有解。

        对于上图的初始状态，将数字2移动到空格，称之为u操作（空格上移），将数字3移动到空格，称之为d操作（空格下移），将数字5移动到空格，称之为l操作（空格左移），将数字6移动到空格，称之为r操作（空格右移），则一个合法移动路径为lurdrdllurrdllurrulldrrull。

 相关知识

        为了完成本关任务，你需要掌握：1.评估函数，2.贪婪最佳优先搜索，3.A*搜索：缩小总评估代价，4.求解思路。

评估函数

   在有信息