人工智能作业



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

二、A*算法梗概：
1.    OPEN:=(S),F(S):=G(S)+H(S);
2.    LOOP : IF OPEN-() THEN EXIT (FALL);
3.    N:=FIRST (OPEN);
4.    IF GOAL(N) THEN EXIT (SUCCESS);
5.    REMOVE (N,OPEN), ADD (N,CLOSED);
6.    EXPAND (N){Mi}, 计算F（N，Mi）=G（N，Mi）+H（Mj）； G（N，M）是通过n到Mi的好散值的估计。ADD （Mj，OPEN），标记Mj到n的指针。IF  F（N，Mk）〈F（Mk） THEN  F（Mk）：=F（N，Mk），标记Mk到n的指针；比较F（N，Mk）和F（Mk），F（Mk）是扩展前计算的耗散值。IF F（N，Ml）〈F（Ml） THEN F（Ml）：=F（N，Ml），标记Ml到n的指针ADD （Ml，OPEN）； 把Ml重新放回OPEN中，不必考虑修改到其中结点的指针。
7.    OPEN 中的结点按F值从大到小排序；
8.    GO LOOP；
调用函数说明：
1、
void AddClosed(struct Gather  *des)
des为struct Gather *类型的结点；
该函数的功能是将des结点加到CLOSED集合中，无返回值。
2、
void PartInit_Point(void)
无行参，无返回值。
该函数的功能是初始化Point P[]中的部分成员。
3、
void AddOpen(struct Point des)
行参为struct Point 类型，可以直接将P[i]作行参。
该函数的功能是将点des加到OPEN集合中。
4、
bool Goal(struct Gather *n)
行参为struct Gather *类型, 返回值为bool型。
该函数的功能是判断n是不是目标结点。是返回TRUE, 否返回FALSE;
５、
bool IsOpenEmpty(void)
返回值为bool型。OPEN集合为空，返回TRUE, 否则返回FALSE;
６、
void Remove(struct Gather *des)
des为struct Gather *类型的结点；
该函数的功能是将des从OPEN集合中删除。
７、
struct Gather *First(void)
返回struct Gather *类型的结点；
该函数的功能是取OPEN集合中存储的第一个有效结点。创建OPEN集合时，头结点未存有效结点。
８、
int InOPENorCLOSED(struct Point R)
返回值为int型，行参为struct Point类型。用法InOPENorCLOSED(P[i])
该函数的功能是判断点R在OPEN集合，或者CLOSED集合，或者都不在
在OPEN中，返回0
在CLOSED中，返回1
俱不在，返回2
9、
void Expand(struct Gather *curr)
无返回值，行参为struct Point类型
该函数的功能是扩展当前结点curr。
10、
void DrawMap(void)
画个草图。

三、源程序：
// 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;
}