**
8 ** ** 数和 ** ** 15 ** ** 数问题
** －、问题描述 ** ** **
8 数或 15 数问题是同一个问题，其就是一个随机排列的 8 个或 15 个数在一个方正格子中移动到达规定的一个目标状态。由于只有一个空格子，故只有在空格附近的棋子可以移动。
** 二、算法描述
F ** 算法选择
此问题需要对所有可能的路径进行穷举，但是由于随着树的高度的加大，其子结点的增加宿舍剧增，所以对所有的子结点进行穷举是不大现实的。而根据当前的状态和目标状态进行对比可以用一个评估函数来评估当前状态的好坏情况。而在这里我们选择 A* 算法来进行求解， A* 算法是一种最好优先的算法。 f'(n) = g'(n) + h'(n) ， f'(n) 是估价函数， g'(n) 是起点到终点的最短路径值，这里就表示树的高度， h'(n) 是 n 到目标的最断路经的启发值，其原理是把当前产生的状态和以前所以的状态的评估函数值进行对比，选择其中最小的评估函数继续进行下一步。这里我选择 h'(n) 的启发值为每个格子到达它的目标位置所需要经过的最少步数。
F ** 算法描述
** 需要说明的几点： ** ** **
1. 用 OpenArr 表示初始节点列表 ( 待扩展，此为一个动态数组 )
2 ． ClosedArr 保存已经访问过的结点
3 ．算法首先需要给出初始状态，由于随机产生的状态并不一定能够走到目标状态，因此这里采用从标准状态往回走产生一个被打乱的随机状态，这样可以保证有解。
** 算法实现：
1. OpenArr 放置初始结点
2. 如果 OpenArr 为空集，则退出并给出失败信号
3. n 取为 OpenArr 的第一个节点，并从 OpenArr 中删除节点 n
4. 如果 n 为目标节点，则退出并给出成功信号
5. 否则，将产生 n 子节点，并对 n 的每个子结点 n’ 进行如下操作：
1 ）如果 n’ 不在 OpenArr 和 ClosedArr 表中，则把 n’ 放入 OpenArr 表中
2 ）否则，如果在 OpenArr 表中，计算评估值，并且如果比表中的评估函数的值小，则更新表中的评估值为当前的值。
3 ）否则，如果在 ClosedArr 表中，计算评估值，并且如果比表中的评估函数的值小，则把表中的评估值更新为当前的值，并把该结点从表中删除，并在 OpenArr 表中加入该结点。
6 、把 n 结点加入 ClosedArr 中
7 、对 OpenArr 进行排序（根据评估函数从小到大），并转到 2 。
** 三、程序设计
算法使用 C ＃语言来实现的。程序主要根据上面提供的广度优先算法的描述来对算法进行实现的。程序共有四个类：
StepNode 类，用来描述产生的各个结点的属性以及方法等
Heuristic_15Num_Search 类，算法实现类
Form1 类，是界面设计的类。
这里分别提供了 8 数和 15 数问题的求解。并显示了所经历过的各个状态转移
以下主要对几个核心算法的程序实现进行说明介绍。
// StepNode 类 以下几个方法主要是控制格子的左右上下的移动
//0 数字上移
private void MoveUp(Position p)
{
if (p.x>=1)
{
StepNode node = new StepNode();
To( this ,node);
Position p1 = new Position(p.x-1,p.y);
AddChild(node,p,p1);
}
}
// 0 数字下移
private void MoveDown(Position p)
{
if (p.x<=text_v.Length-2)
{
StepNode node = new StepNode();
To( this ,node);
Position p1 = new Position(p.x+1,p.y);
AddChild(node,p,p1);
}
}
//0 数字左移
private void MoveLeft(Position p)
{
if (p.y>=1)
{
StepNode node = new StepNode();
To( this ,node);
Position p1 = new Position(p.x,p.y-1);
AddChild(node,p,p1);
}
}
//0 数字右移
private void MoveRight(Position p)
{
if (p.y<=text_v.Length-2)
{
StepNode node = new StepNode();
To( this ,node);
Position p1 = new Position(p.x,p.y+1);
AddChild(node,p,p1);
}
}
// 计算节点的启发函数的值
private void ComputeGeuristicGeneVal()
{
int geneVal = this .Height ;
int g = 0; // 启发因子 每个数据到达标准位置需要走过的最少步数
for ( int i=0;i
1<text_v.length;i++) (="" for="" int="" j="0;j<text_v[0].Length;j++)" p1="GetPosition(text_v[i][j]);" p2="GetPosition(aim[i,j]);" position="" xd="p1.x" {=""> p2.x ? p1.x - p2.x : p2.x - p1.x ;
2
3int yd = p1.y > p2.y ? p1.y - p2.y : p2.y - p1.y ;
4
5g += xd + yd ;
6
7}
8
9}
10
11geneVal += g;
12
13this .Heuristic_Gene = geneVal;
14
15}
16
17** // ** Heuristic_15Num_Search 类 ** **
18
19// 核心算法实现部分
20
21// 循环搜索匹配
22
23private void LoopSearch(StepNode node)
24
25{
26
27while (OpenArr.Count>0)
28
29{
30
31node = (StepNode)OpenArr[0];
32
33OpenArr.Remove(node);
34
35// 如果是目标节点则停止搜索
36
37if (node.IsAim())
38
39{
40
41SetPath(node);
42
43return ;
44
45}
46
47else
48
49{
50
51// 产生子节点。
52
53node.CreateChildren();
54
55// 对每个子节点进行检查
56
57<P class=MsoNormal style="</text_v.length;i++)>