实验一 A*算法求解8数码问题

一、实验目的

熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。

二、实验原理

A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且hn≤h*n , h*n 为n节点到目的结点的最优路径的代价。

图2.1 八数码问题的求解
八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。如下图2.1表示了一个具体的八数码问题求解。

三、实验结果

表3.1 不同启发函数h(n)求解8数码问题的结果比较

	启发函数h(n)
	不在位数	将牌“不在位”的距离和	0
初始状态	283604175	283604175	283604175
目标状态	123804765	123804765	123804765
最优解	最佳路径长度为：8 最佳路径为：第1层的状态： 2 8 3 0 6 4 1 7 5 第2层的状态： 2 8 3 1 6 4 0 7 5 第3层的状态： 2 8 3 1 6 4 7 0 5 第4层的状态： 2 8 3 1 0 4 7 6 5 第5层的状态： 2 0 3 1 8 4 7 6 5 第6层的状态： 0 2 3 1 8 4 7 6 5 第7层的状态： 1 2 3 0 8 4 7 6 5 第8层的状态： 1 2 3 8 0 4 7 6 5	最佳路径长度为：8 最佳路径为：第1层的状态： 2 8 3 0 6 4 1 7 5 第2层的状态： 2 8 3 1 6 4 0 7 5 第3层的状态： 2 8 3 1 6 4 7 0 5 第4层的状态： 2 8 3 1 0 4 7 6 5 第5层的状态： 2 0 3 1 8 4 7 6 5 第6层的状态： 0 2 3 1 8 4 7 6 5 第7层的状态： 1 2 3 0 8 4 7 6 5 第8层的状态： 1 2 3 8 0 4 7 6 5	最佳路径长度为：8 最佳路径为：第1层的状态： 2 8 3 0 6 4 1 7 5 第2层的状态： 2 8 3 1 6 4 0 7 5 第3层的状态： 2 8 3 1 6 4 7 0 5 第4层的状态： 2 8 3 1 0 4 7 6 5 第5层的状态： 2 0 3 1 8 4 7 6 5 第6层的状态： 0 2 3 1 8 4 7 6 5 第7层的状态： 1 2 3 0 8 4 7 6 5 第8层的状态： 1 2 3 8 0 4 7 6 5
扩展节点数（不包括叶子节点）	17	8	294
生成节点数（包含叶子节点）	33	17	470
运行时间（迭代次数）	220.00ms	120.00ms	1469.00ms

四、实验总结

1、画出A*算法求解N数码问题的流程图。

根据A*算法的实验原理，f=g(n) +h(n) ；这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行, 因此f是根据需要找到一条最小代价路径的观点来估算节点的。设计A*算法的流程图如图4.1.1所示，按照流程图编写伪代码，进而编写完整的程序。其中OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。在扩展结点时，还需要考虑两个表即OPEN表和CLOSED表中是否存在了该节点的后继节点。具体编程思路参照算法4.1。

图4.1.1 A*算法求解八数码问题的流程图

算法4.1

将起始点加入open表

当open表不为空时：

寻找open表中f值最小的点current

它是终止点，则找到结果，程序结束。

否则，Open表移出current，对current表中的每一个临近点

若它不可走或在close表中，略过

若它不在open表中，加入。

若它在open表中，计算g值，若g值更小，替换其父节点为current，更新

它的g值。

若open表为空，则路径不存在。

2、分析不同的估价函数对A*算法性能的影响。

对于同一问题启发函数h(n)可以有多种设计方法。在本次时实验中，通过选用“将牌不在位数”和“将牌‘不在位’的距离和”两种不同的启发函数，同时还编写了不考虑h值进行搜索，即不采用启发性搜索的算法（按照广度优先搜索的策略）。正如表3.1所示，我们通过将第一种和第二种启发函数对比，发现第二种启发函数优于第一种启发函数，将采用启发函数与不采用启发性函数对比发现，采用启发性函数远远优于不采用启发性函数。

下面，以图4.2.2为例，分析第二种启发函数求解的过程。第二种启发函数为h(n)=将牌‘不在位’的距离和，初始时的值为6,将牌1：2，将牌2：1，将牌6：2，将牌7：1，将牌8:2。在实验结果演示（表3.1）时，并没有选取图4.3初始状态来比较不同启发函数以及不采用启发函数对求解效率的影响，而是选取了图4.2.1初始状态进行演示，因为图4.2.2的步骤较为复杂，对于不同启发函数对于实验结果和实验效率的影响较为明显。第三种启发函数是按照广度优先搜索的策略。

