DFS与BFS解决骑士移动问题，以及两者对比。

题目

骑士移动:
时间限制:2000毫秒存储容量极限:65536 KB
你的一个朋友正在研究旅行骑士问题(TKP)在那里你可以找到最短的封闭的骑士移动之旅n棋盘上的方格恰好出现一次。他认为这个问题最困难的部分是确定两个给定方格之间最少的骑士移动次数，一旦你完成了这个，找到旅程就容易了。
你当然知道反之亦然。所以你让他写一个程序来解决“困难”的部分。
你的工作是写一个程序，需要两个方块a和b作为输入，然后确定最短路线上的骑士移动次数a到b.
输入规格
输入文件将包含一个或多个测试用例。每个测试用例由一条线组成，这条线包含由一个空格分隔的两个正方形。方块是由字母(a-h)代表棋盘上的列和数字(1-8)代表棋盘上的行组成的字符串。
输出规格
对于每个测试用例，打印一行说明“从xx到尤尼克斯接受n骑士移动。".
样本值输入
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
抽样输出
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

通俗易懂的讲此题的意思就是求国际象棋里用马从指定坐标走到目的坐标的最少步数

---

一、深度优先搜索（DFS）

由于深度优先搜索的特性，从起点到终点的步数不一定是最小的

因此使用DFS时，应该遍历全路径，取最小值

代码如下：

#include
#include
using namespace std;
int movex[8] = { -2,-1,1,2,2,1,-1,-2 }, movey[8] = { 1,2,2,1,-1,-2,-2,-1 };//马的移动方式
int MIN=100000;
void dfs(int x1,int y1,int x2,int y2,int s,int map[][9])
{
	if(s>=MIN)return;//因为只取最小值，一旦s比MIN大，返回，避免走冤枉路
	if(x1==x2&&y1==y2){
		if(s=1&&x0<=8)&&(y0>=1&&y0<=8)&&(b[x0][y0]==0))
			{
				cout<> str1 >> str2;
		char ch1 = str1[0]-96;
		char ch2 = str1[1]-48;
		char ch3 = str2[0]-96;
		char ch4 = str2[1]-48;
		dfs(ch1, ch2, ch3, ch4, s,a);
		cout<<"min is:"< 
 可以明显感觉到使用dfs遍历全路径的方法是及其低效且抽象的！下面使用BFS广度优先搜索。
 
二、广度优先搜索(BFS) 
由于广度优先搜索的特性，只要从起点搜索到终点，所走的步数必是最短的。
 
因此，使用BFS解决此题只需要遍历棋盘！效率比DFS高很多。
 
#include
#include
using namespace std;
int movex[8] = { -2,-1,1,2,2,1,-1,-2 }, movey[8] = { 1,2,2,1,-1,-2,-2,-1 };
//Point类记录坐标与当前步数
class Point{
	public:
		int x,y;
		int pathN;//将当前步数与坐标绑定
		Point(int xx,int yy,int n):x(xx),y(yy),pathN(n){}
};
int bfs(Point &end,queue &list,int a[][9])
{
	while(!list.empty())
	{
		Point nowVertex(list.front());
		list.pop();
		if(nowVertex.x==end.x&&nowVertex.y==end.y)
		{
			return nowVertex.pathN;
		}else{
			a[nowVertex.x][nowVertex.y]=1;
			for(int i=0;i<8;i++)
			{
				Point temp(nowVertex.x+movex[i],nowVertex.y+movey[i],nowVertex.pathN+1);
				if((a[temp.x][temp.y]==0)&&(temp.x>=1&&temp.x<=9)&&(temp.y>=1&&temp.y<=9))
				{
					cout< list;
		string str1,str2;
		cin >> str1 >> str2;
		Point start(str1[0]-96,str1[1]-48,0);
		Point end(str2[0]-96,str2[1]-48,0);
		list.push(start);
		cout<<"min is:"< 
 
事实上，对于最短路径问题，当图的相邻顶点之间的距离相同时，使用BFS是优于DFS的，因为此时绕路走肯定是更远的。(书p51)
 
优化思路如下(懒人一个，还没具体代码实现QAQ)：
 
A*优化算法(以下内容摘自教材《算法竞赛从入门到进阶》，仅作为个人笔记使用)
 
 
 
BFS是一种盲目的搜索技术，他在搜索过程中只会乱走！
 
 
对于人来说，有时候一眼能看出最短路径一定是走“某个方向的”，例如起点在棋盘中间，终点在棋盘右上角，那么我们知道，最短路径肯定是往右上角走（注意，此句话仅适用于当图的相邻顶点之间的距离相同时）。人有“智能”，那么能否把这种智能交给程序呢？这就是说”启发式搜索算法“。启发式搜索算法有很多种，A*算法是其中比较简单的一种。
 
 
简单来说，A*算法就是”BFS+贪心“
 
 

总结 
对于最短路径问题，当图的相邻顶点之间的距离相同时，使用BFS是优于DFS的，因为此时绕路走肯定是更远的，使用BFS先扩展到的路径，距离肯定是最短的。如果相邻点的距离不同，绕路可能更近，BFS就不适用了。