淺析A*算法：

A*算法是一種靜態(tài)路由中求解最短路最有效的直接搜索方法，同時(shí)也是一種啟發(fā)式搜索。
定義A*的公式為：f(n)=g(n)+h(n)
其中f(n)為初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)的代價(jià)估計(jì)，
g(n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)，
h(n)表示從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的代價(jià)估計(jì)。

積木塊游戲問(wèn)題描述：

移動(dòng)積木塊游戲的初始排列順序是：BBWWE，B表示黑牌，W表示白牌，E表示空格。規(guī)定：任一牌移入相鄰空格，或跳過(guò)一張牌移入空格，耗散值為1;跳過(guò)兩張牌移入空格，耗散為2;不能跳過(guò)3或更多的牌移入空格。目標(biāo)序列為白牌均在黑牌之左，空格位置不計(jì)。

分析：定義f(n)=g(n)+h(n)

其中g(shù)(n)從從初始狀態(tài)到狀態(tài)n的所需的耗散值，
h(n)定義為每個(gè)白塊左邊黑塊個(gè)數(shù)的總和。

項(xiàng)目地址：github/MoveBlock/

源代碼設(shè)計(jì)：

定義數(shù)據(jù)類以及其相應(yīng)的方法：

文件：BlockData.h

class BlockData {
public:
    BlockData(string data,int g);    //構(gòu)造函數(shù)
    string block;           //當(dāng)前數(shù)據(jù)
    int f_value;                    //f值
    int g_value;                    //g值
    int h_value;                    //h值
    int findTime;                   //到當(dāng)前狀態(tài)所需要的搜索次數(shù)，為了計(jì)算性能
    BlockData* parent;              //父節(jié)點(diǎn)指針
    int GetFValue();                //獲取f
    int GetGValue();                //獲取g
    int GetHValue();                //獲取h
    int ePos;                       //空格E的位置
    int GetE();                     //獲取空格E的位置
    bool operator<(const BlockData&bd)const{ return f_value<bd.g_value;}        //重載比較
    bool operator>(BlockData&bd){ return f_value>=bd.g_value;}                  //重載比較
    friend istream & operator >> (istream &in, BlockData &obj);                 //重載輸出
    friend ostream & operator << (ostream &out, BlockData &obj);                //重載輸出
};
//移動(dòng)E函數(shù)
BlockData* Move(BlockData* bd,int movePos);

文件：BlockData.cpp

BlockData::BlockData(string data, int g)
{
    //構(gòu)造并初始化
    this->parent=NULL;
    this->block=data;
    this->ePos=this->GetE();
    g_value = g;
    GetHValue();
    GetFValue();
};

int BlockData::GetFValue() {
    return this->f_value=this->g_value + h_value;
}

int BlockData::GetGValue() {
    return this->g_value;
}

int BlockData::GetHValue() {
    //計(jì)算f，算法是每個(gè)W前的B的總和
    this->h_value=0;
    int bCount=0;
    for(int i=0;i<this->block.size();i++)
    {
        if(this->block[i]=='B')
        {
            bCount++;
        } else if(this->block[i]=='W')
        {
            this->h_value+=bCount;
        }
    }
    return this->h_value;
}

istream & operator>>(istream &in, BlockData &obj)
{
    in>>obj.block;
    return in;
}

ostream & operator << (ostream &out, BlockData &obj)
{
    out<<obj.block<<endl;
}

int BlockData::GetE()
{
    for(int i=0;i<this->block.size();i++)
    {
        if(this->block[i]=='E')
        {
            this->ePos=i;
            return i;
        }
    }
    return -1;
}

BlockData* Move(BlockData* bd,int movePos) {
    //判斷參數(shù)合法性
    if(movePos<-3||movePos>3||movePos==0){
        return NULL;
    }
    int ePos=bd->ePos;
    if(!((ePos+movePos)>=0&&(ePos+movePos)<bd->block.size()))
    {
        return NULL;
    }

    //計(jì)算g
    int g;
    if(abs(movePos)==3)
    {
        g=2;
    } else
    {
        g=1;
    }

    //移動(dòng)E
    string temp;
    temp=bd->block;
    temp[bd->ePos]=temp[bd->ePos+movePos];
    temp[bd->ePos+movePos]='E';
    BlockData* ans=new BlockData(temp,bd->g_value+g);
    ans->parent=bd;
    return ans;
}

啟發(fā)搜索類及其實(shí)現(xiàn)方法：