图4.2.1 初始状态 图4.2.2 A*算法求解八数码示意图

3、根据宽度优先搜索算法和A*算法求解八数码问题的结果，分析启发式搜索的特点。

根据表3-1的结果，我们可以发现采用A*算法求解八数码问题时间以及搜索的节点数目远远小于采用宽度优先搜索算法，这说明对于八数码问题，选用的启发性信息有利于搜索效率的提高。但是理论上来讲，如果选用的启发性信息过强，则可能找不到最优解。

4、实验心得体会

当时面对300行的代码时，不知从何处下手，通过查阅资料和请教老师，以及与同学深入探讨，仔细研究A*算法之后，才明白程序如何编写，各部分的函数如何构成。同时，通过本次实验，发现选用不同的启发函数，对于实验的结果有较大的影响。正如表3-1所示，选用第一或第二种（也就是采用A*算法）远远优于普通的广度优先搜索，同时，明显的感觉到第二种启发函数效率更高，更快的找到最优解。但是，在实验过程中，也遇到了一些问题，比如初始值的八数码初始值的选择对于实验结果的影响很大，在选取一些样例时，比如1,3,0,2,8,4,7,6,5，实验结果达到20000次依然没有停止，无法比较两种启发函数的优越性，鉴于时间原因，选取一些迭代次数较小就可以达到目标状态的样例进行验证，发现第二种结果优于第一种启发函数的结果。总的来说，实践出真知，只有把书上的理论知识运用到实践，才是真正地掌握。本次实验顺利完成，还是挺开心的。

附录代码

#include "iostream"  
#include "stdlib.h"  
#include "conio.h"  
#include <math.h>
#include <windows.h>
#define size 3  
using namespace std;  
//定义二维数组来存储数据表示某一个特定状态  
typedef int status[size][size];  
struct SpringLink;  
  
//定义状态图中的结点数据结构  
typedef struct Node  
{  
    status data;//结点所存储的状态 ，一个3*3矩阵 
    struct Node *parent;//指向结点的父亲结点  
    struct SpringLink *child;//指向结点的后继结点  
    struct Node *next;//指向open或者closed表中的后一个结点  
    int fvalue;//结点的总的路径  
    int gvalue;//结点的实际路径  
    int hvalue;//结点的到达目标的困难程度  
}NNode , *PNode;  
  
  
//定义存储指向结点后继结点的指针的地址  
typedef struct SpringLink  
{  
    struct Node *pointData;//指向结点的指针  
    struct SpringLink *next;//指向兄第结点  
}SPLink , *PSPLink;  
  
  
PNode open;  
PNode closed;  
//OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点
  
//开始状态与目标状态  
/*
status startt = {1,3,0,8,2,4,7,6,5};最佳路径为2   
status startt = {1,3,0,2,8,4,7,6,5};迭代超过20000次，手动停止 
status startt = {2,8,3,1,6,4,7,0,5}; 
status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
*/ 
int t=0; //迭代次数,相当于运行时间 
int count_extendnode=0;//扩展结点 
int count_sumnode=0; //生成节点 
status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
status target = {1,2,3,8,0,4,7,6,5};  
//初始化一个空链表  
void initLink(PNode &Head)  
{  
    Head = (PNode)malloc(sizeof(NNode));  
    Head->next = NULL;  
}  
  
  
//判断链表是否为空  
bool isEmpty(PNode Head)  
{  
    if(Head->next == NULL)  
        return true;  
    else  
        return false;  
}  
  
  
//从链表中拿出一个数据  
void popNode(PNode &Head , PNode &FNode)  
{  
    if(isEmpty(Head))  
    {  
        FNode = NULL;  
        return;  
    }  
    FNode = Head->next;  
    Head->next = Head->next->next;  
    FNode->next = NULL;  
}  
  
  
  
