8 数码问题-S201307154

基于A星算法解决8数码问题的编程实现 1.问题描述 8 数码问题又称9 宫问题与游戏“华容道”类似。意在给定3*3棋格的8个格子内分别放一个符号.符号之间互不相同,余下的一格为空格。并且通常把8 个符号在棋格上的排列顺序称作8 数码的状态。开始时规则给定一个初始状态和一个目标状态并要求被试者对棋格内的符号经过若干次移动由初始状态达到目标状态这个过程中只有空格附近的符号可以朝空格的方向移动且每次只能移动一个符号。 为方便编程和表示,本文中8 个格子内的符号分别取1—8的8 个数字表示.空格用0 表示.并给定8数码的初始状态和和目标状态分别如图1,2所示。

图1 初始状态 图二 目标状态 则要求以图1 为初始状态.通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图2 所示目标状态。

2.算法设计

2.1启发式图搜索过程* 核心思想：利用所处理问题的启发信息引导搜索 目的：减少搜索范围，降低问题复杂度. 启发式图搜索算法 A 基本思路：定义一个评价函数 f，对当前待搜索状态进行评估（既考虑从起始节点到节点 n 的花费，又考虑从节点 n 到达目标节点的费用），然后找出一个最有希望的节点来扩展. 函数形式为：f (n)= g (n)+ h (n) . n 为被评价的节点。 用此函数值来排列 OPEN 表中节点顺序的图搜索算法称为 A 算法. 函数符号说明： g*(n)、h*(n)：表示各部分实际最短路径的耗散值. f*(n) = g*(n) + h*(n)：表示从S出发，通过节点n到目标节点 g 的最短路径的耗散值. f (n)、g (n) 和 h (n) 为相应路径耗散值的估计值，是一种预测。 A 算法就是利用这种预测，来达到有效搜索的目的. g（n）可根据搜索历史情况对 g*（n）作出估计，显然有 g（n）>= g*（n）. h（n）则依赖于启发信息，通常称为启发函数，是要对未来扩展的方向作出估计. 算法的伪代码如下： 1. OPEN:=(s)，f(s):=g(s)+h(s); 2. LOOP: IF OPEN=( ) THEN EXIT(FAIL);

3 8 2 1 0 5 7 6 4

1 0 2

8 4 3 7 6 5 3. n:=FIRST(OPEN); 4. IF GOAL (n) THEN EXIT(SUCCESS); 5. REMOVE (n, OPEN), ADD(n, CLOSED); 6. EXPAND(n)→ (mi)，把mi作为n的后继节点添入G，并计算 f(n-mi)=g(n-mi)+h(mi)； ADD (mj, OPEN)，  IF f(n-mk) < f(mk) THEN f(mk):=f(n-mk)，  IF f(n-ml) < f(ml) THEN f(ml):=f(n-ml)， ADD(ml,OPEN); 7. OPEN 中的节点按 f 值从小到大排序; 8. GO LOOP; 算法的说明： A 算法由一般的图搜索算法改变而成.算法的控制策略是按照 f（n）值递增的顺序对 OPEN 中的元素进行排序，f（n）值小的节点排在前面，大的放在 OPEN 表的后面. 每次扩展节点时，优先选择当前 f（n）值最小的节点来扩展.

2.2八数码问题具体事例

根据任务要求，本文采用A*算法.根据上面A*算法的原理，应该设计合适

的启发函数，已经合适的存储结构，以提高效率。

2.2.1存储结构选择

在A*算法中需要用到open表和close表，在A*算法中open表中的结点有

严格的顺序，即应按是一个按照f(n)的严格的递增的有序序列，又因为每个结点都要记录当前的状态，以及方便查找到下一个结点，因此我们使用结构体表示问题的状态，同时因为open和close均是一个线性表，而且要便于删除和插入，从而选择链表作为存储结构。

2.2.2结构体中成员变量的选择

因为8数码是用一个3*3的数组表示的，所以这里我们在结构体变量中需

要有一个 Cur_S[3][3]，来保存当前8数码的状态。为了保证在搜索到目标状态后能够顺利复现寻优路径，我们需要定义一个Prior指针指向该解路径上该节点的父节点。同时因为我们在寻找目标结点的过程中需要对open表进行扩展，从而我们还需要用一个指针Next指针指向扩展结点，当然扩展结点的插入要遵循递增的规则。 为提高程序的运行效率，减少程序扩展结点时候的搜索量，我们需要记录0在Cur_S[3][3]中所处的位置，因此我们使用COL，记录当前空格所在的行号，使用ROW记录当前空格所在的列号。 根据A*算法的定义，当前节点的代价值由估价函数给出即f (n)= g (n)+ h (n) ，在8数码问题中，g(n)是表示当前节点n在搜索树中的深度，h(n)是启发函数，因此在结构体中我增加了Depth表示当前结点的深度，InspireInfo启发信息，CurCost表示当前代价值。 因此结构体TNode定义如下： 2.2.3启发函数的选择

