《2023年人工智能实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年人工智能实验报告.pdf（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能九宫格重移一一搜索成员：赵春杰羊森黄鑫 2023 2 1 0周成兵王素娟1.问题描述:八数码问题也称为九宫问题。在 3 义3的棋盘，摆有八个棋子，每个棋子上标有1 至 8的某一数字，不同棋子上标的数字不相同。棋盘上尚有一个空格，与空格相邻的棋子可以移到空格中。规定解决的问题是:给出一个初始状态和一个目的状态，找出一种从初始转变成目的状态的移动棋子步数最少的移动环节。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题事实上就是找出从初始状态到达目的状态所通过的一系列中间过渡状态。2.九宫重移有无答案检查(逆序数)我们把每个9 宫格横向展开，如第一个,
2、我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然的逆序数为0；考虑横向平移，那么逆序数的增量为 2 或 0 或-2；纵向平移，逆序数的增量为4 或 0 或-4;但的逆序数为奇数。所以是无解的情况。由此也可以类推当将9 宫格展开后，假如数据序列的逆序数为奇数,则此数据序列相应的九宫格是无解的。4.B FS算法队列：Q ue ue o p e n =n e w Q u e u e();存放待扩展的节点L i s t :L i s t c 1 o s e d =n e w L i s t ();存放已被扩展过的节点A r r a y L i s t m a p =n e w A r r a
3、y L i s t ();/存放答案H a s h T a l e：H a s h t a b l e t a b l e =n e w H a s h t a b 1 e ();构造哈希表以方便查找3.1.B FS算法介绍广度优先搜索算法B F S 基本思想:从图中某顶点v出发,逐层对节点进行拓展,并考察是否为目的节点,在第n层节点没有所有扩展并考察前,不对第n+1 层节点进行扩展。对九宫重排问题，即构造广度优先搜索树，从初始状态，运用广度优先搜索算法逐步找到目的状态的节点。3.2.状态空间表达状态空间用一维数组表达，每个节点存放在B f s t r结构体中的字符n o w 中，从第一行开始
4、从左往右给九宫格标号0 8,字符串n o w 元素下标代表格子位置,而n ow 数组中相应数组的值代表九宫格中存放的数码，用数值9 代表空格。3.3.搜索树3.4.算法环节搜索：(1 )把初始节点so 放入O P EN表。(2 )假如O P E N 表为空，则问题无解,退出。(3)把 O P E N 表的第一个节点(记为节点n )取出放入C L O S E 表。(4)考察节点n是否为目的节点。若是,则求得了问题的解，退出。(5 )若节点n不可扩展，则转第2步。(6)扩展节点n,将其子节点放入O PE N 表的尾部,并为每一个子节点都配置指向父节点的指针，然后转第2步。扩 展 f u n()：(
5、1)取 o p e n中第一个节点a 加入到clo s ed 中(2)找到a 9 中值为9 (空格)的位置i;(3)当。p e n 中元素个数不为0时，循环执行(3)到()3.1 从 open 中取出一个元素(状态)，并加入到c los ed中，对这个状态扩展;3.2若空格在第2、3歹 向左移动得到新状态；新状态不是目的状态，就加入open 中；新状态是目的状态，就加入clos ed中，编号加1,结束算法；3.3 若空格在第2、3行，向上移动得到新状态新状态不是目的状态,就加入open 中，新状态是目的状态,就加入c I。s ed中,编号加1 ,结束算法；3.4若空格在第1、2歹 IJ,向右移
6、动得到新状态新状态不是目的状态，就加入open 中，新状态是目的状态,就加入clo s e d 中,编号加1,结束算法；3 .5 若空格在第1 行，向下移动得到新状态新状态不是目的状态，就加入。P e n中，新状态是目的状态，就加入cl o s ed中,编号加1 ,结束算法；3.5.算法流程图4.启发式A*算法队列：Q u e u e o p en=new Que u e();存放待扩展的节点L i s t:L ist cl o sed=new Lis t ();存放已被扩展过的节点A r ra y Lis t ma p=new Arr a yList();/存放答案Ha s h Tai e:
7、H a shta b le tab 1 e=n ew Hasht a b le();构造哈希表以方便查找so r t 排序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.状态空间表达状态空间用一维数组表达，每个节点存放在B fs t r 结构体中的字符now中，从第一行开始从左往右给九宫格标号0 8,字符串n o w 元素下标代表格子位置，
8、而 now数组中相应数组的值代表九宫格中存放的数码,用数值9 代表空格。4.3.搜索树4.4.算法环节算法描述:3.1 把初始节点S O 放入O PE N 表，并建立目前只包含SO的图，记为G；3.2 检查O PE N 表是否为空,若为空则问题无解,退出；3.3 把 OP EN表的第一个节点取出放入C L O S E 表，并计该节点为n ;3.4考察节点n是否为目的节点。若是，则求得了问题的解,退出；3.5扩展节点n,生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M,并把这些子节点作为节点n的子节点加入G中：3.6 针对M中子节点的不同情况，分别进行如下解决：3.6.1 对于那些未曾
9、在G中出现过的M成员设立一个指向父节点（即节点n）的指针,并把它们放入O PE N 表；（不在O P E N 表）3.6.2 对于那些先前已经在G中出现过的M成员，拟定是否需要修改它指向父节点的指针；（在 O P E N 表中，对 g（x）进行更新）3.6.3对于那些先前已在G中出现并且已经扩展了的M成员，拟定是否需要修改其后继节点指向父节点的指针；（在 CLOSE表中，对 节 点 n子节点的子节点更新g（x）3.7 对 O P E N 表中的节点按估价函数进行排序；3.8 转第2步。4.5.算法流程图开始5.启发式A算法队列：Que u e o p 6 n=new Que u e();存放待
10、扩展的节点L i s t:L i st clo s ed=ne w L is t ();存放已被扩展过的节点A r r a y L i s t map=new Arr a y Li s 10;存放答案HashTa 1 e:H a shtable table=n ew Has h t a b le();构造哈希表以方便查找 s o rt 排序5.1算法介绍启发式搜索算法A,一般简称为A算法,是一种典型的启发式搜索算法。其基本思想是:定义一个评价函数f,对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的形式如下：Af(n)=g(n)+h(n);其中n 是被评价的节点。为 说明：g*
11、(n):表达从初始节点s 到节点n 的最短途径的耗散值；4*(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 值大的节点则被放在0 PEN表的后面,这样每次扩展节点时,都是选择当前f 值最小的节点来优先扩展。5.2.状态空间表达状态空间用一维数
12、组表达,每个节点存放在Bfs t r 结构体中的字符now中,从第一行开始从左往右给九宫格标号0 8,字 符 串 n o w 元素下标代表格子位置,而n ow 数组中相应数组的值代表九宫格中存放的数码,用数值9 代表空格。5.3.搜索树K(5)5.4.算法环节5 .1建立一个只含初始节点S o的搜索图G,把S o放入O p e n表，并计算f (S o)的值;5 .2假如Open表是空的，则失败，否则，继续下一步；5.3从O p e n表中取出f值为最小的结点,置于C 1。s e表,给这个结点编号为n；5.4 假如n是目的结点，则得解，算法成功退出。此解可从目的结点开始到初始节点的返回指针中得
13、到。否则，继续下一步；5.5扩展结点n。生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M,并把这些子节点作为节点n的子节点加入G中；5.6对于那些未曾在G中出现过的M成员设立一个指向父节点(即节点n)的指针，并把它们放入O P E N 表；5.7 对于那些先前已经在G中出现过的M成员，拟定是否需要修改它指向父节点的指针；(在 O P E N 表中，对 g(x)进行更新)5.8对于那些先前已在G中出现并且已经扩展了的M成员，拟定是否需要修改其后继节点指向父节点的指针；(在CL OSE表中，对节点n子节点的子节点更新g (x)5.9按 f 值从大至小的顺序,对0 p e n 表中的结点重
14、新排序；5.1 0 返回环节2。5.5算法流程图6.数生成算法V开始v6.1.算法介绍在数据结构、算法分析与设计、科学模拟等方面都需要用到数。由于在数学上，整数是离散型的,实数是连续型的,而在某一具体的工程技术应用中，也许尚有数据值的范围性和是否可反复性的规定。因此，我们就整数数和实数数，以及它们的数据值的范围性和是否可反复性，分别对其算法加以分析和设计。1 M i c r o s o f t VC+产生数的原理：Sr a nd()和 Ran d()函数。它本质上是运用线性同余法，y =a x+b(m o d m)(,其中a,b,m 都是常数。因此r a n d 的产生决定于x,x被称为See
15、d。Seed需要程序中设定,一般情况下取系统时间作为种子。它产生的数之间的相关性很小，取值范围是0 3 2 7 6 7 (in t),即双字节(1 6 位 数)，若用u n s i g n e d i n t 双字节是6 5 5 3 5,四字节是，一般可以满足规定。根据整数数范围性和是否可反复性，可分为：(1)某范围内可反复。(2)某范围内不可反复。(3)枚举可反复。(4)枚举不可反复。所谓范围，是指在两个数nl 和 n 2之间。例如,在1 0 0和 2 0 0 之间这个范围，那么，只要产生的整数数n 满 足 1 0 0 WnW2 0 0,都符合规定。所谓枚举，是指有限的、己知的、若干个不连续
16、的整数。例如,3 4、2 0、1 2 3、5、8 0 0 这 5个整数就是一种枚举数，也就是单独可以一个个拟定下来。某范围内可反复在 Vi s u al B as i c 语言中，有一个数函数R n d。语法：Rnd (nu mber)。参数n u mber 可选,n u m b e r 的值决定了 Rn d生成数的方式。R n d 函数返回小于 1但大于或等于0的值。Num b e r 类型R n d 结果小于零每次都相同的数字,并将num b e r 用作种子。大于零序列中的下一个数。等于零最近生成的数字。未提供序列中的下一个数。在 调 用 Rnd之前，先 使 用无参数的Random iz
17、e语句初始化数生成器，该生成器具有一个基于系记录时器的种子。若要生成某给定范围内的整数,可使用以下公式：In t(u pper b o und lo we r bou n d+1)*Rnd+lowerboun d)这里，upp e r bou n d 是此范围的上限，而 low e rb o u n d 是范围的下限6.2.程序流程图：7 .DFS黄鑫负责部分(请注意与上面的格式搭配一下)8.效果图滑块问题求解系统(1)D F S时当显示只需2、3步时,搜索空间爆栈，内存溢出，失败。暂时解决办法:重新生成结束状态或者初始状态(2)BF S、A、A*时显示3 2步时,搜索空间太多，内存溢出，失败
18、。暂时解决办法:重新生成结束状态或者初始状态(3)不能同时生成结束状态图和初始状态图。暂时解决办法:分步生成结束状态或者初始状态(4)未完毕工作:1、时间显示2、自动演示8.1初始界面：8.3.BFS效果图:8.3.启发式A*效果图:震 滑块问题求解系统1.0 人工智能实会状态空洵的穷搜索发O简单深度优先搜索O启发式搜索算法AI显 示 时 间搜索给果搜索结果为：用启发式搜索A*共需要23步简单广度优先搜索O启发式搜索篁法A*并品捶素T算法说明定义e 采第生）:江果一个恬外宣数可以技戴三之於任，或G称之法仝AW必具考夫充生，算 法 是 一，、可关弟式能好代光算法.8.4 启发式A效果图:8.5.
19、DFS效果图:身 滑块问题求解系统1.0 人工智能实险状态空间的穷搜索发O简单深度优先搜索O启发式搜索篁法AI显 示 时 间 搜索结果搜索结果为：用BPS共需要25步简单广度优先搜索O启发式搜索篁法A*弄 捶 素|当前步数：手 动模式I下 一 步II恢复初始状I0自动演示结束状态菖法说明定又:以斐近起更FWK程度常依弊，逐疔逐芸三展替，点搜索方法=纯.不授索是逐W之不在，即左封七一里时任一七点进咛按森之前，搜索充女三忆尸考中点：一玷曼什什搜案，但若有铝在，必转换到它.9.代码共涉及3 个工程文献：Common RAND YYSEN工程文献名类名功能代码行数Comm o nAse.c s实现A
20、算法约 350行C o mm o nA s t r.c sA 算法的解空间27C ommonB fs.cs实现广度优先算法220CommonB f st r cs广度优先算法的解空间15C o mmo nB s e.cs实现A*算法35C omm o ncommon,cs公用方法72C o mmonDfs.cs实现深度优先算法25 0Commo nD f s t r.c s深度优先算法解空间1 5RANDRandNum.es生成地图55YYYSENF or ml.esWind o ws功能实现290YYYSENForml.D e s i g n er.csW in d ow s界面设计660Y
21、YYSENP r o g r a m.csWindows界面入口2 11、cla s s Ase实现启发式A算法us i n g System;u sing S yst e m.C o lleclions.G eneri c;using Sy s tem.Te x t;using S y stem.Col 1 ectio n s;约3 5 0 行n a mespace Comm o n(pu b 1 i c cl a s s Ase(private int SS=new int9;pri v at e int E NN=new i nt 9;pr i v a t e st r ing S；p
22、r ivate s t ri n g N；pub 1 ic bool BOOL;/是否有解：List o pen=n e w List()J/未搜索；LisKA s tr cl o se d=new L i s t()；已搜索;Hash t ab I e t able=new Hashtable()；p ub I ic AnayL i st ma p=n e w ArrayLi s t();publ i c Ase(i n t SS,i n t NN)(SS.CopyTo(this.SS,0);N N.Copy T o(th i s.NN,0)；S=c o mm o n.c hangest r
23、 in g(SS)；N=comm o n.c h a ng e st r ing(NN);BOOL=c ommo n.c hcck(th i s.SS,t his.N N,th i s.SS.L e n g th);)pu b lie void search()/呵呵，调用其他的搜索,不解释Bfs an s b f s=new Bfs(t h i s.S S,t h is.NN);ansbfs.sea r c h()；m ap=ansb f s.map;r e t urn;if(S!=N)(A s tr node=new Astr();n o d e.now=S;nod e.qia n=；no
24、 d e.gn=0;node.wn=f wn(S,N)；n od e.fn=nod e.g n+n o d e .wn；open.Add(n ode);t able.Ad d(n o de.now,nod e.gn)；fu n();1/构造最佳答案;int i0；A s t r p=closed clo s ed.C o u nt-1；closed.Remove(p);map.A d d(p.n o w);wh i le(p.now!=S)(for(i=0；i c lo s ed.C o unt;i+)(i f(closed i.now=p.q i a n)(map.Add(closed|i.
25、now)；p=closedi;clo s ed.R e m o v e(p);br e ak;1)/互换i nt j=0;fbr(i=0,j=ma p.C ount-1 ；i j;i+,j-)(s tr i ng ss s=mapi a s string;map i =mapj;map j)/互换值p riv a t e v oid swap(int a,i n t x,in t y)(i nt t;t=ax;ax=a y;a y =t;1p ri v a t e i n t fwn(s tring s 1,strin g s 2)(i n t i；i nt s u m=0;f o r(i=0
26、;i 1 000 0)re t u m；/找最小元素/li s t.So r t(x,y)=y.Age-x.Age);排序int i=0;/去ope n 中的f n最小值node_ 1 =o p eni；for(i=0;i=open Li,fn)(n ode_l=o p eni;)o p en.R emov e(nod e 1 );closed.Ad d(n o de_l);if(nodc_l.now=N)ret u m；a=commo n.chan g ei n t(node_ 1 .now);for(i=0；i a.Length：i+)(i f(ai=9)brea k;)int ind e
27、 x=i；if(i%3!=0)(a.C o p y To(b,0);sw a p(b,i,i-1)；s=c omm o n.cha n g e s t ring(b);no d e_2.now=s;n o de_2.q i an=n o d e _ l.n o w;node_ 2.g n=no d e_l.g n+1；node_2.w n=fwn(s,N);node _ 2.fn=nod e _ 2.gn+node_2.wn;intj=0;for(j=0；j nod e _2.g n)(op e n.Re move At(j)；open.Add(node_2);table|nod e _2.n
28、o w =no d e_2.g n;)b re a k;)int k：for(k=0;k n o d e_2.gn)(cl o sed.Rem o veAt(k);close d.Add(node_2);ta b leno d e_ 2.n o w=node_2.g n;)break；)i f(j=op e n.C o unt)(i f(k=cl o sed.C o u nt)Io p e n.A dd(node_ 2);tabi e.Add(no d e_ 2.now,node_ 2.g n);)if(i-3=0)(a.C o p yTo(b,0);swap(b,i,i-3);s=c o m
29、m o n.changestrin g(b)；n od e _ 2.now=s;n ode_2.qian=node_l.now;n o d e_2.g n=n o de_l.gn+1;no d e _ 2.w n=fwn(s,N);no d e_2.f n=n o d e_2.gn+node_ 2.wn;int j=0；for(j=0;j node_ 2.g n)(open.Remove At(j)；open.Add(node_2)；tab 1 enode_ 2.now=nod e _ 2.gn;)b reak；)int k;f o r(k=0;k n o d e_2.g n)(closed.
30、Rem o v e A t(k)：c los e d.Ad d(no d e_2)；table n ode_2.now=n o d e_2.gn；)b r eak;)if(j=ope n.Co u nt&k=closed.Co u nt)(op e n.Add(n o d e_2);tab 1 e.A d d(node_2.n o w,n o de_2.g n);)i f(i%3!=2)a.Co p yTo(b,0);swap(b,i,i+1);s=common,c hang e str i ng(b);no d e_2.now=s;no d e _2.qia n=node.now;node_
31、 2.g n=no d e_l.gn+1;node_ 2.w n=fw n(s,N);node_2.f n=node_ 2.g n+n o de_ 2.w n；i n t j=0;f or(j=0;j nod e _2.g n)o p e n.R e moveAt(j);op e n.Add(node2);t ab 1 e n ode_ 2.n ow=nod e _ 2.gn；b r ea k;)int k;f or(k=0；k n o de_ 2.gn)(c losed.Remove A t(k)；c 1 ose d.Ad d(node_2);t a blcn o d e _ 2.now=n
32、ode_2.gn；break；)if(j=ope n.C o unt&k=c 1 osed.C ount)o p e n.A d d(n od e _ 2 );t a b l e .A d d(n od e _ 2.n ow,n od e _ 2.g n);)Ii f(i+3 9 )a.Cop y T o(b ,0 );s w叩(b,i ,i +3 )；s =c om m on.c h a n g e s t r i n g (b );n od e _ 2.n o w =s;n o d e _ 2.q i a n =n od e _ l.n ow;n o d e _ 2.g n=n od e
33、_ l.g n +1 ；n o d e _ 2.wn=f w n (s ,N)；n od e _ 2.f n =n o d e _ 2 ,g n+n od e _ 2.w n ;i n t j=O;f b r(j =0;j n od e _ 2.g n)op e n.RcmoveAt(j);open.A d d(node_2);tablcfnode_ 2.n ow=node_ 2.g n;bre a k;)i n i k;f or(k=0;k n o de_ 2,gn)(closed.Remove A t(k);c lo s ed.A d d(n od e _2);t a bl e node_
34、2.now=nod e_2.g n;b r e ak：)if(j=ope n.Co u n t&k=c I o s e d.C o u n t)o p en.A d d(nod e _2);ta b 1c.A d d(node_2.now,node_2.g n);)1(2 c la s s A s tr 重要是启发式搜索算法A 算法的解空间usin g S y s tem；u sing System.Coll e ctio n s.G e n e r i c；u s i n g System.Tex t;/2 7n a mespa c e C o mmon(struct Astrp ubl i
35、 c s t ring n o w ge t；set;/从起始点到n 的途径长度/p ub 1 i c i n t g n get;set;/summary/代表节点n的格局与目的节点的格局相比文职不符的数目/p u blic i n t wn g et；set；/f n=g n+w n;/public i nt fn g e t；set;/前一个的状态；/pu b 1 i c s t rin g q i an g e t；st)3、B FS重要是完毕广度优先搜索功能usi n g S y s t em;using S y s tem.Co 1 lec t i ons.G e n er i c
36、;u sing Sy s t em.Text;using S y stem.C o 1 1 e c t io n s;/220name s p ace Common(public clas s B f s(pr i v a te i n t SS=new in t 9 ;priva t e i n t NN=new i n t 9；pri v ate s t r ing S;private string N;pub 1 ic b o ol BOO L;/是否有解;Hashtable t ab 1 e=ne w IIas h ta b 1 e()；Qu e ue o pen=n e w Q u
37、eue();L i s t clo s e d=new List();p u blic ArrayList map=n ew ArrayL i s t();pu b 1 i c Bfs(int SS,i nt NN)(S S.C opyTo(t h i s.S S,0);NN.C o pyT o(this.NN,0);S=common.chang e stri n g(SS);N=commo n.c h a nges t ring(NN);B OOL=common,c h e c k (this.S S,th i s.NN,this.S S.Len g t h)；)pr i vate v oi
38、 d swap(inl a,i nt x,i n t y)i nt t;t=ax；ax=a y;a y =t;p ublic v oid s e a r ch()i f(S!=N)Bfst r no d e=n e w B f str();node.no w=S；nod e.q i an=”；node,tol=0；ope n.Enqueue(n o de)；tabi e.Add(S,0);fun();)e Ise(B f str nod e=n e w B f str();node.n o w=S;no d e.qia n=”；node.tol=0；cl o s ed.A d d(node);
39、Iin t i=0;/在 ck s ed中去寻找答案Bfs tip =new Bf s tr()；p=c lo s e d clos e d.Count-1;closed.R emove(p)；map.Add(p.now);w h ile(p.now!=S)f or(i=0;i clos e d.C o unt;i+)(i f(clo s e d i.now=p.qi a n)(ma p.Add(c losedi.now);p=c lo s e d i；cl o s e d.Remo v e(p);b r eak;)i n t j=0;f or(i=0,j=map.C o unt 1;i j;
40、i+,j-)(st r i n g s ss=mapi as s t r i n g ;mapi=map j;ma p Lj=s ss;pri v a t e void fun()Bf s t r node_ 0=new Bf s tr()；B f s t r node_l=new B f str()；i n t a=new in t 9;i n t b=new int9J;st r i ng s;while(o pe n.Cou n t!=0)(/取 o p e n 中的第一个节点；no d e_ 0=(B f s tr)(o p e n.De q ueue();close d.A d d(
41、nod e _ 0);/a=c onun o n.ch a n geint(node_ 0.n o w);in t i=0;for(i=0;i=0)a.C o pyTo(b,0);swap(b,i,i3);s=c o mm o n.c h a n ge s t r i n g(b);if(s!=N)(if(!table.Cont a i n s(s)(n o de_l.now =s;no d e _ 1.qian=no d e _ 0.now；n od e _ l.to l=node_0.tol+1;o p e n .Enqueue(no d e_l);t able.Add(s,no d e_
42、 1.t o 1 )；)else(n od e _1.now=s；n o d e_ 1.q ia n =n o de_0.n o w;n o d e _1.t ol=n o de_O.t o 1 +1;table.Add(s,node_l.tol);c 1 o sed.A d d(node_ 1);br e ak;)if(i%3!=2)a.C o p yT o(b,0);s w a p(b,i,i+1);s=c o mmon.c h an g estri n g(b);if(s!=N)(if(!t a ble.C o nt a ins(s)(node,now=s；nod e _ 1.q ian
43、=node_0.now;node_l.tol=n o de_0.tol+1；o p e n.E nqu e u e(node_l);t able.Add(s,n od e _l.t o 1);e Ise(no d e_l.now=s；no d e_l.qian=nod e _0.n ow;n o d e_l.t ol=node_ 0.tol+1;c 1 osed.Add(node 1);table.Add(s,n o de_l.to 1 );break;)i f(i+3 9)a.Cop y To(b,0);swap(b,i,i+3)；s=c o mmon.c han g e s t r i n
44、g(b);i f(s!=N)(i f(Jtable.Cont a in s(s)(n o d e_l.now=s；node_ l.qian=nod e _ 0.n o w；nod e _ l.to 1 =n o de_0.t o 1 +1;open.E nque u e(node_ 1)；tab 1 e.A d d(s,n ode_ l.to 1 );)else(nod e _ 1.n o w=s;n o de_l.qi a n=node_0.now；n od e _ 1.tol=n o de_0.tol+1;c losed.Add(no de_l);tab 1 e.A d d(s,nod e
45、 _ 1 .t ol);b r e ak;)4、Bfst r 功能为深度优先搜索的解空间usi n g System；u s ing S ys t em.Co 1 lec t ions.G e n eric；u s ing Sys t em.Text；/I 5n a m espace C o mmonpu b 1 i c s true t Bfstr(pub l i e s t rin g n ow get;s epublic st r ing qian g e t;s et；publ i c i n t tol get;set;)us i ng S ys t em;us i n g S ys
46、tem.C o 1 1 ections.G e n e r i c;u sing S y stem.T ext;u sing S ystem.Colle c t i on s;/3 5nam e sp a ce C o mmonp u b 1 ic cla s s Bsepri v a te i nt SS=new int 9;p r i v a t e int NN=n ew i n t9；private s tring S；p ri v ate str i n g N;pub 1 i c b o o l B O O L;/是否有解p u b l i c Array L is t map=n
47、 e w Arr a y L i st();p ub 1 ic B se(in t ESS,int NN)SS.Cop y To(t h i s.SS,0)；NN.CopyTo(t hi s.NN,0);S=c o mmon.chan g e s tr i ng(SS)；N=commo n.chan g e stri n g(NN)；BO OL=comm on.check(t h i s.S S,t hi s.N N,t his.S S.Length)；p ublic v oid se a rch()(B fs a nsbfs=n e w B f s(th i s.S S,th i s.N N
48、);ans b f s.se a rch();ma p=a nsbf s.m a p;)5、包含的公共方法using S y s te m；u s in g System.Co 1 lect io n s.G eneri c;us i ng System.Tex t;u sing RAND；/72namespac e Comm o n(public c 1 ass common检查接是否和理p u b 1 ic s t atic bool check(int a,i nt b,int num)(in t i,j；i n t sum=0；int an s=0;fo r(i=1;i =0；j-)i
49、f(aj ai)s u m+；f(b jj bi)a n s+;)i f(sum%2=ans%2)re t u r n t rue；else ret u rn false;pu b 1 i c s tatic s t ring c h a n g est r in g(i n t a)(int i;string st r=nfor(i=0;i a.Length;i+)(str+=C onv e rt.To S tr i n g(a i);)r eturn str;)p u b 1 ic s t a t ic in t c h a n g e!nt(s tri ng str)(int i=0;i
50、nt a=new ints t r.Lengt h；f o r (i=0;i s t r.Length;i+)a i =Co n ver t.Tolnt 3 2(s t r .Subs t rin g(i,1);retu r n a;)public stat i c int gets()|in t s=new int 9;Rand N um r=new Ra n dNum();s=r.G etRandomNums(1,9,9);r etur n s；)public static int Lj g e t n()(int n=n e w in t 9;R an d Num r=n e w Ran