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

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

一、实验目的

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

二、实验思路

以8数码问题和15数码问题为例实现A*算法的求解程序（编程语言不限，如Python等），要求设计两种不同的估价函数。

三、实验原理

A算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价以及从节点n到达目标节点的估价代价。
A算法中，若对所有的x存在h(x)≤h*(x),则称h(x)为的下限，表示某种偏于保守的估计。采用的下限h(x)为启发函数的A算法，称为A算法，其中限制：h(x)≤h(x)十分重要，它能保证A算法找到最优解。在本问题中，g(x)相对容易得到，就是从初始节点到当前节点的路径代价，即当前节点在搜索树中的深度。关键在于启发函数h(x)的选择，A算法的搜索效率很大程度上取决于估价函数h(x)。一般而言，满足h(x)≤h*(x)前提下，h(x)的值越大越好，说明其携带的启发性信息越多，A算法搜索时扩展的节点就越少，搜索效率就越高。
传统的BFS是选取当前节点在搜索树中的深度作为g(x)，但没有使用启发函数h(x)，在找到目标状态之前盲目搜索，生成了过多的节点，因此搜索效率相对较低。
本实验分别使用不在位的元素个数和曼哈顿距离作为启发函数h(x)。每次从open表中选取时，优先选取估价函数最小的状态来扩展。
A算法的估价函数可表示为：f’(n) = g’(n) + h’(n)
这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h’(n)是n到目标的最短路经的启发值。由于这个f’(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n)
其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f’(n)的近似，也就是用g(n)代替g’(n)，h(n)代替h’(n)。这样必须满足两个条件：
(1) g(n)>=g’(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。
(2) h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h’(n);第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
具体步骤：从初始状态S_0出发，分别采用不同的操作符作用于生成新的状态x并将其加入open表中（对应到状态空间图中便是根节点生成新的子节点n） ,接着从open表中按照某种限制或策略选择一个状态x使操作符作用于x又生成了新的状态并加入open表中(状态空间图中相应也产生了新的子节点)，如此不断重复直到生成目标状态。
对于以上所述的“某种策略”，在图搜索过程中，若该策略是依据进行排序并选取最小的估价值，则称该过程为A*算法。

四、实验结果

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

五、实验过程

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

2、分析不同的估价函数对A算法性能的影响
对于同一问题启发函数h(n)可以有多种设计方法。在本次时实验中，通过选用“将牌不在位数”和“将牌‘不在位’的距离和”两种不同的启发函数，同时还编写了不考虑h值进行搜索，即不采用启发性搜索的算法（按照广度优先搜索的策略）。正如表1所示，我们通过将第一种和第二种启发函数对比，发现第二种启发函数优于第一种启发函数，将采用启发函数与不采用启发性函数对比发现，采用启发性函数远远优于不采用启发性函数。
下面，以图4.2.2为例，分析第二种启发函数求解的过程。第二种启发函数为h(n)=将牌‘不在位’的距离和，初始时的值为6,将牌1：2，将牌2：1，将牌6：2，将牌7：1，将牌8:2。在实验结果演示（表1）时，并没有选取初始状态来比较不同启发函数以及不采用启发函数对求解效率的影响，而是选取了图2初始状态进行演示，因为图3的步骤较为复杂，对于不同启发函数对于实验结果和实验效率的影响较为明显。第三种启发函数是按照广度优先搜索的策略。


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

六、实验心得体会

第一次接触到A算法，第一次实验课的时候连花两节课去看算法的原理和计算过程，但还是没能充分理解。通过查阅资料，以及与同学深入探讨，仔细研究A算法之后，才明白程序如何编写，各部分的函数如何构成。同时，通过本次实验，发现选用不同的启发函数，对于实验的结果有较大的影响。正如表3-1所示，选用第一或第二种（也就是采用A*算法）远远优于普通的广度优先搜索，同时，明显的感觉到第二种启发函数效率更高，更快的找到最优解。总的来说，实践出真知，只有把书上的理论知识运用到实践，才是真正地掌握。

附录代码：

#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=nullptr;//指向从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;
}