深度优先搜索（DFS）
1．图的深度优先遍历的递归定义
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
2、深度优先搜索的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
n 深度优先搜索算法的算法框架
1对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点；
2深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生站顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结点。
含有深度界限的深度优先搜索算法如下：
(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。
(2) 如果OPEN为一空表，则失败退出。
(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。
(4) 如果节点n的深度等于最大深度，则转向(2)。
(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。
(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。
::DFS一般是用递归或STACK实现，有的题目还会涉及到回溯。
它的学习方法和BFS类似，这里不加以赘述：
下面是DFS模板级例程：
//HDOJ_1010
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
char map[9][9];
int n,m,t,di,dj;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void dfs(int si,int sj,int cnt)
{
int i,temp;
if(si>n || sj>m || si<=0 || sj<=0) //搜索越界返回
return;
if(cnt==t && si==di && sj==dj) /到达！
escape=1;
if(escape)
return;
temp=(t-cnt)-abs(si-di)-abs(sj-dj);
if(temp<0 || temp&1) //
return;
for(i=0;i<4;i++)
{
if(map[si+dir[i][0]][sj+dir[i][1]]!='X')
{
map[si+dir[i][0]][sj+dir[i][1]] = 'X';
dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
map[si+dir[i][0]][sj+dir[i][1]]='.';
}
}
return;
}
//----------------------------------------------------
int main()
{
int i,j,si,sj;
while(cin>>n>>m>>t)
{
if(n==0&&m==0&&t==0) break;
int wall=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S') { si=i; sj=j; }
else if(map[i][j]=='D') { di=i; dj=j; }
else if(map[i][j]=='X') wall++;
}
if(n*m-wall<=t) //时间与路程关系剪技
{
cout<<"NO"<<endl;
continue;
}
escape=0;
map[si][sj]='X';
dfs(si,sj,0); //开始搜索
if(escape) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
//PKU 1256_Anagram
//深度优先搜索，给出n个字符串,对于每一个字符串,按字母顺序输出其中字母的所有排列形式,相同的只能出现一次.
#include<iostream>
using namespace std;
char str[15],temp;
char s[15];
char flag[15];
char save[1000][15];
int tag[15];
void dfs(int n);
int len,counter,sc;
int main()
{
int i,j,k,n,m,t;
scanf("%d",&n);
while(n--)
{
counter = 0 , sc = 0;
scanf("%s",str);
len = strlen(str);
for(i=0;i<len;i++)
{
if(str[i] <= 'Z') //如果是大写
flag[i] = str[i] + 'a' - 'A';
else
flag[i] = str[i];
}
flag[len] = '/0';
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(flag[i] > flag[j])
{
temp = str[i];
str[i] = str[j];
str[j] = temp;
temp = flag[i];
flag[i] = flag[j];
flag[j] = temp;
}
else if(flag[i] == flag[j])
{
if(str[i] > str[j])
{
temp = str[i];
str[i] = str[j];
str[j] = temp;
temp = flag[i];
flag[i] = flag[j];
flag[j] = temp;
}
}
}
}
//sort done
//printf("%s/n",str);
for(i=0;i<len;i++)
{
memset(tag,0,sizeof(tag));
memset(s,NULL,sizeof(s));
counter = 0;
dfs(i);
}
for(i=0;i<sc;i++)
printf("%s/n",save[i]);
}
return 0;
}
void dfs(int n)
{
int i,j;
s[counter] = str[n];
counter++;
tag[n] = 1; //已搜标记
for(i=0;i<len;i++)
{
if(tag[i] == 0)
{
dfs(i);
tag[i] = 0;
counter--;
}
}
if(i == len)
{
for(j=0;j<sc;j++)
{
if(strcmp(save[j],s) == 0)
break;
}
if(j == sc)
{
strcpy(save[sc] , s);
sc++;
}
}
}
然而这样不经过优化的深度是很容易超时的
对于这样的问题，我们有两种选择
第一，放弃使用原来的搜索，如换成启发式搜索，甚至是换一种做法。
如直接用STL的全排列。
第二，剪枝！
不得不说，剪枝是搜索中一项重要的技术。
而剪技中的经典不得不数PKU1011
本题中所用到的剪枝技巧：
剪枝1：分段数res肯定能被总长度sum整除
剪枝2：每段的长度不可能大于初始分段的最大值
剪枝3：将输入的数据从大到小排序，因为一支长度为L的完整木棍肯定比几支短木棍拼成的同样长度的用处小（短小的用途更灵活一点）
剪枝4：找到结果之后在能返回的地方马上返回递归的上一层
剪枝5：相同长度的木棍不要搜索多次，用当前的这支搜下去得不出结果,那么用下一支同样长度的还是得不到结果
剪枝6：相当关键的剪枝，就是栽在这个剪枝上面两个多小时。判断当前长度是不是大于每段应该的长度，如果大于则没必要往下递归
剪枝7：不用说了，前面的肯定都用过了，所以从level+1开始
剪枝8： if(all-times+1<res-no)判断当前剩下的段数是否还足以拼成需要拼得的段数
剪枝9：如果从当前最长的长度开始往下搜索一遍得不到正确结果则返回，因为每段都要用上，如果搜索不成功，那么以比它短的开始也一定不能得到全局的成功。
剪枝的原则
原则之一：正确性。
我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。
为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了）。
原则之二：准确性。
在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。因此，准确性可以说是剪枝优化的生命。
当然，为了提高剪枝判断的准确性，我们就必须对题目的特点进行全面而细致的分析，力求发现题目的本质，从而设计出优秀的剪枝判断方案。
原则之三：高效性。
一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。
然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。
综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
当然，我们在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类：
1. 可行性剪枝。
2. 最优性剪枝（上下界剪枝）。
::但不管怎样剪枝，一个现实的问题摆在眼前，在一些较难的搜索题中，盲目的搜索方法往往是不够用的，于是我们不得不用一种更优的搜索方式：启发式搜索！
盲目搜索的不足：效率低，耗费过多的计算空间与时间。
分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。
启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。
把利用启发信息的搜索方法叫做启发性搜索方法。