//向结点的最终后继结点链表中添加新的子结点  
void addSpringNode(PNode &Head , PNode newData)  
{  
    PSPLink newNode = (PSPLink)malloc(sizeof(SPLink));  
    newNode->pointData = newData;  
  
    newNode->next = Head->child;  
    Head->child = newNode;  
}  
  
  
//释放状态图中存放结点后继结点地址的空间  
void freeSpringLink(PSPLink &Head)  
{  
    PSPLink tmm;  
  
    while(Head != NULL)  
    {  
        tmm = Head;  
        Head = Head->next;  
        free(tmm);  
    }  
}  
  
  
//释放open表与closed表中的资源  
void freeLink(PNode &Head)  
{  
    PNode tmn;  
  
    tmn = Head;  
    Head = Head->next;  
    free(tmn);  
  
    while(Head != NULL)  
    {  
        //首先释放存放结点后继结点地址的空间  
        freeSpringLink(Head->child);  
        tmn = Head;  
        Head = Head->next;  
        free(tmn);  
    }  
}  
  
  
//向普通链表中添加一个结点  
void addNode(PNode &Head , PNode &newNode)  
{  
    newNode->next = Head->next;  
    Head->next = newNode;  
}  
  
  
//向非递减排列的链表中添加一个结点（已经按照权值进行排序）  
void addAscNode(PNode &Head , PNode &newNode)  
{  
    
    PNode P;  
    PNode Q;  
  
    P = Head->next;  
    Q = Head;  
    while(P != NULL && P->fvalue < newNode->fvalue)  
    {  
        Q = P;  
        P = P->next;  
    }  
    //上面判断好位置之后，下面就是简单的插入了  
    newNode->next = Q->next;  
    Q->next = newNode;  
}  
  
/*
//计算结点的 h 值  f=g+h. 按照不在位的个数进行计算 
int computeHValue(PNode theNode)  
{  
    int num = 0;  
  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            if(theNode->data[i][j] != target[i][j])  
                num++;  
        }  
    }  
    return num;  
}   

//计算结点的 h 值  f=g+h. 按照将牌不在位的距离和进行计算 
int computeHValue(PNode theNode)  
{  
    int num = 0;  
  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            if(theNode->data[i][j] != target[i][j]&&theNode->data[i][j] !=0){
            	for(int ii=0;ii<3;ii++){
            		for(int jj=0;jj<3;jj++){
            			if(theNode->data[i][j] == target[ii][jj]){
            				num+=abs(ii-i)+abs(jj-j);
							break; 
						}
					}
				}
			}
			
        }  
    }  
    return num;  
}  */ 
  
//计算结点的f，g，h值  
void computeAllValue(PNode &theNode , PNode parentNode)  
{  
    if(parentNode == NULL)  
        theNode->gvalue = 0;  
    else  
        theNode->gvalue = parentNode->gvalue + 1;  
  
//    theNode->hvalue = computeHValue(theNode);  
    theNode->hvalue = 0;  
    theNode->fvalue = theNode->gvalue + theNode->hvalue;  
}  
  
  
  
//初始化函数，进行算法初始条件的设置  
void initial()  
{  
    //初始化open以及closed表  
    initLink(open);  
    initLink(closed);  
  
    //初始化起始结点，令初始结点的父节点为空结点  
    PNode NULLNode = NULL;  
    PNode Start = (PNode)malloc(sizeof(NNode));  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            Start->data[i][j] = startt[i][j];  
        }  
    }  
    Start->parent = NULL;  
    Start->child = NULL;  
    Start->next = NULL;  
    computeAllValue(Start , NULLNode);  
  
    //起始结点进入open表	  
    addAscNode(open , Start);  
    
}  
  
  
//将B节点的状态赋值给A结点  
void statusAEB(PNode &ANode , PNode BNode)  
{  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            ANode->data[i][j] = BNode->data[i][j];  
        }  
    }  
}  
  
  
//两个结点是否有相同的状态  
bool hasSameStatus(PNode ANode , PNode BNode)  
{  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            if(ANode->data[i][j] != BNode->data[i][j])  
                return false;  
        }  
    }  
    return true;  
}  
  
  
  
//结点与其祖先结点是否有相同的状态  
bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode)  
{  
    while(AnceNode != NULL)  
    {  
        if(hasSameStatus(OrigiNode , AnceNode))  
            return true;  
        AnceNode = AnceNode->parent;  
    }  
    return false;  
}  
  
  
//取得方格中空的格子的位置  
void getPosition(PNode theNode , int &row , int &col)  
{  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            if(theNode->data[i][j] == 0)  
            {  
                row = i;  
                col = j;  
                return;  
            }  
        }  
    }  
}  
  
  
//交换两个数字的值  
void changeAB(int &A , int &B)  
{  
    int C;  
    C = B;  
    B = A;  
    A = C;  
}  
  
  
//检查相应的状态是否在某一个链表中  
bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode)  
{  
    preNode = theLink;  
    theLink = theLink->next;  
  
    while(theLink != NULL)  
    {  
        if(hasSameStatus(spciNode , theLink))  
        {  
            theNodeLink = theLink;  
            return true;  
        }  
        preNode = theLink;  
        theLink = theLink->next;  
    }  
    return false;  
}  
  
  
  
