人工智能实验报告.doc

-_人工智能人工智能九宫格重移九宫格重移搜索搜索成员：赵春杰成员：赵春杰 20092106652009210665羊森羊森 20092106532009210653黄鑫黄鑫 20092102009210周成兵周成兵 20092106642009210664王素娟王素娟 20092106442009210644-_1.1.问题描述：问题描述：八数码问题也称为九宫问题。在 3×3 的棋盘，摆有八个棋子，每个棋子上标有 1 至 8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.2.九宫重移有无答案检查（逆序数）九宫重移有无答案检查（逆序数）我们把每个 9 宫格横向展开，如第一个 123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然 123456789 的逆序数为 0；考虑横向平移，那么逆序数的增量为 2 或 0 或-2；纵向平移，逆序数的增量为 4 或 0或-4；但 147258369 的逆序数为奇数。所以 147258369 是无解的情况。由此也可以类推当将 9 宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。3.BFS3.BFS 算法算法队列： Queue open = new Queue();存放待扩展的节点List： List closed = new List();存放已被扩展过的节点ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找-_3.1BFS 算法介绍广度优先搜索算法 BFS 基本思想：从图中某顶点 v 出发，逐层对节点进行拓展，并考察是否为目标节点，在第 n 层节点没有全部扩展并考察前，不对第 n+1 层节点进行扩展。对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。3.2状态空间表示状态空间用一维数组表示，每个节点存放在 Bfstr 结构体中的字符 now 中，从第一行开始从左往右给九宫格标号 08，字符串 now 元素下标代表格子位置，而 now 数组中对应数组的值代表九宫格中存放的数码，用数值 9 代表空格。3.3搜索树2 8 3 1 6 4 7 512 8 3 1 6 4 7 52 8 3 1 4 7 6 52 8 3 1 6 4 7 52342 8 3 6 4 1 7 52 3 1 8 4 7 6 52 8 3 1 6 7 5 42 8 3 1 4 7 6 52 8 3 1 4 7 6 556789-_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）找到 a9中值为 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算法流程图-_输入初始状态 SS 和目标状态 NN开始open 空?YNn=0,初始节点送 入 open 队列搜索失败， 算法结束，从 open 中取出节 点到 closed 中并编 号加 1扩展编号为 n 的节 点，加入 open 中closed 中是否有目标节点Y算法 结束是否还有后续节点NNY-_4.4.启发式启发式 A*A*算法算法队列： Queue open = new Queue();存放待扩展的节点-_List： List closed = new List();存放已被扩展过的节点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) closed = new List();存放已被扩展过的节点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 中，从第一行开始从左往右给九宫格标号 08，字符串 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 算法流程图 -_开始输入初始状态 SS和目标状态 NNS0 加入 open 表，构造 Gopen 空？YN失败 结束open 取首节点放 入 closed,n 号扩展 n 节点， 加入 G将不是 n 为父的 子节点记做集合 M M 中未在 G 出现过的设 置父节点 n,放入 openM 中已 G 出现过的 open 表中更新M 中已 G 出现过且扩展 的，closed 表中更新 g(x)OPEN 表中的节点按估 价函数进行排序-_6.6.随机数生成算法随机数生成算法-_6.1.6.1.算法介绍算法介绍在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数。由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。因此，我们就整数随机数和实数随机数，以及它们的数据值的范围性和是否可重复性，分别对其算法加以分析和设计。1、Microsoft VC+产生随机数的原理：Srand ( )和 Rand( )函数。它本质上是利用线性同余法，y=ax+b(mod m)。其中a，b，m 都是常数。因此 rand 的产生决定于 x，x 被称为 Seed。Seed 需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是 032767（int） ，即双字节（16 位数） ，若用 unsigned int 双字节是 65535，四字节是4294967295，一般可以满足要求。根据整数随机数范围性和是否可重复性，可分为：(1)某范围内可重复。(2)某范围内不可重复。(3)枚举可重复。(4)枚举不可重复。所谓范围，是指在两个数 n1 和 n2 之间。例如，在 100 和 200 之间这个范围，那么，只要产生的整数随机数 n 满足 100n200，都符合要求。所谓枚举，是指有限的、已知的、若干个不连续的整数。例如，34、20、123、5、800 这 5 个整数就是一种枚举数，也就是单独可以一个个确定下来。某范围内可重复在 Visual Basic 语言中，有一个随机数函数 Rnd。-_语法：Rnd(number)。参数 number 可选，number 的值决定了 Rnd 生成随机数的方式。Rnd 函数返回小于 1 但大于或等于 0 的值。NumberNumber 类型类型RndRnd 结果结果小于零每次都相同的数字，并将 number 用作种子。大于零序列中的下一个随机数。等于零最近生成的数字。未提供序列中的下一个随机数。在调用 Rnd 之前，先使用无参数的 Randomize 语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子。若要生成某给定范围内的随机整数，可使用以下公式：Int(upperbound - lowerbound + 1) * Rnd + lowerbound)这里，upperbound 是此范围的上限，而 lowerbound 是范围的下限6.2.6.2.程序流程图：程序流程图：-_开始给定范围上限： lowerbound下限：upperbound生成随机数：Random Int(upperboundlowerbound+1)%Rnd+lowerbound结束-_7.DFS7.DFS 黄鑫负责部分（请注意与上面的格式搭配一下）黄鑫负责部分（请注意与上面的格式搭配一下）8.8.效果图效果图滑块问题求解系统（1）DFS 时当显示只需 2、3 步时，搜索空间爆栈，内存溢出，失败。暂时解决办法：重新生成结束状态或者初始状态（2）BFS、A、A*时显示 32 步时，搜索空间太多，内存溢出，失败。暂时解决办法：重新生成结束状态或者初始状态（3）不能同时生成结束状态图和初始状态图。暂时解决办法：分步生成结束状态或者初始状态（4）未完成工作：1、时间显示2、自动演示8.1 初始界面：-_8.3.BFS 效果图：-_8.3.启发式*效果图：-_8.4 启发式 A 效果图：-_8.5.DFS 效果图：-_9.9.代码代码共包括共包括 3 个工程文件：个工程文件：Common RAND YYSEN工程文件名工程文件名类名类名功能功能代码行数代码行数Common Ase.cs实现实现 A 算法算法约 350 行Common Astr.csA 算法的解空间算法的解空间27Common Bfs.cs实现广度优先算法实现广度优先算法220Common Bfstr.cs广度优先算法的解空间广度优先算法的解空间15Common Bse.cs实现实现 A*算法算法35Common common.cs公用方法公用方法72Common Dfs.cs实现深度优先算法实现深度优先算法250Common Dfstr.cs深度优先算法解空间深度优先算法解空间15RANDRandNum.cs生成随机地图生成随机地图55YYYSENForm1.csWindows 功能实现功能实现290YYYSENForm1.Designer.csWindows 界面设计界面设计660YYYSENProgram.csWindows 界面入口界面入口211、class Ase 实现启发式 A 算法using System;using System.Collections.Generic;using System.Text;-_using System.Collections;/约350行namespace Commonpublic class Aseprivate int SS=new int9;private int NN=new int9;private string S;private string N;public bool BOOL;/是否有解；List open=new List() ;/未搜索；List closed = new List();/已搜索；Hashtable table = new Hashtable();public ArrayList map=new ArrayList();public Ase(int SS,int NN)SS.CopyTo(this.SS ,0);NN.CopyTo(this.NN, 0);S = common.changestring(SS);N = common.changestring(NN);BOOL = common.check(this.SS, this.NN, this.SS.Length);public void search()/呵呵，调用其他的搜索，不解释Bfs ansbfs = new Bfs(this.SS, this.NN);ansbfs.search();map = ansbfs.map;return;if (S != N)Astr node = new Astr();node.now = S;node.qian = “;node.gn = 0;-_node.wn = fwn(S, N);node.fn = node.gn + node.wn;open.Add(node);table.Add(node.now, node.gn);fun();/构造最佳答案；int i = 0;Astr p=closed closed .Count -1;closed.Remove(p);map.Add(p.now);while (p.now != S)for (i = 0; i 10000)return;/找最小元素/list.Sort(x, y) => y.Age - x.Age);排序int i = 0;/去open中的fn最小值node_1 = openi;for (i = 0; i = openi.fn)node_1 = openi; -_open.Remove (node_1); closed.Add(node_1);if(node_1.now =N)return ;a = common.changeint(node_1.now); for (i = 0; i node_2.gn)open.RemoveAt(j);open.Add(node_2);tablenode_2.now = node_2.gn; break;int k;for (k = 0; k node_2.gn)closed.RemoveAt(k);closed.Add(node_2);tablenode_2.now = node_2.gn; break;if (j = open.Count)if(k = closed .Count)open.Add(node_2);table.Add(node_2.now, node_2.gn);if (i -3>= 0)a.CopyTo(b, 0);swap(b, i, i - 3);s = common.changestring(b);node_2.now =s;node_2.qian=node_1.now;node_2.gn=node_1.gn +1;node_2.wn=fwn(s,N);node_2.fn =node_2.gn+node_2.wn ;int j=0;for (j = 0; j node_2.gn)-_open.RemoveAt(j);open.Add(node_2);tablenode_2.now = node_2.gn;break;int k;for (k = 0; k node_2.gn)closed.RemoveAt(k);closed.Add(node_2);tablenode_2.now = node_2.gn;break;if (j = open.Counttable.Add(node_2.now, node_2.gn);if (i % 3 != 2)a.CopyTo(b, 0);swap(b, i, i + 1);s = common.changestring(b);node_2.now =s;node_2.qian=node_1.now;node_2.gn=node_1.gn +1;node_2.wn=fwn(s,N);node_2.fn =node_2.gn+node_2.wn ;-_int j=0;for (j = 0; j node_2.gn)open.RemoveAt(j);open.Add(node_2);tablenode_2.now = node_2.gn;break;int k;for (k = 0; k node_2.gn)closed.RemoveAt(k);closed.Add(node_2);tablenode_2.now = node_2.gn; break;if (j = open.Counttable.Add(node_2.now, node_2.gn);if (i + 3 node_2.gn)open.RemoveAt(j);open.Add(node_2);tablenode_2.now = node_2.gn;break;int k;for (k = 0; k node_2.gn)closed.RemoveAt(k);closed.Add(node_2);tablenode_2.now = node_2.gn; break;if (j = open.Counttable.Add(node_2.now, node_2.gn);-_2 class Astr 主要是启发式搜索算法 A 算法的解空间 using System; using System.Collections.Generic; using System.Text; /27 namespace Common struct Astr public string now get; set; / / 从起始点到n的路径长度/ public int gn get; set; / / 代表节点n的格局与目标节点的格局相比文职不符的数目/ public int wn get; set; / / fn=gn+wn;/ public int fn get; set; / / 前一个的状态；/ public string qian get; set; 3、BFS主要是完成广度优先搜索功能 using System; using System.Collections.Generic; using System.Text; using System.Collections; /220 namespace Common -_public class Bfsprivate int SS = new int9;private int NN = new int9;private string S;private string N;public bool BOOL;/是否有解；Hashtable table = new Hashtable();Queue open = new Queue();List closed = new List();public ArrayList map = new ArrayList();public Bfs(int SS, int NN)SS.CopyTo(this.SS, 0);NN.CopyTo(this.NN, 0);S = common.changestring(SS);N = common.changestring(NN);BOOL = common.check(this.SS, this.NN, this.SS.Length);private void swap(int a, int x, int y)int t;t = ax;ax = ay;ay = t;public void search()if (S != N)Bfstr node = new Bfstr();node.now = S;node.qian = “;node.tol = 0;open.Enqueue(node);table.Add(S, 0);fun();else-_Bfstr node = new Bfstr();node.now = S;node.qian = “;node.tol = 0;closed.Add(node);int i = 0;/在closed中去寻找答案Bfstr p = new Bfstr ();p = closedclosed.Count - 1;closed.Remove(p);map.Add(p.now);while (p.now != S)for (i = 0; i = 0)a.CopyTo(b, 0);swap(b, i, i - 3);s = common.changestring(b);if (s != N)if (!table.Contains(s)node_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;open.Enqueue(node_1);table.Add(s, node_1.tol);elsenode_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;table.Add(s, node_1.tol);closed.Add(node_1);break;if (i %3!=2)a.CopyTo(b, 0);swap(b, i, i +1);s = common.changestring(b);if (s != N)if (!table.Contains(s)node_1.now = s;node_1.qian = node_0.now;-_node_1.tol = node_0.tol + 1;open.Enqueue(node_1);table.Add(s, node_1.tol);elsenode_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;closed.Add(node_1);table.Add(s, node_1.tol);break;if (i +3 = 0; j-)if (aj > ai)sum+;if (bj > bi)ans+;if (sum % 2 = ans % 2)return true;else return false;-_public static string changestring(int a)int i;string str = “;for (i = 0; i open = new Stack();private List closed = new List();Hashtable table = new Hashtable();/构造函数public Dfs(int SS,int NN)this.SS = SS;this.NN = NN;S = common.changestring(SS);N = common.changestring(NN);map = new ArrayList();BOOL = common.check(SS, NN, SS.Length);/public void search()-_if (S != N)Dfstr node = new Dfstr();node.now = S;node.qian = “;node.tol = 0;open.Push(node);table.Add(node.now , 0);fun();elseDfstr node = new Dfstr();node.now = S;node.qian = “;node.tol = 0;closed.Add(node);int i = 0;/在closed中去寻找答案Dfstr p = new Dfstr();p = closedclosed.Count - 1;closed.Remove(p);map.Add(p.now);while (p.now != S)for (i = 0; i 90)continue;a = common.changeint(node_0.now);int i = 0;for (i = 0; i = 0)a.CopyTo(b, 0);swap(b, i, i - 3);s = common.changestring(b);if (s != N)if (!table.Contains(s)node_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;open.Push(node_1);table.Add(s, node_1.tol);elsenode_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;-_table.Add(s, node_1.tol);closed.Add(node_1);break;if (i % 3 != 2)a.CopyTo(b, 0);swap(b, i, i + 1);s = common.changestring(b);if (s != N)if (!table.Contains(s)node_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;open.Push(node_1);table.Add(s, node_1.tol);elsenode_1.now = s;node_1.qian = node_0.now;node_1.tol = node_0.tol + 1;table.Add(s, node_1.tol);closed.Add(node_1);break;if (i + 3 max)/如果参数max小雨min，交换两个的值int a = min;min = max;max = a;int deference = max - min;if (deference / 必需的设计器变量。/ private System.ComponentModel.IContainer components = null;/ / 清理所有正在使用的资源。/ / 如果应释放托管资源，为 true；否则为 false。protected override void Dispose(bool disposing)if (disposing base.Dispose(disposing);#region Windows 窗体设计器生成的代码/ / 设计器支持所需的方法 - 不要-_/ 使用代码编辑器修改此方法的内容。/ private void InitializeComponent()System.ComponentModel.ComponentResourceManager resources = new System.ComponentModel.ComponentResourceManager(typeof(Form1);this.groupBox1 = new System.Windows.Forms.GroupBox();this.a1_rad = new System.Windows.Forms.RadioButton();this.bfs_rad = new System.Windows.Forms.RadioButton();this.a_rad = new System.Windows.Forms.RadioButton();this.dfs_rad = new System.Windows.Forms.RadioButton();this.time_btn = new System.Windows.Forms.Button();this.search_btn = new System.Windows.Forms.Button();this.groupBox3 = new System.Windows.Forms.GroupBox();this.s9_btn = new System.Windows.Forms.Button();this.s8_btn = new System.Windows.Forms.Button();this.s7_btn = new System.Windows.Forms.Button();this.s6_btn = new System.Windows.Forms.Button();this.s5_btn = new System.Windows.Forms.Button();this.s4_btn = new System.Windows.Forms.Button();this.s3_btn = new System.Windows.Forms.Button();this.s2_btn = new System.Windows.Forms.Button();this.s1_btn = new System.Windows.Forms.Button();this.groupBox4 = new System.Windows.Forms.GroupBox();this.n9_btn = new System.Windows.Forms.Button();this.n8_btn = new System.Windows.Forms.Button();this.n7_btn = new System.Windows.Forms.Button();this.n6_btn = new System.Windows.Forms.Button();this.n5_btn = new System.Windows.Forms.Button();this.n4_btn = new System.Windows.Forms.Button();this.n3_btn = new System.Windows.Forms.Button();this.n2_btn = new System.Windows.Forms.Button();this.n1_btn = new System.Windows.Forms.Button();this.des_txt = new System.Windows.Forms.TextBox();this.ans_txt = new System.Windows.Forms.TextBox();this.groupBox5 = new System.Windows.Forms.GroupBox();this.groupBox6 = new System.Windows.Forms.GroupBox();this.groupBox7 = new System.Windows.Forms.GroupBox();this.check_box = new System.Windows.Forms.CheckBox();this.jie_box = new System.Windows.Forms.CheckBox();this.chu_box = new System.Windows.Forms.CheckBox();this.rand_btn = new System.Windows.Forms.Button();this.moren_btn = new System.Windows.Forms.Button();this.up_btn = new System.Windows.Forms.Button();-_this.down_btn = new System.Windows.Forms.Button();this.recovery_btn = new System.Windows.Forms.Button();this.zidong_btn = new System.Windows.Forms.Button();this.label1 = new System.Windows.Forms.Label