关于搜索
作者：焦祺 08-11-3
关于搜索，我一直没有系统的总结过，对于ACM，我除了一些自己写的东西和有用的模板外，我一直没有保留什么太多的资料，这可能和我的方法不同有关，一般好的资料都应该转化为思想以笔记的形式整理，这样可以更好的实现知识内化，而不好的资料则更是没有什么保留的意义。这也是为什么我写这篇关于搜索的文章。
对于搜索的领域及经典搜索的分类：
1：地图寻路问题
盲目搜索策略有：
广度优先搜索，深度优先，*迭代加深搜索．
启发式搜索 有：
Ａ＊（用评估函数，永远先扩展最有可能更快达到目标点的节点）
Ａ算法（）
ＩＤＡ＊（Ａ＊＋迭代加深iterate depth）
双向搜索．
2：博弈问题
解决ＡＩ问题，在博弈数搜索中通常会使用Alpha-Beta剪枝，当总是先展开评估值高的节点时用SSS*算法，其改进型是MemSS*（对内存空间有上限控制）．
3：智能算法
遗传算法（Genetic Algorithm）模拟退火算法（Simulater Annealing）,禁忌搜索（Tabu Search）人工神经网络（Artificial Neural Network）
4:优化
a数学方法的改进
b预运算节省时间，或者重复运算来节省空间
c简化算法求得近似解来取代精确解
d改进数据组织方式，用更少的操作处理更多的数据
e尽可能让计算机做并行操作
主要研究方向：
地图寻路问题的搜索
盲目搜索策略：
广度优先搜索（BFS）
::简单好用的搜索方法，通常结合队列或优先队列的使用。
算法思想：
从一点出发，将待搜索的点入队列，弹出搜索点，再将待搜索的点入队列，以此实现广度方向上的优先搜索。
n 宽度优先搜索算法的算法框架
对于宽度优先搜索法来说，问题不同则状态结点的结构和结点扩展规则是不同的，但搜索的策略是相同的，因此算法框架也基本相同。
struct tnode{ //定义一个结点数据类型
…… //根据具体问题确定所需的数据类型
}state[maxn]; //定义tnode类型的数组作为存储结点的队列
void init(); //初始化函数
bool extend(); //判断结点是否能扩展，如果能则产生新结点
bool repeat(); //检查新结点是否在队列中已经出现
bool find() //检查新结点是否目标结点
void outs(); //输出结点状态
void printpath(); //输出路径
//----------------------------------------------------------------------------------------------
int main()
{
init();
bfs();
}
//-----------------------------------------------------------------------------------------------
void init()
{
//初始化
}
//-----------------------------------------------------------------------------------------------
void bfs() //BFS算法主程序
{
tnode temp; //tnode型临时结点
int head=0,tail=0; //队列头指针和尾指针
while(head<=tail && tail<maxn )
{
//队列非空且数据空间为用完时循环
//根据具体问题确定一个结点扩展规则
temp=state[head]; //取队列头的结点
if(extend())
{//如果该结点可以扩展则产生一个新结点
if(!repeat())
{ //如果新结点未曾在队列中出现过则
tail++; // 将新结点加入队列尾
state[tail] =temp;
state[tail].last=head; //记录父结点标识
if(find())
{ // 如果新结点是目标结点
tail++; // 将队列尾结点的父结点指针指向队列尾
state[tail].last =tail-1;
printpath(); //输出路径
break; //退出程序
}
}
}
head++; //队列头的结点扩展完后出队，取下一结点扩展
}
}
//-----------------------------------------------------------------------------------------------
::对于广度优先搜索的应用，关键还是要先对其过程的了解，通过实际的题目，写出自己的模板，以便今后的应用。
有几种模板是必要的：
一般搜索
三维搜索
BFS中使用优先队列
以下是几道相对经典的模板级题目例程:
一般的平面搜索 ：HDOJ1072 Nightmare炸弹逃脱问题
#include<iostream>
using namespace std;
#include<queue>
#include<cmath>
void bfs();
struct Node
{ int x; int y; int left_time;int count;};
int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
int map[9][9],l[9][9];
bool mark[9][9],success;
int n,m,s_x,s_y,e_x,e_y;
Node N,P;
int s[9][9];
int main()
{ int t,i,j;
while(scanf("%d",&t)!=EOF)
{ while(t--)
{ int wall=0;
scanf("%d%d",&n,&m);
for(i=0; i<n ; i++)
{ for(j=0;j<m;j++)
{ scanf("%d",&map[i][j]);
if(map[i][j]==0)
wall++; //统计墻数
if(map[i][j]==2) //标记起点
{ s_x=i;s_y=j; }
if(map[i][j]==3) //标记终点
{ e_x=i;e_y=j; }
}
}
if(wall+abs(s_x-e_x)+abs(s_y-e_y) >= n*m) //剪枝
cout<<-1<<endl;
else
{
success=false;
bfs(); //广搜
if(success)
cout<<N.count<<endl; //成功输出时间
else cout<<-1<<endl;
}
}
}
}
void bfs()
{ queue<Node> Q; //建立一个队列
N.x=s_x; N.y=s_y; N.left_time=6; N.count=0;
Q.push(N);
memset(s,-1,sizeof(s));
memset(mark,0,sizeof(mark));
while( !Q.empty() )
{ N=Q.front(); //找队列中第一个数
Q.pop(); //弹出来
int i;
if(s[N.x][N.y] < N.left_time) //标记最少用时，得到余时大者
s[N.x][N.y] = N.left_time;
else //如果本身的大，那么标记该点
mark[N.x][N.y]=1;
if(N.left_time>0 && map[N.x][N.y]==3) //成功找到!!
{success=1;break; }
//----------------------开始向四方向搜：
for(i=0;i<4;i++)