316.cpp

程序目的： 通过编制迷宫程序来熟练掌握A*算法。充分理解A*算法和启发函数的关系。

// C++编写， Visual Studio 6.0调试成功
#include <iostream>
using namespace std;
const int PointNum = 16; //迷宫点的总数
const int SideNum  = 18; //迷宫边的总数

struct Point
{
    int    x;        //横坐标
    int    y;        //纵坐标
    int    F;        //评价函数值
    int    H;        //当前点到目标点的横截距与纵截距之和
    int    D;        //深度
    int    index;    //点的编号
    int    pre;        //保存路径，作标志指针之用
};

struct Index
{
    int    from;        //边的起点
    int    to;            //边的终点   注：由于是无向图，from，to既是起点又是终点。
};

struct Gather
{
    struct Point     pnode;
    struct Gather    *next;
};

//存储点的信息 共PointNum个点
struct Point P[PointNum] = {
    {1,1,0,0,0,0, -1}, {1,2,0,0,0,1 ,-2}, {1,3,0,0,0,2 ,-2}, {1,4,0,0,0,3 ,-2},
    {2,1,0,0,0,4 ,-2}, {2,2,0,0,0,5 ,-2}, {2,3,0,0,0,6 ,-2}, {2,4,0,0,0,7 ,-2}, 
    {3,1,0,0,0,8 ,-2}, {3,2,0,0,0,9 ,-2}, {3,3,0,0,0,10,-2}, {3,4,0,0,0,11,-2}, 
    {4,1,0,0,0,12,-2}, {4,2,0,0,0,13,-2}, {4,3,0,0,0,14,-2}, {4,4,0,0,0,15,-2}
};

//存储边的信息 共SideNum个边
struct Index In[SideNum] = {
    {0, 1 }, {1, 2 }, {2, 6 }, {3, 7 }, {4 , 5 }, {4 , 8}, {5 , 6}, {5 ,9 },
    {6, 7 }, {7, 11}, {8, 9 }, {8, 12}, {9 , 10}, {10,11}, {10,14}, {12,13},
    {13,14}, {14,15}
};

//OPEN, CLOSED集合中头结点不存数据，且设OPEN, CLOSED为指针类型的常量
//确保OPEN, CLOSED两全局指针不被意外修改。
struct    Gather *const OPEN   = new struct Gather;
struct    Gather *const CLOSED = new struct Gather;

//将结点加到CLOSED集合中
void    AddClosed(struct Gather *des)
{    
    des->next = CLOSED->next;
    CLOSED->next = des;
}

//部分初始化    
void    PartInit_Point(void)
{
    for (int i=0; i<PointNum; i++){
        P[i].H = (4 - P[i].x) + (4 - P[i].y);
    }
    P[0].D = 0;
    P[0].F = P[0].H + P[0].D;
    OPEN->next = NULL;
    CLOSED->next = NULL;
}

//将点加到OPEN集合中，插入，确保OPEN集合中的点是按照F值由小到大排序的
void    AddOpen(struct Point des)
{
    struct Gather    *q = OPEN, 
                *r = NULL, 
                *temp = new struct Gather;
    temp->pnode = des;

    while ((q->next != NULL) && (q->next->pnode.F < des.F)){
        q = q->next;
    }
    r = q->next;        
    temp->next = r;
    q->next = temp;    
}

/////////////////////////////////////////////////////////////////////////
//判断是否到达终点, 到达则返回 True
bool    Goal(struct Gather *n) 
{
    if (n->pnode.index == 15) //该迷宫(课本)的目标结点编号是15[自定义]
        return true;
    else
        return false;
}


//判断Open集合是不是为空， 空则返回 True
bool    IsOpenEmpty(void)
{
    if (OPEN->next == NULL) 
        return true;
    else
        return false;
}