//产生结点的后继结点(与祖先状态不同)链表  
void SpringLink(PNode theNode , PNode &spring)  
{  
    int row;  
    int col;  
  
    getPosition(theNode , row , col);  
  
    //空的格子右边的格子向左移动  
    if(col != 2)  
    {  
        PNode rlNewNode = (PNode)malloc(sizeof(NNode));  
        statusAEB(rlNewNode , theNode);  
        changeAB(rlNewNode->data[row][col] , rlNewNode->data[row][col + 1]);  
        if(hasAnceSameStatus(rlNewNode , theNode->parent))  
        {  
            free(rlNewNode);//与父辈相同，丢弃本结点  
        }  
        else  
        {  
            rlNewNode->parent = theNode;  
            rlNewNode->child = NULL;  
            rlNewNode->next = NULL;  
            computeAllValue(rlNewNode , theNode);  
            //将本结点加入后继结点链表  
            addNode(spring , rlNewNode);  
        }  
    }  
    //空的格子左边的格子向右移动  
    if(col != 0)  
    {  
        PNode lrNewNode = (PNode)malloc(sizeof(NNode));  
        statusAEB(lrNewNode , theNode);  
        changeAB(lrNewNode->data[row][col] , lrNewNode->data[row][col - 1]);  
        if(hasAnceSameStatus(lrNewNode , theNode->parent))  
        {  
            free(lrNewNode);//与父辈相同，丢弃本结点  
        }  
        else  
        {  
            lrNewNode->parent = theNode;  
            lrNewNode->child = NULL;  
            lrNewNode->next = NULL;  
            computeAllValue(lrNewNode , theNode);  
            //将本结点加入后继结点链表  
            addNode(spring , lrNewNode);  
        }  
    }  
    //空的格子上边的格子向下移动  
    if(row != 0)  
    {  
        PNode udNewNode = (PNode)malloc(sizeof(NNode));  
        statusAEB(udNewNode , theNode);  
        changeAB(udNewNode->data[row][col] , udNewNode->data[row - 1][col]);  
        if(hasAnceSameStatus(udNewNode , theNode->parent))  
        {  
            free(udNewNode);//与父辈相同，丢弃本结点  
        }  
        else  
        {  
            udNewNode->parent = theNode;  
            udNewNode->child = NULL;  
            udNewNode->next = NULL;  
            computeAllValue(udNewNode , theNode);  
            //将本结点加入后继结点链表  
            addNode(spring , udNewNode);  
        }  
    }  
    //空的格子下边的格子向上移动  
    if(row != 2)  
    {  
        PNode duNewNode = (PNode)malloc(sizeof(NNode));  
        statusAEB(duNewNode , theNode);  
        changeAB(duNewNode->data[row][col] , duNewNode->data[row + 1][col]);  
        if(hasAnceSameStatus(duNewNode , theNode->parent))  
        {  
            free(duNewNode);//与父辈相同，丢弃本结点  
        }  
        else  
        {  
            duNewNode->parent = theNode;  
            duNewNode->child = NULL;  
            duNewNode->next = NULL;  
            computeAllValue(duNewNode , theNode);  
            //将本结点加入后继结点链表  
            addNode(spring , duNewNode);  
        }  
    }  
}  
  
  
//输出给定结点的状态  
void outputStatus(PNode stat)  
{  
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            cout << stat->data[i][j] << " ";  
        }  
        cout << endl;  
    }  
}  
  
  
  
