人工智能九宫格重移搜索的实验报告Word下载.docx
《人工智能九宫格重移搜索的实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《人工智能九宫格重移搜索的实验报告Word下载.docx（101页珍藏版）》请在冰点文库上搜索。
283
164
75
1
14
765
2
3
4
64
175
23
184
16
754
5
6
7
8
9
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中，
3.4若空格在第1、2列,向右移动得到新状态
3.5若空格在第1行,向下移动得到新状态
3.5．算法流程图
输入初始状态SS和目标状态NN
开始
open空?
Y
N
n=0,初始节点送入open队列
搜索失败，
算法结束，
从open中取出节点到closed中并编号加1
扩展编号为n的节点，加入open中
closed中是否有目标节点
算法结束
是否还有后续节点
4.启发式A*算法
队列：
构造哈希表以方便查找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.状态空间表示
4.3.搜索树
因为2节点离目标节点更近，调换到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.算法流程图
S0加入open表，构造G
open空？
失败
结束
open取首节点放入closed,n号
扩展n节点，
加入G
将不是n为父的子节点记做集合M
M中未在G出现过的设置父节点n,放入open
M中已G出现过的open
表中更新
M中已G出现过且扩展的，closed表中更新g（x）
OPEN表中的节点按估价函数进行排序
5.启发式A算法
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.状态空间表示
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。
生成一组子节点。
5.6对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；
5.7对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；
5.8对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；
5.9按f值从大至小的顺序，对Open表中的结点重新排序；
5.10返回步骤2。
5.5算法流程图
6.随机数生成算法
6.1.算法介绍
在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数。
由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。
因此，我们就整数随机数和实数随机数，以及它们的数据值的范围性和是否可重复性，分别对其算法加以分析和设计。
1、MicrosoftVC++产生随机数的原理：
Srand（）和Rand（）函数。
它本质上是利用线性同余法，y=ax+b（modm）。
其中a，b，m都是常数。
因此rand的产生决定于x，x被称为Seed。
Seed需要程序中设定，一般情况下取系统时间作为种子。
它产生的随机数之间的相关性很小，取值范围是0—32767（int），即双字节（16位数），若用unsignedint双字节是65535，四字节是4294967295，一般可以满足要求。
根据整数随机数范围性和是否可重复性，可分为：
（1）某范围内可重复。
（2）某范围内不可重复。
（3）枚举可重复。
（4）枚举不可重复。
所谓范围，是指在两个数n1和n2之间。
例如，在100和200之间这个范围，那么，只要产生的整数随机数n满足100≤n≤200，都符合要求。
所谓枚举，是指有限的、已知的、若干个不连续的整数。
例如，34、20、123、5、800这5个整数就是一种枚举数，也就是单独可以一个个确定下来。
某范围内可重复
在VisualBasic语言中，有一个随机数函数Rnd。
语法：
Rnd[（number）]。
参数number可选，number的值决定了Rnd生成随机数的方式。
Rnd函数返回小于1但大于或等于0的值。
Number类型
Rnd结果
小于零
每次都相同的数字，并将number用作种子。
大于零
序列中的下一个随机数。
等于零
最近生成的数字。
未提供
在调用Rnd之前，先使用无参数的Randomize语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子。
若要生成某给定范围内的随机整数，可使用以下公式：
Int（（upperbound-lowerbound+1）*Rnd+lowerbound）
这里，upperbound是此范围的上限，而lowerbound是范围的下限
6.2.程序流程图：
给定范围
上限：
lowerbound
下限：
upperbound
生成随机数：
Random—Int（（upperbound—lowerbound+1）%Rnd+lowerbound
7.DFS
黄鑫负责部分（请注意与上面的格式搭配一下）
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.代码
共包括3个工程文件：
CommonRANDYYSEN
工程文件名
类名
功能
代码行数
Common
Ase.cs
实现A算法
约350行
Astr.cs
A算法的解空间
27
Bfs.cs
实现广度优先算法
220
Bfstr.cs
广度优先算法的解空间
15
Bse.cs
实现A*算法
35
common.cs
公用方法
72
Dfs.cs
实现深度优先算法
250
Dfstr.cs
深度优先算法解空间
RAND
RandNum.cs
生成随机地图
55
YYYSEN
Form1.cs
Windows功能实现
290
Form1.Designer.cs
Windows界面设计
660
Program.cs
Windows界面入口
21
1、classAse实现启发式A算法
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Text;
usingSystem.Collections;
//约350行
namespaceCommon
{
publicclassAse
{
privateint[]SS=newint[9];
privateint[]NN=newint[9];
privatestringS;
privatestringN;
publicboolBOOL;
//是否有解；
Astr>
open=newList<
（）;
//未搜索；
//已搜索；
publicArrayListmap=newArrayList（）;
publicAse（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）;
}
publicvoidsearch（）
//呵呵，调用其他的搜索，不解释
Bfsansbfs=newBfs（this.SS,this.NN）;
ansbfs.search（）;
map=ansbfs.map;
return;
if（S!
=N）
Astrnode=newAstr（）;
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（）;
//构造最佳答案；
inti=0;
Astrp=closed[closed.Count-1];
closed.Remove（p）;
map.Add（p.now）;
while（p.now!
=S）
for（i=0;
i<
closed.Count;
i++）
if（closed[i].now==p.qian）
map.Add（closed[i].now）;
p=closed[i];
break;
//交换
intj=0;
for（i=0,j=map.Count-1;
j;
i++,j--）
stringsss=map[i]asstring;
map[i]=map[j];
map[j]=sss;
//交换值
privatevoidswap（int[]a,intx,inty）
intt;
t=a[x];
a[x]=a[y];
a[y]=t;
privateintfwn（strings1,strings2）
inti;
intsum=0;
s1.Length;
if（s1[i]!
=s2[i]）
sum++;
returnsum;
//
privatevoidfun（）
Astrnode_1=newAstr（）;
Astrnode_2=newAstr（）;
//Astrnode_3=newAstr（）;
int[]a=newint[9];
int[]b=newint[9];
strings;
intcount=0;
while（true&
&
open.Count!
=0）
if（count++>
10000）
//找最小元素
//list.Sort（（x,y）=>
y.Age-x.Age）;
排序
//去open中的fn最小值
node_1=open[i];
open.Count;
if（node_1.fn>
=open[i].fn）
}
open.Remove（node_1）;
closed.Add（node_1）;
if（node_1.now==N）
return;
a=common.changeint（node_1.now）;
a.Length;
if（a[i]==9）
intindex=i;
if（i%3!
=0）
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;
intj=0;
for（j=0;
j<
j++）
if（open[j].now==node_2.now）
if（open[j].gn>
node_2.gn）
open.RemoveAt（j）;
open.Add（node_2）;
table[node_2.now]=node_2.gn;
intk;
for（k=0;
k<
k++）
if（closed[k].now==node_2.now）
if（closed[k].gn>
closed.RemoveAt（k）;
closed.Add（node_2）;
if（j==open.Count）
if（k==closed.Count）
table.Add（node_2.now,
升级会员 