migongyuanchengxu.txt

采用Ａ*算法解决了迷宫问题的源程序

#include <iostream>  
using namespace std;  
const int PointNum = 16; //迷宫点的总数  
const int SideNum  = 18; //迷宫边的总数  
vv                                                                                              
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;  
}