POJ---2243 Knight Moves 使用A*算法的廣度優先搜尋

題目連結：http://poj.org/problem?id=2243

啟發式搜尋：啟發式搜尋就是在狀态空間中的搜尋對每一個搜尋的位置進行評估，得到最好的位置，再從這個位置進行搜尋直到目标。這樣可以省略大量無畏的搜尋路徑，提到了效率。在啟發式搜尋中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。

估價函數：從目前節點移動到目标節點的預估費用；這個估計就是啟發式的。在尋路問題和迷宮問題中，我們通常用曼哈頓（manhattan）估價函數（下文有介紹）預估費用。

A*算法與BFS：可以這樣說，BFS是A*算法的一個特例。對于一個BFS算法，從目前節點擴充出來的每一個節點（如果沒有被通路過的話）都要放進隊列進行進一步擴充。也就是說BFS的估計函數h永遠等于0，沒有一點啟發式的資訊，可以認為BFS是“最爛的”A*算法。

選取最小估價：如果學過資料結構的話，應該可以知道，對于每次都要選取最小估價的節點，應該用到最小優先級隊列（也叫最小二叉堆）。在C++的STL裡有現成的資料結構priority_queue，可以直接使用。當然不要忘了重載自定義節點的比較操作符。

A*算法的特點：A*算法在理論上是時間最優的，但是也有缺點：它的空間增長是指數級别的。

啟發函數：f=g+h;其中g是起點到目前結點的直線距離，h是目前結點到目的結點的某種度量函數，在本題中采用曼哈頓距離。

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
struct node{
	int x,y,step;
	int f,g,h;
	bool operator<(const node & n)const { //優先隊列，需要重載操作符 
		return step>n.step;
	}
	
}k;
int endx,endy;
int Heuristic(const node &a){                  //manhattan估價函數
	return (abs(a.x-endx)+abs(a.y-endy))*10;
}
bool isbond(const node &a){                  //判斷是否是邊界 
	if(a.x<0||a.y>=8||a.x>=8||a.y<0)return 1;
	return 0;
}
bool visit[10][10];
int dir[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
priority_queue<node> Q;             //8個方向 
int bfs()
{
	while(!Q.empty())Q.pop();
	Q.push(k);
	node p,q;
	while(!Q.empty())
	{
		p=Q.top();
		Q.pop();
		if(p.x==endx&&p.y==endy){
			return p.step;
		}
		visit[p.x][p.y]=1;
		for(int i=0;i<8;i++)
		{
			q.x=p.x+dir[i][0];
			q.y=p.y+dir[i][1];
			if(visit[q.x][q.y])continue;
			if(isbond(q))continue;
			q.g=p.g+23;
			q.h=Heuristic(q);
			q.step=p.step+1;
			Q.push(q);
		}
	}
	
}
int main()
{
	string a,b;
	while(cin>>a>>b)
	{
		k.x=a[0]-'a';
		k.y=a[1]-'1';
		endx=b[0]-'a';
		endy=b[1]-'1';
		k.step=k.g=0;
		k.h=Heuristic(k);
		k.f=k.g+k.h;
		memset(visit,0,sizeof(visit));
		cout<<"To get from "<<a<<" to "<<b<<" takes ";  
        cout<<bfs()<<" knight moves."<<endl;  
	}
	return 0;
}