人工智能实验报告

人工智能

九宫格重移——搜索

成员：赵春杰 2009210665

羊森 2009210653

黄鑫 2009210

周成兵 2009210664

王素娟 2009210644

1.问题描述：

八数码问题也称为九宫问题。在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.状态空间表示

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.状态空间表示

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 生成随机数的方式。Rnd 函数返回小于 1 但大于或等于 0 的值。

在调用 Rnd 之前，先使用无参数的 Randomize 语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子。

若要生成某给定范围内的随机整数，可使用以下公式：

Int((upperbound - lowerbound + 1) * Rnd + lowerbound)

这里，upperbound 是此范围的上限，而 lowerbound 是范围的下限

6.2.程序流程图：

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个工程文件：Common RAND YYSEN

1、class Ase实现启发式A算法

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

//约350行

namespace Common

{

public class Ase

{

private int[] SS=new int[9];

private int[] NN=new int[9];

private string S;

private string N;

public bool BOOL;//是否有解；

List<Astr> open=new List<Astr>() ;//未搜索；

List<Astr> closed = new List<Astr>();//已搜索；

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 < closed.Count; i++)

{

if (closed[i].now == p.qian)

{

map.Add(closed[i].now);

p = closed[i];

closed.Remove(p);

break;

}

//交换

int j = 0;

for (i = 0, j = map.Count - 1; i < j; i++, j--)

{

string sss = map[i] as string;

map[i] = map[j];

map[j] = sss;

}

//交换值

private void swap(int[] a, int x, int y)

{

int t;

t = a[x];

a[x] = a[y];

a[y] = t;

}

private int fwn(string s1, string s2)

{

int i;

int sum=0;

for (i = 0; i < s1.Length; i++)

{

if (s1[i] != s2[i])

sum++;

}

return sum;

}

private void fun()

{

Astr node_1 = new Astr();

Astr node_2 = new Astr();

//Astr node_3 = new Astr();

int[] a = new int[9];

int[] b = new int[9];

string s;

int count = 0;

while (true&&open.Count !=0)

{

if (count++ > 10000)

return;

//找最小元素

//list.Sort((x, y) => y.Age - x.Age);排序

int i = 0;

//去open中的fn最小值

node_1 = open[i];

for (i = 0; i < open.Count; i++)

{

if (node_1.fn >= open[i].fn)

{

node_1 = open[i];

}

open.Remove (node_1);

closed.Add(node_1);

if(node_1.now ==N)

return ;

a = common.changeint(node_1.now);

for (i = 0; i < a.Length; i++)

{

if (a[i] == 9)

break;

}

int index = 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 ;

int j=0;

for (j = 0; j < open.Count; 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;

}

break;

}

int k;

for (k = 0; k < closed.Count; k++)

{

if (closed [k].now == node_2.now)

{

if (closed [k].gn > node_2.gn)

{

closed.RemoveAt(k);

closed.Add(node_2);

table[node_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 < open.Count; 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;

}break;

}

int k;

for (k = 0; k < closed.Count; k++)

{

if (closed [k].now == node_2.now)

{

if (closed [k].gn > node_2.gn)

{

closed.RemoveAt(k);

closed.Add(node_2);

table[node_2.now] = node_2.gn;

}break;

}

if (j == open.Count&&k==closed .Count )

{

open.Add(node_2);

table.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 < open.Count; 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;

}break;

}

int k;

for (k = 0; k < closed.Count; k++)

{

if (closed [k].now == node_2.now)

{

if (closed [k].gn > node_2.gn)

{

closed.RemoveAt(k);

closed.Add(node_2);

table[node_2.now] = node_2.gn;

} break;

}

if (j == open.Count&&k==closed .Count )

{

open.Add(node_2);

table.Add(node_2.now, node_2.gn);

}

if (i + 3 < 9)

{

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 < open.Count; 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;

}break;

}

int k;

for (k = 0; k < closed.Count; k++)

{

if (closed [k].now == node_2.now)

{

if (closed [k].gn > node_2.gn)

{

closed.RemoveAt(k);

closed.Add(node_2);

table[node_2.now] = node_2.gn;

} break;

}

if (j == open.Count&&k==closed .Count )

{

open.Add(node_2);

table.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; }

/// <summary>

/// 从起始点到n的路径长度

/// </summary>

public int gn { get; set; }

/// <summary>

/// 代表节点n的格局与目标节点的格局相比文职不符的数目

/// </summary>

public int wn { get; set; }

/// <summary>

/// fn=gn+wn;

/// </summary>

public int fn { get; set; }

/// <summary>

/// 前一个的状态；

/// </summary>

public string qian { get; set; }

}

3、BFS主要是完成广度优先搜索功能

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

//220

namespace Common

{

public class Bfs

{

private int[] SS = new int[9];

private int[] NN = new int[9];

private string S;

private string N;

public bool BOOL;//是否有解；

Hashtable table = new Hashtable();

Queue open = new Queue();

List<Bfstr> closed = new List<Bfstr>();

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 = a[x];

a[x] = a[y];

a[y] = 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 = 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];

closed.Remove(p);

break;

}

int j=0;

for (i = 0, j = map.Count - 1; i < j; i++, j--)

{

string sss = map[i] as string ;

map[i] = map[j];

map[j] = sss;

}

private void fun()

{

Bfstr node_0 = new Bfstr();

Bfstr node_1 = new Bfstr();

int[] a = new int[9];

int[] b = new int[9];

string s;

while (open.Count != 0)

{

//取open 中的第一个节点；

node_0 = (Bfstr)(open.Dequeue());

closed.Add(node_0);

a = common.changeint(node_0.now);

int i=0;

for (i = 0; i < a.Length; i++)

{

if (a[i] == 9)

break;

}

int index = i;

if (index % 3 != 0)

{

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);

}

else

{

node_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 >= 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);

}

else

{

node_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);

}

else

{

node_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 <9)

{

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);

}

else

{

node_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;

}

4、Bfstr功能为深度优先搜索的解空间

using System;

using System.Collections.Generic;

using System.Text;

//15

namespace Common

{

public struct Bfstr

{

public string now { get; set; }

public string qian { get; set; }

public int tol { get; set; }

}

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

//35

namespace Common

{

public class Bse

{

private int[] SS = new int[9];

private int[] NN = new int[9];

private string S;

private string N;

public bool BOOL;//是否有解

public ArrayList map = new ArrayList();

public Bse(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;

}

5、包含的公共方法

using System;

using System.Collections.Generic;

using System.Text;

using RAND;

//72

namespace Common

{

public class common

{

检查接是否和理

public static bool check(int[] a, int[] b, int num)

{

int i, j;

int sum = 0;

int ans = 0;

for (i = 1; i < num; i++)

{

for (j = i - 1; j >= 0; j--)

{

if (a[j] > a[i])

sum++;

if (b[j] > b[i])

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 < a.Length; i++)

{

str += Convert.ToString(a[i]);

}

return str;

}

public static int[] changeint(string str)

{

int i=0;

int[] a = new int[str.Length];

for (i = 0; i < str.Length; i++)

{

a[i] = Convert.ToInt32(str.Substring(i, 1));

}

return a;

}

public static int[] gets()

{

int[] s = new int[9];

RandNum r = new RandNum();

s=r.GetRandomNums(1,9,9);

return s;

}

public static int[] getn()

{

int[] n = new int[9];

RandNum r = new RandNum();

n = r.GetRandomNums(1, 9, 9);

return n;

}

6、Dfs功能是实现深度优先搜索

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

//250

namespace Common

{

//深度优先搜索

public class Dfs

{

//初始状态和结束状态

private int []SS;

private int[] NN;

private string S;

private string N;

public bool BOOL;

//存放答案

public ArrayList map;

//private int have;

private Stack<Dfstr> open = new Stack<Dfstr>();

private List<Dfstr> closed = new List<Dfstr>();

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();

}

else

{

Dfstr node = new Dfstr();

node.now = S;

node.qian = "";

node.tol = 0;

closed.Add(node);

}

int i = 0;

//在closed中去寻找答案

Dfstr p = new Dfstr();

p = 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];

closed.Remove(p);

break;

}

int j = 0;

for (i = 0, j = map.Count - 1; i < j; i++, j--)

{

string sss = map[i] as string;

map[i] = map[j];

map[j] = sss;

}

//开始深度优先搜索

private void fun()

{

Dfstr node_0 = new Dfstr();

Dfstr node_1 = new Dfstr();

int[] a = new int[9];

int[] b = new int[9];

string s;

while (open.Count != 0)

{

node_0 = open .Pop();

closed.Add(node_0);

//限制深度优先的dept

if (node_0.tol > 90)

continue;

a = common.changeint(node_0.now);

int i = 0;

for (i = 0; i < a.Length; i++)

{

if (a[i] == 9)

break;

}

int index = i;

if (i % 3 != 0)

{

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);

}

else

{

node_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 >= 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);

}

else

{

node_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);

}

else

{

node_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 < 9)

{

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);

}

else

{

node_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;

}

private void swap(int[] a, int x, int y)

{

int t;

t = a[x];

a[x] = a[y];

a[y] = t;

}

7、深度优先搜索的解空间

using System;

using System.Collections.Generic;

using System.Text;

//15

namespace Common

{

public struct Dfstr

{

public string now { get; set; }

public string qian { get; set; }

public int tol { get; set; }

}

8、生成9个随机数

using System;

using System.Collections.Generic;

using System.Text;

//55

namespace RAND

{

//生成随机数

public class RandNum

{

public int[] GetRandomNums(int min, int max, int nums)

{

if (min > max)

{

//如果参数max小雨min，交换两个的值

int a = min;

min = max;

max = a;

}

int deference = max - min;

if (deference <= nums - 1)

{

nums = deference + 1;

}

Random random = new Random();

int[] result = new int[nums];

int k = 0;

while (k < nums)

{

int x = random.Next(min, max + 1);

if (!IfHasOne(x, result))

{

result[k] = x;

k++;

}

return result;

}

private bool IfHasOne(int a, int[] b)

{

foreach (int c in b)

{

if (a == c) { return true; }

}

return false;

}

9、生成界面界面

namespace YYYSEN

{

//660

partial class Form1

{

/// <summary>

/// 必需的设计器变量。

/// </summary>

private System.ComponentModel.IContainer components = null;

/// <summary>

/// 清理所有正在使用的资源。

/// </summary>

/// <param name="disposing">如果应释放托管资源，为 true；否则为 false。</param>

protected override void Dispose(bool disposing)

{

if (disposing && (components != null))

{

components.Dispose();

}

base.Dispose(disposing);

}

#region Windows 窗体设计器生成的代码

/// <summary>

/// 设计器支持所需的方法 - 不要

/// 使用代码编辑器修改此方法的内容。

/// </summary>

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();

this.sum_lab = new System.Windows.Forms.Label();

this.shou_box = new System.Windows.Forms.CheckBox();

this.time_lab = new System.Windows.Forms.Label();

this.groupBox1.SuspendLayout();

this.groupBox3.SuspendLayout();

this.groupBox4.SuspendLayout();

this.groupBox5.SuspendLayout();

this.groupBox6.SuspendLayout();

this.groupBox7.SuspendLayout();

this.SuspendLayout();

// groupBox1

this.groupBox1.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox1.BackgroundImage")));

this.groupBox1.Controls.Add(this.a1_rad);

this.groupBox1.Controls.Add(this.bfs_rad);

this.groupBox1.Controls.Add(this.a_rad);

this.groupBox1.Controls.Add(this.dfs_rad);

this.groupBox1.Location = new System.Drawing.Point(12, 12);

this.groupBox1.Margin = new System.Windows.Forms.Padding(2);

this.groupBox1.Name = "groupBox1";

this.groupBox1.Padding = new System.Windows.Forms.Padding(2);

this.groupBox1.Size = new System.Drawing.Size(318, 110);

this.groupBox1.TabIndex = 0;

this.groupBox1.TabStop = false;

this.groupBox1.Text = "状态空间的穷搜索发";

// a1_rad

this.a1_rad.AutoSize = true;

this.a1_rad.Location = new System.Drawing.Point(167, 66);

this.a1_rad.Margin = new System.Windows.Forms.Padding(2);

this.a1_rad.Name = "a1_rad";

this.a1_rad.Size = new System.Drawing.Size(119, 16);

this.a1_rad.TabIndex = 3;

this.a1_rad.TabStop = true;

this.a1_rad.Text = "启发式搜索算法A*";

this.a1_rad.UseVisualStyleBackColor = true;

this.a1_rad.CheckedChanged += new System.EventHandler(this.a1_rad_CheckedChanged);

// bfs_rad

this.bfs_rad.AutoSize = true;

this.bfs_rad.Location = new System.Drawing.Point(22, 66);

this.bfs_rad.Margin = new System.Windows.Forms.Padding(2);

this.bfs_rad.Name = "bfs_rad";

this.bfs_rad.Size = new System.Drawing.Size(119, 16);

this.bfs_rad.TabIndex = 1;

this.bfs_rad.TabStop = true;

this.bfs_rad.Text = "简单广度优先搜索";

this.bfs_rad.UseVisualStyleBackColor = true;

this.bfs_rad.CheckedChanged += new System.EventHandler(this.bfs_rad_CheckedChanged);

// a_rad

this.a_rad.AutoSize = true;

this.a_rad.Location = new System.Drawing.Point(167, 20);

this.a_rad.Margin = new System.Windows.Forms.Padding(2);

this.a_rad.Name = "a_rad";

this.a_rad.Size = new System.Drawing.Size(113, 16);

this.a_rad.TabIndex = 2;

this.a_rad.TabStop = true;

this.a_rad.Text = "启发式搜索算法A";

this.a_rad.UseVisualStyleBackColor = true;

this.a_rad.CheckedChanged += new System.EventHandler(this.a_rad_CheckedChanged);

// dfs_rad

this.dfs_rad.AutoSize = true;

this.dfs_rad.Location = new System.Drawing.Point(22, 20);

this.dfs_rad.Margin = new System.Windows.Forms.Padding(2);

this.dfs_rad.Name = "dfs_rad";

this.dfs_rad.Size = new System.Drawing.Size(119, 16);

this.dfs_rad.TabIndex = 0;

this.dfs_rad.TabStop = true;

this.dfs_rad.Text = "简单深度优先搜索";

this.dfs_rad.UseVisualStyleBackColor = true;

this.dfs_rad.Click += new System.EventHandler(this.dfs_rad_Click);

// time_btn

this.time_btn.Location = new System.Drawing.Point(373, 26);

this.time_btn.Margin = new System.Windows.Forms.Padding(2);

this.time_btn.Name = "time_btn";

this.time_btn.Size = new System.Drawing.Size(74, 23);

this.time_btn.TabIndex = 2;

this.time_btn.Text = "显示时间";

this.time_btn.UseVisualStyleBackColor = true;

// search_btn

this.search_btn.Location = new System.Drawing.Point(373, 85);

this.search_btn.Margin = new System.Windows.Forms.Padding(2);

this.search_btn.Name = "search_btn";

this.search_btn.Size = new System.Drawing.Size(74, 23);

this.search_btn.TabIndex = 3;

this.search_btn.Text = "开始搜索";

this.search_btn.UseVisualStyleBackColor = true;

this.search_btn.Click += new System.EventHandler(this.search_btn_Click);

// groupBox3

this.groupBox3.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox3.BackgroundImage")));

this.groupBox3.Controls.Add(this.s9_btn);

this.groupBox3.Controls.Add(this.s8_btn);

this.groupBox3.Controls.Add(this.s7_btn);

this.groupBox3.Controls.Add(this.s6_btn);

this.groupBox3.Controls.Add(this.s5_btn);

this.groupBox3.Controls.Add(this.s4_btn);

this.groupBox3.Controls.Add(this.s3_btn);

this.groupBox3.Controls.Add(this.s2_btn);

this.groupBox3.Controls.Add(this.s1_btn);

this.groupBox3.Location = new System.Drawing.Point(100, 158);

this.groupBox3.Margin = new System.Windows.Forms.Padding(2);

this.groupBox3.Name = "groupBox3";

this.groupBox3.Padding = new System.Windows.Forms.Padding(2);

this.groupBox3.Size = new System.Drawing.Size(200, 200);

this.groupBox3.TabIndex = 4;

this.groupBox3.TabStop = false;

this.groupBox3.Text = "初始状态";

// s9_btn

this.s9_btn.BackColor = System.Drawing.Color.Cyan;

this.s9_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s9_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s9_btn.Location = new System.Drawing.Point(132, 140);

this.s9_btn.Margin = new System.Windows.Forms.Padding(2);

this.s9_btn.Name = "s9_btn";

this.s9_btn.Size = new System.Drawing.Size(60, 60);

this.s9_btn.TabIndex = 8;

this.s9_btn.UseVisualStyleBackColor = false;

// s8_btn

this.s8_btn.BackColor = System.Drawing.Color.Cyan;

this.s8_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s8_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s8_btn.Location = new System.Drawing.Point(68, 140);

this.s8_btn.Margin = new System.Windows.Forms.Padding(2);

this.s8_btn.Name = "s8_btn";

this.s8_btn.Size = new System.Drawing.Size(60, 60);

this.s8_btn.TabIndex = 7;

this.s8_btn.UseVisualStyleBackColor = false;

// s7_btn

this.s7_btn.BackColor = System.Drawing.Color.Cyan;

this.s7_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s7_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s7_btn.Location = new System.Drawing.Point(6, 140);

this.s7_btn.Margin = new System.Windows.Forms.Padding(2);

this.s7_btn.Name = "s7_btn";

this.s7_btn.Size = new System.Drawing.Size(60, 60);

this.s7_btn.TabIndex = 6;

this.s7_btn.UseVisualStyleBackColor = false;

// s6_btn

this.s6_btn.BackColor = System.Drawing.Color.Cyan;

this.s6_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s6_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s6_btn.Location = new System.Drawing.Point(132, 80);

this.s6_btn.Margin = new System.Windows.Forms.Padding(2);

this.s6_btn.Name = "s6_btn";

this.s6_btn.Size = new System.Drawing.Size(60, 60);

this.s6_btn.TabIndex = 5;

this.s6_btn.UseVisualStyleBackColor = false;

// s5_btn

this.s5_btn.BackColor = System.Drawing.Color.Cyan;

this.s5_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s5_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s5_btn.Location = new System.Drawing.Point(68, 80);

this.s5_btn.Margin = new System.Windows.Forms.Padding(2);

this.s5_btn.Name = "s5_btn";

this.s5_btn.Size = new System.Drawing.Size(60, 60);

this.s5_btn.TabIndex = 4;

this.s5_btn.UseVisualStyleBackColor = false;

// s4_btn

this.s4_btn.BackColor = System.Drawing.Color.Cyan;

this.s4_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s4_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s4_btn.Location = new System.Drawing.Point(6, 80);

this.s4_btn.Margin = new System.Windows.Forms.Padding(2);

this.s4_btn.Name = "s4_btn";

this.s4_btn.Size = new System.Drawing.Size(60, 60);

this.s4_btn.TabIndex = 3;

this.s4_btn.UseVisualStyleBackColor = false;

// s3_btn

this.s3_btn.BackColor = System.Drawing.Color.Cyan;

this.s3_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s3_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s3_btn.Location = new System.Drawing.Point(132, 20);

this.s3_btn.Margin = new System.Windows.Forms.Padding(2);

this.s3_btn.Name = "s3_btn";

this.s3_btn.Size = new System.Drawing.Size(60, 60);

this.s3_btn.TabIndex = 2;

this.s3_btn.Text = "3";

this.s3_btn.UseVisualStyleBackColor = false;

// s2_btn

this.s2_btn.BackColor = System.Drawing.Color.Cyan;

this.s2_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s2_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s2_btn.Location = new System.Drawing.Point(68, 20);

this.s2_btn.Margin = new System.Windows.Forms.Padding(2);

this.s2_btn.Name = "s2_btn";

this.s2_btn.Size = new System.Drawing.Size(60, 60);

this.s2_btn.TabIndex = 1;

this.s2_btn.UseVisualStyleBackColor = false;

// s1_btn

this.s1_btn.BackColor = System.Drawing.Color.Cyan;

this.s1_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.s1_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.s1_btn.Location = new System.Drawing.Point(6, 20);

this.s1_btn.Margin = new System.Windows.Forms.Padding(2);

this.s1_btn.Name = "s1_btn";

this.s1_btn.Size = new System.Drawing.Size(60, 60);

this.s1_btn.TabIndex = 0;

this.s1_btn.UseVisualStyleBackColor = false;

// groupBox4

this.groupBox4.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox4.BackgroundImage")));

this.groupBox4.Controls.Add(this.n9_btn);

this.groupBox4.Controls.Add(this.n8_btn);

this.groupBox4.Controls.Add(this.n7_btn);

this.groupBox4.Controls.Add(this.n6_btn);

this.groupBox4.Controls.Add(this.n5_btn);

this.groupBox4.Controls.Add(this.n4_btn);

this.groupBox4.Controls.Add(this.n3_btn);

this.groupBox4.Controls.Add(this.n2_btn);

this.groupBox4.Controls.Add(this.n1_btn);

this.groupBox4.Location = new System.Drawing.Point(382, 158);

this.groupBox4.Margin = new System.Windows.Forms.Padding(2);

this.groupBox4.Name = "groupBox4";

this.groupBox4.Padding = new System.Windows.Forms.Padding(2);

this.groupBox4.Size = new System.Drawing.Size(200, 200);

this.groupBox4.TabIndex = 5;

this.groupBox4.TabStop = false;

this.groupBox4.Text = "结束状态";

// n9_btn

this.n9_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n9_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n9_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n9_btn.Location = new System.Drawing.Point(132, 140);

this.n9_btn.Margin = new System.Windows.Forms.Padding(2);

this.n9_btn.Name = "n9_btn";

this.n9_btn.Size = new System.Drawing.Size(60, 60);

this.n9_btn.TabIndex = 17;

this.n9_btn.UseVisualStyleBackColor = false;

// n8_btn

this.n8_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n8_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n8_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n8_btn.Location = new System.Drawing.Point(68, 140);

this.n8_btn.Margin = new System.Windows.Forms.Padding(2);

this.n8_btn.Name = "n8_btn";

this.n8_btn.Size = new System.Drawing.Size(60, 60);

this.n8_btn.TabIndex = 16;

this.n8_btn.UseVisualStyleBackColor = false;

// n7_btn

this.n7_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n7_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n7_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n7_btn.Location = new System.Drawing.Point(6, 140);

this.n7_btn.Margin = new System.Windows.Forms.Padding(2);

this.n7_btn.Name = "n7_btn";

this.n7_btn.Size = new System.Drawing.Size(60, 60);

this.n7_btn.TabIndex = 15;

this.n7_btn.UseVisualStyleBackColor = false;

// n6_btn

this.n6_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n6_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n6_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n6_btn.Location = new System.Drawing.Point(132, 80);

this.n6_btn.Margin = new System.Windows.Forms.Padding(2);

this.n6_btn.Name = "n6_btn";

this.n6_btn.Size = new System.Drawing.Size(60, 60);

this.n6_btn.TabIndex = 14;

this.n6_btn.UseVisualStyleBackColor = false;

// n5_btn

this.n5_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n5_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n5_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n5_btn.Location = new System.Drawing.Point(68, 80);

this.n5_btn.Margin = new System.Windows.Forms.Padding(2);

this.n5_btn.Name = "n5_btn";

this.n5_btn.Size = new System.Drawing.Size(60, 60);

this.n5_btn.TabIndex = 13;

this.n5_btn.UseVisualStyleBackColor = false;

// n4_btn

this.n4_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n4_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n4_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n4_btn.Location = new System.Drawing.Point(6, 80);

this.n4_btn.Margin = new System.Windows.Forms.Padding(2);

this.n4_btn.Name = "n4_btn";

this.n4_btn.Size = new System.Drawing.Size(60, 60);

this.n4_btn.TabIndex = 12;

this.n4_btn.UseVisualStyleBackColor = false;

// n3_btn

this.n3_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n3_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n3_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n3_btn.Location = new System.Drawing.Point(132, 20);

this.n3_btn.Margin = new System.Windows.Forms.Padding(2);

this.n3_btn.Name = "n3_btn";

this.n3_btn.Size = new System.Drawing.Size(60, 60);

this.n3_btn.TabIndex = 11;

this.n3_btn.UseVisualStyleBackColor = false;

// n2_btn

this.n2_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n2_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n2_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n2_btn.Location = new System.Drawing.Point(68, 20);

this.n2_btn.Margin = new System.Windows.Forms.Padding(2);

this.n2_btn.Name = "n2_btn";

this.n2_btn.Size = new System.Drawing.Size(60, 60);

this.n2_btn.TabIndex = 10;

this.n2_btn.UseVisualStyleBackColor = false;

// n1_btn

this.n1_btn.BackColor = System.Drawing.Color.DodgerBlue;

this.n1_btn.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.n1_btn.Font = new System.Drawing.Font("隶书", 21.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.n1_btn.Location = new System.Drawing.Point(6, 20);

this.n1_btn.Margin = new System.Windows.Forms.Padding(2);

this.n1_btn.Name = "n1_btn";

this.n1_btn.Size = new System.Drawing.Size(60, 60);

this.n1_btn.TabIndex = 9;

this.n1_btn.UseVisualStyleBackColor = false;

// des_txt

this.des_txt.Cursor = System.Windows.Forms.Cursors.SizeAll;

this.des_txt.Font = new System.Drawing.Font("华文宋体", 8.999999F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.des_txt.Location = new System.Drawing.Point(14, 24);

this.des_txt.Margin = new System.Windows.Forms.Padding(2);

this.des_txt.Multiline = true;

this.des_txt.Name = "des_txt";

this.des_txt.ReadOnly = true;

this.des_txt.Size = new System.Drawing.Size(132, 154);

this.des_txt.TabIndex = 6;

// ans_txt

this.ans_txt.Location = new System.Drawing.Point(14, 20);

this.ans_txt.Margin = new System.Windows.Forms.Padding(2);

this.ans_txt.Multiline = true;

this.ans_txt.Name = "ans_txt";

this.ans_txt.ReadOnly = true;

this.ans_txt.Size = new System.Drawing.Size(268, 76);

this.ans_txt.TabIndex = 7;

// groupBox5

this.groupBox5.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox5.BackgroundImage")));

this.groupBox5.Controls.Add(this.des_txt);

this.groupBox5.Location = new System.Drawing.Point(598, 175);

this.groupBox5.Margin = new System.Windows.Forms.Padding(2);

this.groupBox5.Name = "groupBox5";

this.groupBox5.Padding = new System.Windows.Forms.Padding(2);

this.groupBox5.Size = new System.Drawing.Size(161, 184);

this.groupBox5.TabIndex = 8;

this.groupBox5.TabStop = false;

this.groupBox5.Text = "算法说明";

// groupBox6

this.groupBox6.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox6.BackgroundImage")));

this.groupBox6.Controls.Add(this.ans_txt);

this.groupBox6.Location = new System.Drawing.Point(476, 12);

this.groupBox6.Margin = new System.Windows.Forms.Padding(2);

this.groupBox6.Name = "groupBox6";

this.groupBox6.Padding = new System.Windows.Forms.Padding(2);

this.groupBox6.Size = new System.Drawing.Size(289, 110);

this.groupBox6.TabIndex = 9;

this.groupBox6.TabStop = false;

this.groupBox6.Text = "搜索结果";

// groupBox7

this.groupBox7.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("groupBox7.BackgroundImage")));

this.groupBox7.Controls.Add(this.check_box);

this.groupBox7.Controls.Add(this.jie_box);

this.groupBox7.Controls.Add(this.chu_box);

this.groupBox7.Controls.Add(this.rand_btn);

this.groupBox7.Controls.Add(this.moren_btn);

this.groupBox7.Location = new System.Drawing.Point(13, 158);

this.groupBox7.Margin = new System.Windows.Forms.Padding(2);

this.groupBox7.Name = "groupBox7";

this.groupBox7.Padding = new System.Windows.Forms.Padding(2);

this.groupBox7.Size = new System.Drawing.Size(86, 200);

this.groupBox7.TabIndex = 10;

this.groupBox7.TabStop = false;

this.groupBox7.Text = "状态设置";

// check_box

this.check_box.AutoSize = true;

this.check_box.Location = new System.Drawing.Point(7, 146);

this.check_box.Margin = new System.Windows.Forms.Padding(2);

this.check_box.Name = "check_box";

this.check_box.Size = new System.Drawing.Size(72, 16);

this.check_box.TabIndex = 4;

this.check_box.Text = "避免无解";

this.check_box.UseVisualStyleBackColor = true;

// jie_box

this.jie_box.AutoSize = true;

this.jie_box.Location = new System.Drawing.Point(7, 122);

this.jie_box.Margin = new System.Windows.Forms.Padding(2);

this.jie_box.Name = "jie_box";

this.jie_box.Size = new System.Drawing.Size(72, 16);

this.jie_box.TabIndex = 3;

this.jie_box.Text = "结束状态";

this.jie_box.UseVisualStyleBackColor = true;

// chu_box

this.chu_box.AutoSize = true;

this.chu_box.Location = new System.Drawing.Point(7, 98);

this.chu_box.Margin = new System.Windows.Forms.Padding(2);

this.chu_box.Name = "chu_box";

this.chu_box.Size = new System.Drawing.Size(72, 16);

this.chu_box.TabIndex = 2;

this.chu_box.Text = "初始状态";

this.chu_box.UseVisualStyleBackColor = true;

// rand_btn

this.rand_btn.Location = new System.Drawing.Point(6, 56);

this.rand_btn.Margin = new System.Windows.Forms.Padding(2);

this.rand_btn.Name = "rand_btn";

this.rand_btn.Size = new System.Drawing.Size(74, 23);

this.rand_btn.TabIndex = 1;

this.rand_btn.Text = "随机选择";

this.rand_btn.UseVisualStyleBackColor = true;

this.rand_btn.Click += new System.EventHandler(this.rand_btn_Click);

// moren_btn

this.moren_btn.Location = new System.Drawing.Point(6, 20);

this.moren_btn.Margin = new System.Windows.Forms.Padding(2);

this.moren_btn.Name = "moren_btn";

this.moren_btn.Size = new System.Drawing.Size(74, 23);

this.moren_btn.TabIndex = 0;

this.moren_btn.Text = "默认状态";

this.moren_btn.UseVisualStyleBackColor = true;

this.moren_btn.Click += new System.EventHandler(this.moren_btn_Click);

// up_btn

this.up_btn.Location = new System.Drawing.Point(307, 197);

this.up_btn.Margin = new System.Windows.Forms.Padding(2);

this.up_btn.Name = "up_btn";

this.up_btn.Size = new System.Drawing.Size(74, 23);

this.up_btn.TabIndex = 11;

this.up_btn.Text = "上一步";

this.up_btn.UseVisualStyleBackColor = true;

this.up_btn.Click += new System.EventHandler(this.up_btn_Click);

// down_btn

this.down_btn.Location = new System.Drawing.Point(307, 226);

this.down_btn.Margin = new System.Windows.Forms.Padding(2);

this.down_btn.Name = "down_btn";

this.down_btn.Size = new System.Drawing.Size(74, 23);

this.down_btn.TabIndex = 12;

this.down_btn.Text = "下一步";

this.down_btn.UseVisualStyleBackColor = true;

this.down_btn.Click += new System.EventHandler(this.down_btn_Click);

// recovery_btn

this.recovery_btn.Location = new System.Drawing.Point(307, 254);

this.recovery_btn.Margin = new System.Windows.Forms.Padding(2);

this.recovery_btn.Name = "recovery_btn";

this.recovery_btn.Size = new System.Drawing.Size(74, 23);

this.recovery_btn.TabIndex = 13;

this.recovery_btn.Text = "恢复初始状态";

this.recovery_btn.UseVisualStyleBackColor = true;

this.recovery_btn.Click += new System.EventHandler(this.recovery_btn_Click);

// zidong_btn

this.zidong_btn.Location = new System.Drawing.Point(307, 284);

this.zidong_btn.Margin = new System.Windows.Forms.Padding(2);

this.zidong_btn.Name = "zidong_btn";

this.zidong_btn.Size = new System.Drawing.Size(74, 23);

this.zidong_btn.TabIndex = 14;

this.zidong_btn.Text = "自动演示";

this.zidong_btn.UseVisualStyleBackColor = true;

// label1

this.label1.AutoSize = true;

this.label1.Location = new System.Drawing.Point(311, 326);

this.label1.Margin = new System.Windows.Forms.Padding(2, 0, 2, 0);

this.label1.Name = "label1";

this.label1.Size = new System.Drawing.Size(65, 12);

this.label1.TabIndex = 15;

this.label1.Text = "当前步数：";

// sum_lab

this.sum_lab.AutoSize = true;

this.sum_lab.Location = new System.Drawing.Point(336, 346);

this.sum_lab.Margin = new System.Windows.Forms.Padding(2, 0, 2, 0);

this.sum_lab.Name = "sum_lab";

this.sum_lab.Size = new System.Drawing.Size(11, 12);

this.sum_lab.TabIndex = 16;

this.sum_lab.Text = "0";

// shou_box

this.shou_box.AutoSize = true;

this.shou_box.Location = new System.Drawing.Point(307, 175);

this.shou_box.Margin = new System.Windows.Forms.Padding(2);

this.shou_box.Name = "shou_box";

this.shou_box.Size = new System.Drawing.Size(72, 16);

this.shou_box.TabIndex = 17;

this.shou_box.Text = "手动模式";

this.shou_box.UseVisualStyleBackColor = true;

// time_lab

this.time_lab.AutoSize = true;

this.time_lab.Location = new System.Drawing.Point(470, 26);

this.time_lab.Margin = new System.Windows.Forms.Padding(2, 0, 2, 0);

this.time_lab.Name = "time_lab";

this.time_lab.Size = new System.Drawing.Size(0, 12);

this.time_lab.TabIndex = 18;

// Form1

this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 12F);

this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;

this.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("$this.BackgroundImage")));

this.BackgroundImageLayout = System.Windows.Forms.ImageLayout.Stretch;

this.ClientSize = new System.Drawing.Size(776, 374);

this.Controls.Add(this.time_lab);

this.Controls.Add(this.shou_box);

this.Controls.Add(this.sum_lab);

this.Controls.Add(this.label1);

this.Controls.Add(this.zidong_btn);

this.Controls.Add(this.recovery_btn);

this.Controls.Add(this.down_btn);

this.Controls.Add(this.up_btn);

this.Controls.Add(this.groupBox7);

this.Controls.Add(this.groupBox6);

this.Controls.Add(this.groupBox5);

this.Controls.Add(this.groupBox4);

this.Controls.Add(this.groupBox3);

this.Controls.Add(this.search_btn);

this.Controls.Add(this.time_btn);

this.Controls.Add(this.groupBox1);

this.Font = new System.Drawing.Font("宋体", 9F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134)));

this.Margin = new System.Windows.Forms.Padding(2);

this.Name = "Form1";

this.Text = "滑块问题求解系统1.0 人工智能实验";

this.Load += new System.EventHandler(this.Form1_Load);

this.groupBox1.ResumeLayout(false);

this.groupBox1.PerformLayout();

this.groupBox3.ResumeLayout(false);

this.groupBox4.ResumeLayout(false);

this.groupBox5.ResumeLayout(false);

this.groupBox5.PerformLayout();

this.groupBox6.ResumeLayout(false);

this.groupBox6.PerformLayout();

this.groupBox7.ResumeLayout(false);

this.groupBox7.PerformLayout();

this.ResumeLayout(false);

this.PerformLayout();

}

#endregion

private System.Windows.Forms.GroupBox groupBox1;

private System.Windows.Forms.RadioButton a1_rad;

private System.Windows.Forms.RadioButton a_rad;

private System.Windows.Forms.RadioButton bfs_rad;

private System.Windows.Forms.RadioButton dfs_rad;

private System.Windows.Forms.Button time_btn;

private System.Windows.Forms.Button search_btn;

private System.Windows.Forms.GroupBox groupBox3;

private System.Windows.Forms.GroupBox groupBox4;

private System.Windows.Forms.TextBox des_txt;

private System.Windows.Forms.TextBox ans_txt;

private System.Windows.Forms.GroupBox groupBox5;

private System.Windows.Forms.Button s3_btn;

private System.Windows.Forms.Button s2_btn;

private System.Windows.Forms.Button s1_btn;

private System.Windows.Forms.GroupBox groupBox6;

private System.Windows.Forms.Button s9_btn;

private System.Windows.Forms.Button s8_btn;

private System.Windows.Forms.Button s7_btn;

private System.Windows.Forms.Button s6_btn;

private System.Windows.Forms.Button s5_btn;

private System.Windows.Forms.Button s4_btn;

private System.Windows.Forms.Button n9_btn;

private System.Windows.Forms.Button n8_btn;

private System.Windows.Forms.Button n7_btn;

private System.Windows.Forms.Button n6_btn;

private System.Windows.Forms.Button n5_btn;

private System.Windows.Forms.Button n4_btn;

private System.Windows.Forms.Button n3_btn;

private System.Windows.Forms.Button n2_btn;

private System.Windows.Forms.Button n1_btn;

private System.Windows.Forms.GroupBox groupBox7;

private System.Windows.Forms.Button rand_btn;

private System.Windows.Forms.Button moren_btn;

private System.Windows.Forms.CheckBox check_box;

private System.Windows.Forms.CheckBox jie_box;

private System.Windows.Forms.CheckBox chu_box;

private System.Windows.Forms.Button up_btn;

private System.Windows.Forms.Button down_btn;

private System.Windows.Forms.Button recovery_btn;

private System.Windows.Forms.Button zidong_btn;

private System.Windows.Forms.Label label1;

private System.Windows.Forms.Label sum_lab;

private System.Windows.Forms.CheckBox shou_box;

private System.Windows.Forms.Label time_lab;

}

10、应用程序的主入口

using System;

using System.Collections.Generic;

using System.Windows.Forms;

//21

namespace YYYSEN

{

static class Program

{

/// <summary>

/// 应用程序的主入口点。

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new Form1());

}

11、完成界面与功能的调用

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

using System.Collections;

using RAND;

using Common;

//290

namespace YYYSEN

{

public partial class Form1 : Form

{

private Image []img = new Image[10];

//当前值

private int[] SS = {9,8,7,6,5,4,3,2,1};

private int[] NN = { 8, 7, 9,6, 5, 4, 3, 2, 1 };

private int[] mos = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

private int[] mon = { 8, 7, 9, 6, 5, 4, 3, 2, 1 };

private string[] str = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "" };

private int[] sss = new int[9];

private int[] nnn = new int[9];

private Dfs ansdfs;

private Ase ansase ;

private Bfs ansbfs;

private Bse ansbse;

private int count;

//private int sum = 0;

ArrayList map = new ArrayList();

public Form1()

{

InitializeComponent();

}

private void Form1_Load(object sender, EventArgs e)

{

S_show();

N_show();

}

private void S_show()

{

s1_btn.Text = str[SS[0]];

s2_btn.Text = str[SS[1]];

s3_btn.Text = str[SS[2]];

s4_btn.Text = str[SS[3]];

s5_btn.Text = str[SS[4]];

s6_btn.Text = str[SS[5]];

s7_btn.Text = str[SS[6]];

s8_btn.Text = str[SS[7]];

s9_btn.Text = str[SS[8]];

}

private void N_show()

{

n1_btn.Text = str[NN[0]];

n2_btn.Text = str[NN[1]];

n3_btn.Text = str[NN[2]];

n4_btn.Text = str[NN[3]];

n5_btn.Text = str[NN[4]];

n6_btn.Text = str[NN[5]];

n7_btn.Text = str[NN[6]];

n8_btn.Text = str[NN[7]];

n9_btn.Text = str[NN[8]];

}

private void rand_btn_Click(object sender, EventArgs e)

{

sum_lab.Text = "0";

if (chu_box.Checked)

{

SS = common .gets();

}

if (jie_box.Checked)

{

NN =common .getn();

}

if (check_box.Checked)

{

while (!common.check(SS, NN, SS.Length))

{

if(chu_box .Checked )

SS = common.gets();

int time=100000;

while (time--!=0) ;

if(jie_box .Checked )

NN = common.gets();

}

S_show();

N_show();

}

private void search_btn_Click(object sender, EventArgs e)

{

SS.CopyTo(sss, 0);

//深度优先搜索；

if (dfs_rad.Checked)

{

ansdfs = new Dfs(SS, NN);

if (ansdfs.BOOL)

{

try

{

ansdfs.search();

map.Clear();

copy(ansdfs.map, map);

sss = common.changeint(map[0] as string);

ans_txt.Text = "搜索结果为：用DFS共需要" + map.Count + "步";

}

catch

{

ans_txt.Text = "搜索结果为：步骤太多，爆栈!";

}

else

{

ans_txt.Text = "搜索结果为：无解";

}

else

if (a_rad.Checked)

{

ansase = new Ase(SS, NN);

if (ansase.BOOL)

{

try

{

ansase.search();

map.Clear();

copy(ansase.map, map);

sss = common.changeint(map[0] as string);

ans_txt.Text = "搜索结果为：用启发式搜索A算法共需要" + map.Count + "步";

}

catch

{

ans_txt.Text = "搜索结果为：步骤太多，爆栈!";

}

else

{

ans_txt.Text = "搜索结果为：无解!";

}

else

if (bfs_rad.Checked)

{

ansbfs = new Bfs(SS, NN);

if (ansbfs.BOOL)

{

try

{

ansbfs.search();

map.Clear();

copy(ansbfs.map, map);

sss = common.changeint(map[0] as string);

ans_txt.Text = "搜索结果为：用BFS共需要" + map.Count + "步";

}

catch

{

ans_txt.Text = "搜索结果为：步骤太多，爆栈!";

}

else

{

ans_txt.Text = "搜索结果为：无解!";

}

else

if (a1_rad.Checked)

{

ansbse = new Bse(SS, NN);

if (ansbse.BOOL)

{

try

{

ansbse.search();

map.Clear();

copy(ansbse.map, map);

sss = common.changeint(map[0] as string);

ans_txt.Text = "搜索结果为：用启发式搜索A*共需要" + map.Count + "步";

}

catch

{

ans_txt.Text = "搜索结果为：步骤太多，爆栈!";

}

else

{

ans_txt.Text = "搜索结果为：无解!";

}

private void down_btn_Click(object sender, EventArgs e)

{

if (shou_box.Checked)

{

count = Convert.ToInt32(sum_lab.Text);

count++;

if (count >=map .Count )

{

MessageBox.Show("完成");

return;

}

string s = map[count] as string;

if (s != null)

{

sum_lab.Text = Convert.ToString(count);

SS= common.changeint(s);

S_show();

}

private void up_btn_Click(object sender, EventArgs e)

{

if (shou_box.Checked)

{

count--;

if (count <0)

{

MessageBox.Show("已是第0步了!");

return;

}

string s = map[count] as string;

if (s != null)

{

sum_lab.Text = Convert.ToString(count);

SS = common.changeint(s);

S_show();

}

private void recovery_btn_Click(object sender, EventArgs e)

{

count = 0;

sum_lab.Text = "0";

sss.CopyTo(SS, 0);

S_show();

}

private void copy(ArrayList a_1, ArrayList a_2)

{

int i = 0;

for (i = 0; i < a_1.Count; i++)

{

a_2.Add(a_1[i]);

}

private void moren_btn_Click(object sender, EventArgs e)

{

sum_lab.Text = "0";

mos.CopyTo(SS, 0);

mon.CopyTo(NN, 0);

S_show();

N_show();

}

private void dfs_rad_Click(object sender, EventArgs e)

{

des_txt .Text ="定义:首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。";

}

private void bfs_rad_CheckedChanged(object sender, EventArgs e)

{

des_txt.Text = "定义:以接近起始节点的程度为依据，进行逐层扩展的节点搜索方法。特点:搜索是逐层进行的，即在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。一种高代价搜索，但若有解存在，则必能找到它。";

}

private void a1_rad_CheckedChanged(object sender, EventArgs e)

{

des_txt.Text = "定义(可采纳性)：如果一个估价函数可以找出最短的路径，我们称之该估价函数具有可采纳性。A*算法是一个可采纳的最好优先算法。";

}

private void a_rad_CheckedChanged(object sender, EventArgs e)

{

des_txt.Text = "定义估价函数(evaluation function),估算节点希望程度的量度.一个节点的“希望”(promise)有几种定义方法。一种方法是估算此节点到目标节点的距离;另一种方法认为,解答路径包括被估价过的节点,并计算全条路径的长度或难度.每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性,或者对给定节点与目标节点进行比较,以决定相关特性。表示方法f(n) — 表示节点n的估价函数值";

}

相关推荐

人工智能实验报告

专栏推荐