//将des结点从OPEN集合中删除
void    Remove(struct Gather *des)
{
    struct  Gather *p = OPEN, *q = NULL;
    while ((p->next!=NULL) && (p->next->pnode.index!=des->pnode.index)){
        p = p->next;
    }
    if (p->next == NULL) 
        cout << "Error occurs when delete node from Open!" << endl;
    else
    {
        q = p->next;
        p->next = q->next;
    }
}

//取OPEN集合中存的第一个结点 [ 注意：OPEN头结点未存数据 ]
struct Gather  *First(void)
{
    return    OPEN->next;
}

//判断点R在OPEN,CLOSED集合中，还是都不在
int    InOPENorCLOSED(struct Point R)
{
    for (struct Gather *p = OPEN; p->next!=NULL; p = p->next){
            if (p->next->pnode.index == R.index) return 0;//在OPEN中                    
        }
    for (p = CLOSED; p->next!=NULL ;p = p->next){
            if (p->next->pnode.index == R.index) return 1;//在CLOSED中                    
        }
    return  2; //都不在
}

//扩展结点遇到的三种情况处理
void  Process(struct Point *A, struct Gather *curr)
{
    (*A).D++;
    (*A).F = (*A).D + (*A).H;
    if (InOPENorCLOSED(*A) == 2)  //如果A不在OPEN,CLOSED集合中
    { 
        AddOpen(*A);  //将A加到OPEN集合中                    
        (*A).pre = curr->pnode.index;  //标志指针（游标）                                  
    }
    if (InOPENorCLOSED(*A) == 0)  //如果A在OPEN集合中
    {
        struct    Gather *r = OPEN;
        while ((r->next != NULL) && (r->next->pnode.index != (*A).index))
        {
            r = r->next;
        }
        if ((*A).F < r->next->pnode.F)
        {
            r->next->pnode.F = (*A).F;  //修改OPEN集合中结点A的F值
            (*A).pre = curr->pnode.index;  //标志指针（游标）    
        }
    }
    if (InOPENorCLOSED(*A) == 1)  //如果A在CLOSED集合中
    {
        struct    Gather *r = CLOSED;
        while ((r->next != NULL) && (r->next->pnode.index != (*A).index))
        {
            r = r->next;
        }
        if ((*A).F < r->next->pnode.F)
        {
            (*A).pre = curr->pnode.index;  //标志指针（游标）    
            AddOpen(*A);  //将A重新放到OPEN集合中
        }
    }            
}

//扩展当前结点curr
void    Expand(struct Gather *curr)
{
    for (int i=0; i<SideNum; i++)
    {
        if (In[i].from == curr->pnode.index)
        {
            int    t = In[i].to;            
            Process(&P[t], curr);            
        }
        //由于是无向图，可以由点from扩展到点to; 同样可以由点to扩展到点from
        if (In[i].to == curr->pnode.index)
        {
            int    t = In[i].from;
            Process(&P[t], curr);        
        }
    }//end for
}

//画课本上的迷宫图
void    DrawMap(void)
{
    cout    << "The labyrinth is : " << endl << endl;
    cout    << "     _______________@" << endl
            << "          |    |    |" << endl
            << "     _____|    |____|" << endl
            << "     |    |    |    |" << endl
            << "     |    |____|    |" << endl
            << "     |    |    |    |" << endl
            << "    .|    |____|____|" << endl
            << endl;
}

void main()
{
    DrawMap();
    PartInit_Point();    
    struct Gather  *n = new struct Gather;    
    AddOpen(P[0]);    
LOOP:
    if (IsOpenEmpty()){
        cout << "Fail for Open is Null!" << endl;
        exit(0);
    }
    n = First();    
    if (Goal(n)){
        cout << "Succeed! The shortest route is: " <<endl<<endl;        
        int  i = n->pnode.index;
        do  {
            cout << "(" << P[i].x << "," << P[i].y << ")" << "   ";
            i = P[i].pre;
        }while (P[i].pre != -1);
        cout << "(" << P[i].x << ", " << P[i].y << ")" << endl;
        exit(1);
    }    
    Remove(n);
    AddClosed(n);
    Expand(n);
    goto    LOOP;
}