//输出最佳的路径  
void outputBestRoad(PNode goal)  
{  
    int deepnum = goal->gvalue;  
  
    if(goal->parent != NULL)  
    {  
        outputBestRoad(goal->parent);  
    }  
    cout << "第" << deepnum-- << "层的状态：" << endl;  
    outputStatus(goal);  
}  
  
  
void AStar()  
{  

    PNode tmpNode;//指向从open表中拿出并放到closed表中的结点的指针  
    PNode spring;//tmpNode的后继结点链  
    PNode tmpLNode;//tmpNode的某一个后继结点  
    PNode tmpChartNode; 
	 
    PNode thePreNode;//指向将要从closed表中移到open表中的结点的前一个结点的指针  
    bool getGoal = false;//标识是否达到目标状态  
    long numcount = 1;//记录从open表中拿出结点的序号  
  	
    initial();//对函数进行初始化  
    initLink(spring);//对后继链表的初始化  
    tmpChartNode = NULL;  
    //Target.data=target;
    	cout<<"1"<<endl;
    PNode Target = (PNode)malloc(sizeof(NNode)); 
    for(int i = 0 ; i < 3 ; i++)  
    {  
        for(int j = 0 ; j < 3 ; j++)  
        {  
            Target->data[i][j] =target[i][j];  
        }  
    }
  	cout<<"1"<<endl;
    cout << "从open表中拿出的结点的状态及相应的值" << endl;
 
    while(!isEmpty(open))  
    {  
    	t++;
        //从open表中拿出f值最小的元素,并将拿出的元素放入closed表中  
        popNode(open , tmpNode); 
        addNode(closed , tmpNode);
		count_extendnode=count_extendnode+1;    
		  
        cout << "第" << numcount++ << "个状态是：" << endl;  
        outputStatus(tmpNode);  
        cout << "其f值为：" << tmpNode->fvalue << endl;  
        cout << "其g值为：" << tmpNode->gvalue << endl;  
        cout << "其h值为：" << tmpNode->hvalue << endl;  
  
  
       /* //如果拿出的元素是目标状态则跳出循环  
        if(computeHValue(tmpNode) == 0)  
        {  count_extendnode=count_extendnode-1;
            getGoal = true;  
            break;  
        }*/ 
		//如果拿出的元素是目标状态则跳出循环  
        if(hasSameStatus(tmpNode,Target)== true)  
        {  count_extendnode=count_extendnode-1;
            getGoal = true;  
            break;  
        }  
  
        //产生当前检测结点的后继(与祖先不同)结点列表，产生的后继结点的parent属性指向当前检测的结点  
        SpringLink(tmpNode , spring);  
  
        //遍历检测结点的后继结点链表  
        while(!isEmpty(spring))  
        {  
            popNode(spring , tmpLNode);  
            //状态在open表中已经存在，thePreNode参数在这里并不起作用  
            if(inLink(tmpLNode , open , tmpChartNode , thePreNode))  
            {  
                addSpringNode(tmpNode , tmpChartNode);  
                if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                {  
                    tmpChartNode->parent = tmpLNode->parent;  
                    tmpChartNode->gvalue = tmpLNode->gvalue;  
                    tmpChartNode->fvalue = tmpLNode->fvalue;  
                }  
                free(tmpLNode);  
            }  
            //状态在closed表中已经存在  
            else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode))  
            {  
                addSpringNode(tmpNode , tmpChartNode);  
                if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                {  
                    PNode commu;  
                    tmpChartNode->parent = tmpLNode->parent;  
                    tmpChartNode->gvalue = tmpLNode->gvalue;  
                    tmpChartNode->fvalue = tmpLNode->fvalue;  
                    freeSpringLink(tmpChartNode->child);  
                    tmpChartNode->child = NULL;  
                    popNode(thePreNode , commu);  
                    addAscNode(open , commu);  
                }  
                free(tmpLNode);  
            }  
            //新的状态即此状态既不在open表中也不在closed表中  
            else  
            {  
                addSpringNode(tmpNode , tmpLNode);  
                addAscNode(open , tmpLNode); 	
				count_sumnode+=1;//生成节点			 
            }  
        }  
    }  
  
    //目标可达的话，输出最佳的路径  
    if(getGoal)  
    {  
        cout << endl;  
        cout << "最佳路径长度为：" << tmpNode->gvalue << endl;
		cout << "最佳路径为：" <<endl;
        outputBestRoad(tmpNode);  
    }  
  
    //释放结点所占的内存  
    freeLink(open);  
    freeLink(closed);  
//    getch();  
}  
  
  
int main()  
{ 	double start = GetTickCount(); 
    AStar();  
    printf("生成节点数目：%d\n",count_sumnode);	
    printf("扩展节点数目：%d\n",count_extendnode); 
    printf("运行时间：%f\n",GetTickCount()-start); 
    return 0;  
}

【人工智能实验】A*算法求解8数码问题

实验一 A*算法求解8数码问题

一、实验目的

二、实验原理

三、实验结果

四、实验总结

附录代码

推荐文章

发表回复

【人工智能实验】A*算法求解8数码问题

实验一 A*算法求解8数码问题

一、实验目的

二、实验原理

三、实验结果

四、实验总结

附录代码

推荐文章

相关推荐

发表回复