人工智能九宫格重移——搜索成员：赵春杰 2009210665羊森 2009210653黄鑫 2009210周成兵 2009210664王素娟 20092106441.问题描述：八数码问题也称为九宫问题。
在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。
棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。
棋子移动后，状态就会发生改变。
解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。
所以147258369是无解的情况。
由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。
3.BFS算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找3.1．BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。
对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。
3.2．状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。
3.3．搜索树3.4．算法步骤搜索：（1）把初始节点S0放入OPEN表。
（2）如果OPEN表为空，则问题无解，退出。
（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。
（4）考察节点n是否为目标节点。
若是，则求得了问题的解，退出。
（5）若节点n不可扩展，则转第2步。
（6）扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。
扩展fun()：（1）取open中第一个节点a加入到closed中（2）找到a[9]中值为9（空格）的位置i；（3）当open中元素个数不为0时，循环执行（3）到（）3.1从open中取出一个元素（状态），并加入到closed中，对这个状态扩展；3.2若空格在第2、3列,向左移动得到新状态；新状态不是目标状态，就加入open中；新状态是目标状态，就加入closed中，编号加1，结束算法；3.3若空格在第2、3行,向上移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；3.4若空格在第1、2列,向右移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；3.5若空格在第1行,向下移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；3.5．算法流程图4.启发式A*算法队列：Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找sort排序4.1．算法介绍算法A不能保证当图中存在从起始节点到目标节点的最短路径时，一定能找到它，而A*中评估函数f*(n)=g*(n)+f*(n)保证路径存在时，一定能找到。
算法A中，g(n)和h(n)是g*(n)和f*(n)的近似估价。
如果对于所有节点h(n)<g*(n),则它就称为A*算法：4.2.状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。
4.3.搜索树4.4.算法步骤算法描述：3.1把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；3.2检查OPEN表是否为空，若为空则问题无解，退出；3.3把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；3.4考察节点n是否为目标节点。
若是，则求得了问题的解，退出；3.5扩展节点n，生成一组子节点。
把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；3.6针对M中子节点的不同情况，分别进行如下处理：3.6.1对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）3.6.2对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）3.6.3对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中, 对节点n子节点的子节点更新g(x) ）3.7对OPEN表中的节点按估价函数进行排序；3.8转第2步。
4.5.算法流程图5.启发式A算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找sort排序5.1算法介绍启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。
其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。
评价函数的形式如下：f（n）＝g（n）＋h（n） ; 其中n是被评价的节点。
说明：g*(n)：表示从初始节点s到节点n的最短路径的耗散值；h*(n)：表示从节点n到目标节点g的最短路径的耗散值；f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。
而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。
是一种预测。
A算法就是利用这种预测，来达到有效搜索的目的的。
它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。
5.2.状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。
5.3.搜索树5.4.算法步骤5.1 建立一个只含初始节点So的搜索图G，把So放入Open表，并计算f（So）的值；5.2 如果Open表是空的，则失败，否则，继续下一步；5.3从Open表中取出f值为最小的结点，置于Close表，给这个结点编号为n；5.4如果n是目标结点，则得解，算法成功退出。
此解可从目标结点开始到初始节点的返回指针中得到。
否则，继续下一步；5.5扩展结点n。
生成一组子节点。
把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；5.6对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；5.7对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）5.8对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中, 对节点n子节点的子节点更新g(x) ）5.9按f值从大至小的顺序，对Open表中的结点重新排序；5.10 返回步骤2。
5.5算法流程图6.随机数生成算法6.1.算法介绍在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数。
由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。
因此，我们就整数随机数和实数随机数，以及它们的数据值的范围性和是否可重复性，分别对其算法加以分析和设计。
1、Microsoft VC++产生随机数的原理：Srand ( )和Rand( )函数。
它本质上是利用线性同余法，y=ax+b(mod m)。
其中a，b，m都是常数。
因此rand的产生决定于x，x被称为Seed。
Seed需要程序中设定，一般情况下取系统时间作为种子。
它产生的随机数之间的相关性很小，取值范围是0—32767（int），即双字节（16位数），若用unsigned int 双字节是65535，四字节是4294967295，一般可以满足要求。
根据整数随机数范围性和是否可重复性，可分为：(1)某范围内可重复。
(2)某范围内不可重复。
(3)枚举可重复。
(4)枚举不可重复。
所谓范围，是指在两个数n1和n2之间。
例如，在100和200之间这个范围，那么，只要产生的整数随机数n满足100≤n≤200，都符合要求。
所谓枚举，是指有限的、已知的、若干个不连续的整数。
例如，34、20、123、5、800这5个整数就是一种枚举数，也就是单独可以一个个确定下来。
某范围内可重复在Visual Basic 语言中，有一个随机数函数Rnd。
语法：Rnd[(number)]。
参数number 可选，number 的值决定了 Rnd 生成随机数的方式。