淺析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ù)類(lèi)以及其相應(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ā)搜索類(lèi)及其實(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;
}
