人工智能作業



一、    程序目的：
通過編制迷宮程序來熟練掌握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;
}