文件：MoveBlock.h

//用于優(yōu)先隊(duì)列的比較函數(shù)，f值最小的優(yōu)先
struct cmp{
    bool operator()(BlockData* a, BlockData* b){
        return a->f_value>b->f_value;
    }
};

class MoveBlock {
public:
    MoveBlock();        //構(gòu)造函數(shù)
    ~MoveBlock();       //析構(gòu)函數(shù)
    int findTime;       //統(tǒng)計(jì)搜索次數(shù)
    BlockData* firstData;       //初始狀態(tài)
    priority_queue<BlockData*,vector<BlockData*>,cmp> blockQueue;       //優(yōu)先隊(duì)列
    queue<BlockData*>recycleQueue;          //回收隊(duì)列
    map<string,int>searchMap;               //記錄搜索過(guò)的狀態(tài)
    BlockData* Run(string data);            //搜索函數(shù)
    void ShowWay(BlockData* ans);           //回溯路徑
    bool CleanQueue();                      //清除內(nèi)存
    friend istream & operator >> (istream &in, MoveBlock &obj);         //重載輸入輸出
    friend ostream & operator << (ostream &out, MoveBlock &obj);
};

文件：MoveBlock.cpp

MoveBlock::MoveBlock()
:firstData(NULL)
{
}

BlockData* MoveBlock::Run(string data)
{
    findTime=0;
    this->firstData=new BlockData(data,0);

    //將初始狀態(tài)壓入優(yōu)先隊(duì)列
    this->blockQueue.push(this->firstData);
    searchMap.insert(pair<string,int>(this->firstData->block,1));
    while(this->blockQueue.size()>0)
    {
        //取隊(duì)頭元素并壓入回收隊(duì)列
        BlockData* topData=this->blockQueue.top();
        this->blockQueue.pop();
        recycleQueue.push(topData);

        //執(zhí)行移動(dòng)函數(shù)
        int moveOper[]=MOVE_OPER;
        for(int i=0;i<5;i++)
        {
            BlockData* afterOperData=Move(topData,moveOper[i]);
            if(afterOperData==NULL)
            {
                continue;
            }

            //判斷是否已經(jīng)搜索過(guò)
            if(searchMap.find(afterOperData->block)!=searchMap.end())
            {
                delete(afterOperData);
                continue;
            }
            searchMap.insert(pair<string,int>(afterOperData->block,1));

            findTime++;

            //判斷是否找到答案
            if(afterOperData->GetHValue()==0)
            {
                //找到答案將優(yōu)先隊(duì)列的元素壓入回收隊(duì)列
                while (!this->blockQueue.empty())
                {
                    recycleQueue.push(this->blockQueue.top());
                    this->blockQueue.pop();
                }

                //置搜索次數(shù)并返回答案
                afterOperData->findTime=findTime;
                return afterOperData;
            }

            //找不到答案，將當(dāng)前狀態(tài)壓入優(yōu)先隊(duì)列
            this->blockQueue.push(afterOperData);
        }
    }
    return NULL;
}


void MoveBlock::ShowWay(BlockData* ans)
{
    //使用棧回溯找路徑
    stack<BlockData*>backStack;
    backStack.push(ans);
    BlockData* parent=ans->parent;
    while(parent!=NULL)
    {
        backStack.push(parent);
        parent=parent->parent;
    }
    while (!backStack.empty())
    {
        BlockData* backData=backStack.top();
        backStack.pop();
        cout<<backData->block<<endl;
    }
}

istream & operator>>(istream &in, MoveBlock &obj)
{
    if(obj.firstData!=NULL)
    {
        delete(obj.firstData);
    }
    string firstData;
    cout << "請(qǐng)輸入初始值:" << endl;
    in >> firstData;
    obj.firstData=new BlockData(firstData,0);
    return in;
}

ostream & operator << (ostream &out, MoveBlock &obj)
{
    out<<obj.firstData->block<<endl;
}

MoveBlock::~MoveBlock()
{
    this->CleanQueue();
}

bool MoveBlock::CleanQueue()
{
    for(int i=0;i<this->blockQueue.size();i++){
        BlockData* delData=blockQueue.top();
        blockQueue.pop();
        recycleQueue.push(delData);
    }
    for(int i=0;i<recycleQueue.size();i++)
    {
        BlockData* recycleData=recycleQueue.front();
        recycleQueue.pop();
        delete(recycleData);
    }
    return true;
}