在8 数码问题常用的启发函数为“不在位”的数码个数和数码“不在位”

的距离和，在这里，我选择数码“不在位”的距离和作为启发函数。

2.2.4规则库的设计

0 在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进

行移动，主要取决于当前0所处的行列号，为提高效率新节点要与其祖父节点不同，或其父节点为起始节点。在A*算法中没扩展一个新结点都必须是有效子节点，不为有效子节点不能插入到open表中，具体实现见附件代码中的Expand_TNode函数。 //左移 if(p->ROW<=1) //空格所在列号不小于1,可左移 { Temp=p->Prior; if(Temp!=NULL&&Temp->COL==p->COL&&Temp->ROW-1==p->ROW) ; //新节点与其祖父节点相同,无操作 else //新节点与其祖父节点不同或其父节点为起始节点 { .......(扩展新节点并判断是否加入open 表)//详细代码见源程序 } }//end 左移 //右移 if(p->ROW<=1) //空格所在列号不大于1,可右移 { Temp=p->Prior; if(temp!=NULL&&temp->i_0==p->i_0&&Temp->j_0+1==p->j_0) ; //新节点与其祖父节点相同无操作 else //新节点与其祖父节点不同或其父节点为起始节点 { ......(扩展新节点并判断是否加入open 表)//详细代码见源程序 } }//end 右移 //上移 if(p->COL>=1) //空格所在列号不小于1,可上移 { Temp=p->Prior; if(Temp!=NULL&&Temp->COL==p->COL-1&&Temp->ROW==p->ROW) ; //新节点与其祖父节点相同,无操作 else //新节点与其祖父节点不同或其父节点为起始节点 { ......(扩展新节点并判断是否加入open 表)//详细代码见源程序 } }//end 上移 //下移 if(p->COL<=1) //空格所在列号不大于1,可下移 { Temp=p->Prior; if(Temp!=NULL&&Temp->COL==p->COL+1&&Temp->ROW==p->ROW) ; //新节点与其祖父节点相同无操作 else //新节点与其祖父节点不同或其父节点为起始节点 { ......(扩展新节点并判断是否加入open 表)//详细代码见源程序 } }//end 下 2.2.5程序流程

其中扩展节点n的具体步骤如下： 首先判断其是否在closed 表已经出现过, 如果出现过并且新节点的代价值比其小，则应将其从closed 表删除，同时将新节点加入到open表。如果没有出现过则判断其是否已经存在于open 表中待扩展，如果出现过并且新节点的代价值比其小，则应将其从open 表删除同时将新节点加入到open 表，如果没有出现过则说明该节点为一个全新的节点转将该节点加入open 表。 3运行结果： 附件： #include "Stdio.h" #include "Conio.h" #include "stdlib.h" #include "math.h" void Copy_Init_State(struct TNode *q,struct TNode *p); void Cal_Cur_Cost(int deepth,struct TNode *p); void Insert_to_open(struct TNode *p); void Insert_to_closed(struct TNode *p); void Delete_TNode(struct TNode *name,struct TNode *p); int JudgeEqualA_B(struct TNode *p1,struct TNode *p2); struct TNode * Solve_A(struct TNode *p); void Expand_TNode(struct TNode *p); struct TNode * Search_A(struct TNode *name,struct TNode *Temp); void PrintProcessing(struct TNode *p); void InputData(void);

/* 定义8数码的节点状态 */ typedef struct TNode { int Cur_S[3][3]; //当前8数码的状态 int COL; //当前空格所在行号 int ROW; //当前空格所在列号 int CurCost; //当前代价值 int Depth; //当前节点深度 int InspireInfo; //启发信息，采用数码“不在位”距离和 struct TNode *Prior; //指向解路径上该节点的父节点 struct TNode *Next; //指向所在open或closed表中的下一个元素 }; struct TNode *open=NULL; //建立open表指针 struct TNode *closed=NULL; //建立closed表指针 int Sum_TNode=0; //用于记录扩展节点总数 struct TNode Str; struct TNode Dir; int main(void) { struct TNode s,*target; InputData();//输入数据 Copy_Init_State(&Str,&s); //拷贝8数码初始状态，初始化代价值 Cal_Cur_Cost(0,&s); printf("%s","开始计算！"); target=Solve_A(&s); //求解主程序 if(target) PrintProcessing(target); //输出解路径 else printf("问题求解失败！");