Ⅰ 搜索技术
问题求解过程是 搜索答案（目标） 的过程，所以问题求解技术也叫做搜索技术——通过对 状态空间 的搜索而求解问题的技术。
问题可形式化地定义成四个组成部分
在解题过程中 达到过的所有状态 的集合。不同于状态空间，搜索空间是其中一部分。状态空间和搜索空间都属于 过程性知识表示 。
八数码问题详解
两种搜索技术
无信息搜索策略也称 盲目搜索 ：没有任何附加信息，只有生成后继和区分目标和非目标状态。
五种盲目搜索策略有：广度优先搜索，代价一直搜索，深度优先搜索，深度有限搜索，迭代深入深度优先搜索。
从四种度量来评价广度优先搜索
性能：通常使用递归函数实现，一次对当前节点的子节点调用该函数。相比广度优先，内存需求少(分支因子 * 最大深度+1)。但 不是完备的也不是最优的 *。
深度优先搜索的无边界问题可以通过提供一个 预先设定的深度限制I 来解决。深度=I的节点当作无后继节点看待；虽然解决了无边界问题，但 有可能无解 ； 如果选择I>d则深度优先原则也不是最优解 。
每次改变限制深度 ，多次调用深度有限搜索，当 搜索到达最浅的目标节点深度 时就可以发现目标节点，称为迭代深入深度优先搜索。这种搜索结合了广度优先和深度优先两种搜索方式的优势。 解决了深度优先的完备性问题 。空间需求是(b * d),时间需求是(b d )。当搜索空间很大且深度未知时，迭代深入深度优先搜索 是首选的无信息搜索方式 。
迭代深入搜索中因为多次重复搜索上层节点，使部分状态反复生成，看起来很浪费内存空间和时间。但是因为 在分支因子比较均衡的搜索树 中， 多数节点都是叶子节点 *（叶子节点数远大于上层节点总和），所以上层节点多次生成的影响并不大，与广度优先相比，效率还是很高。
用于目标状态已知，求解过程的问题。通常通过 广度优先搜索 实现。从 起始节点和目标状态两个方向 开始扩展，当 两个OPEN表出现交集 时表明搜索到了一条从起始到结果的一条路径。 缺点 ：算法编写难。但一旦实现，效率要远高于其他盲目搜索。
评价函数 ：f ( n ) = h ( n ) ；评价函数等于启发函数
解释：贪婪最佳优先搜索中 无条件选择 当前离目标最近（代价最小）的结点进行扩展。但是 局部最佳不是全局最佳，即非最优。 其中h（ n ）称为 启发函数 ，是从节点n到目标节点的最低代价的 估计值 。
评价函数 ：f ( n ) = g ( n ) + h ( n )；评价函数等于启发函数加路径耗散函数
解释：
另，对于有向图的搜索还可以采用图搜索方式。详情： 图搜索和树搜索详解
称启发函数是可采纳的，如果h( n ) 满足 h( n ) ≤ h * ( n ) ，其中 h * ( n )是从当前节点 n到达目标的最低真实代价 ，即h( n )的估值永远小于真实耗散值；因为f ( n ) = g ( n ) + h ( n )，且g（n）为已知常数，所以 f（n）永远不会高估经过结点n的解的实际代价 ，所以是最优解。
如果采用 A* 图搜索算法，则不一定返回最优解 。因为如果最优路径不是第一个生成的，可能因为有重复状态而被丢弃了。见上个链接： 图搜索和树搜索详解
如果对于每个结点n，以及n的行为a产生的后继结点n'满足如下公式： h ( n ) ≤ c ( n, n', a) + h( n ') （c ( n, n', a)可以理解为g（n'）），则称这个h ( n )启发函数是一致的。
A* 搜索由初始结点出发开始搜索，以同心带状增长f（n）耗散值的方式扩展结点。如果h（n）= 0 意味着只按g（n）值排序，即同心带为“圆形”。使用启发函数则同心带向目标节点拉伸（椭圆越来越扁）。
如果C*是最优路径的耗散值，则：
A* 搜索的关键就是 设计可采纳的或一致的（单调的）启发函数 。
绝不高估 到达目标的耗散值，尽可能的接近真实耗散值
子问题的解耗散是完整问题的 耗散下界 。
从实例中学习，每个实例包含了解路径上各状态及其到达解的耗散值。每个最优解实例提供了可学习h(n)的实例，由此产生可预测其他状态解消耗的启发函数。
联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图
智能体初始位置在S，其已知信息为：
A* 搜索在不同子空间结点的跳跃式扩展， 模拟而非实际行动 ；联机搜索只扩展实际占据的结点——采用深度优先。 联机搜索必须维护一个回溯表
博弈搜索是智能体之间的对抗，每个智能体的目的是冲突的。本节需要解决两个问题：如何搜索到取胜的 路径 /如何提高搜索 效率 。相应的办法是 极大极小决策和α-β剪枝 。
两个智能体博弈时，可令一方为MAX，一方为MIN。MAX希望终局得分高，MIN希望终局得分低。
博弈搜索中，最优解是导致取胜的终止状态的一系列招数。MAX制定取胜策略时，必须不断考虑MIN应对条件下如何取胜。
如果博弈双方 都按照最优策略 进行，则一个结点的 极大极小值就是对应状态的效用值
简单的递归算法——按照定义计算每个后继结点的极大极小值/搜索是从目标到初始结点的 反向推导
如果博弈树最大深度为m，每个节点的合法招数为b，则
剪掉那些不可能影响最后决策的分支，返回和极大极小值相同的结果。
α-β剪枝可以应用树的任何深度。
如果在结点n的父节点或更上层有一个更好的选择m，则在搜索中永远不会到达n。
很大程度上取决于检查后继节点的次序—— 应先检查那些可能更好的后继 。如果能先检查那些最好的后继，则 时间复杂度为O(b (d/2) ) 。优于极大极小算法的O(b d )
许多问题中 路径是无关紧要的 。从当前状态出发，通常 只移动到相邻状态 ，且路径不保留。
内存消耗少，通常是一个常数。
向目标函数值增加的方向持续移动，直到相邻状态没有比它更高的值。 取到一个局部最优则终止 。
使新状态估计值优于当前状态值和其他所有候补结点值，则取新状态放弃其他状态。
将 爬山法 （停留在局部最优）和 随机行走 （下山）以某种方式结合，同时拥有 完备性和效率 。
技巧是，概率足够大可以弹出局部最优；但概率不能太大而弹出全局最优。
按照模拟退火的思想， T随时间逐渐减小 。如果 T下降的足够慢 ，则找到全局最优解是 完备的 。
随机移动，如果评价值改善则采纳； 否则以小于一的概率接受 。
从 k个随机生成的状态开始 ，每步生成k个结点的所有后继状态。如果其中之一是目标状态则停止算法；否则从全部后继状态中选择最佳的k个状态继续搜索。
有用的信息 在k个并行的 搜索线程之间传递 ，算法会很快放弃没有成果的搜索，而把资源放在取得最大进展的搜索上。
局部剪枝搜索的变种。因为局部剪枝搜索搜索是贪婪的，因而用随机剪枝搜索代替。不是选择最好的k个后代，而是按照一定概率选取k个后继状态。
类似于自然界的选择过程。状态对应个体，其 值对应适应性 ，后代就是状态。因此如果k个状态缺乏多样性，则局部搜索会受影响。
局部剪枝算法已有 群体进化 （优胜劣汰）的趋势。遗传算法是随机剪枝的变种。
包括选择，交叉和变异
又称繁殖，按照一定的概率选择两对个体生成后继状态
计算每个个体i被选中的概率： pi = f(i) / [f(1)+...+f(n)] .然后根据概率将圆盘分为n个扇形，每个扇形大小为 2Πpi 。
繁殖过程中，后代是父串在杂交点上进行杂交得来的。这样一来，后代子串保留了父串的优良特性又与父串不同。
首先以概率p随机在种群中选择pa和pb两个个体，再从{1,2,...,m}中（可以按一定概率，如两边概率小于中间概率）选择一个数i，作为交叉点。而后将两个个体的交叉点后面的部分交换。
在新生成的后继状态中各个位置都会按照一个 独立的很小的概率 随机变异。
变异时要做到 一致变异 ；即相同概率地变异所有个体的每一位。
结合了“上山”和随机行走，并在并行搜索线程之间交换信息。遗传算法的 最大优点在于杂交 。因为杂交可以 将独立发展的若干个砖块组合起来 ，提高搜索的粒度。
个体编码某些位置上数字仍未确定的一个状态子串。
如果 一个模式的实例的平均适应值超过均值 ，则种群内这个模式的实例数量会随时间而增长（优胜）；反之则减少（劣汰）
长度较短，高于平均适应度的模式在遗传算子的作用下， 相互结合 ，能生成长度较长、适应度较高的 模式 。
Constraint Satisfying Problem，CSP。
由一个 变量集合{X1~Xn} 和一个 约束集合{C1~Cn} ；每个变量都有一个 非空可能的值域Di 。每个约束指定了 若干变量的一个子集内各变量的赋值范围 。
CSP的一个状态是，对一些或每个变量赋值
一组既是 相容赋值 又是 完全赋值 的对变量的赋值就是CSP的解。
提前考虑某些约束，以减少搜索空间
若X被赋值，检查与X相连的Y，判断是否满足约束，去掉Y中不满足约束的赋值。（进行某种检验，可以不为有问题的Y集合赋值 ）
Ⅱ 什么是宽度优先搜索
是数据结构中的问题，涉及到图的遍历，应该是深度优先搜索，和广度优先搜索吧？
追问，在线。。。
你说的宽度优先，应该就是广度优先，不一样的叫法而已。
【广度（宽度）优先搜索】
类似于树的层次遍历，先从一个顶点出发，依次遍历与之相邻的未访问过的，也就是先搜索与顶点路径为1的，全部写出；在搜索与顶点路径为2的，全部写出……以此类推，通俗地讲，是采用了一种扩散的方法来搜索整张图
【深度优先搜索】这是与广度优先相对立的一种搜索方式
从一个顶点出发，找一条路径（注意，只是一条），依次写出一直相邻的的未被访问过的结点，直到这条路都被访问过，通俗地讲，就是一条路径走到头，之后在返回上一个结点看有没有未访问的，再返回上一个，再返回上一个……以此类推
都是自己的话说的，更容易理解些，希望对你有帮助o(∩_∩)o
Ⅲ 图的矩阵深度和广度遍历算法
图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。
图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1，V2和V3之后，有可能沿着边（V3，V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空
集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
从图G=（V，E）的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
例25.(p194.c)图的深度优先搜索。从图G的顶点V0
发进行深度优先搜索，打印出各个顶点的遍历顺序。
解：图的深度优先搜索法为：
（1）首先访问V0并把V0加到集合visited中；
（2）找到与V0相邻的顶点W，若W未进入
visited中，则以深度优先方法从W开始搜索。
（3）重复过程（2）直到所有于V0相邻的顶点
都被访问过为止。
下面是对用邻接表表示的图G进行深度优先搜索的程序
int rear=0; /*Visit和rear都为全局变量*/
int visit[500];
depth_first_search(g,v0) /*从V0开始对图G进行深度
优先搜索*/
graphptr g[ ]; /*指针数组,为邻接表表头顶点指针
g[vi]...g[vn]*/
int v0; /*这里V0和W都是顶点标号,如V0=0或1*/
{ /*g[v0]是顶点V0的表头指针*/
int w;
graphptr p; /*链表的结点指针*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一个顶点，通过邻接表表头指针
，访问v0的邻接顶点*/
while (p!=NULL)
{
w=p->vertex ;/*这里W是与V0相邻的一个顶点*/
if (!visited(w))/*当V0的相邻结点，W未被访问时，从W开始遍厉*/
depth_first_search(g,w);
p=p->next;/*接着访问另一个相邻顶点*/
}
}
int visited(w) /*检查顶点w是否进入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，说明被访问过*/
return(0); /*W不在visit[]中，说明未被访问过，返回0*/
}
2）图的广度优先搜索
从图G的一个顶点V0出发，依次访问V0的邻接点K1,K2...Kn。然后再顺序访问K1,K2...Kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从V1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
（1）首先把V0放入队列；
（2）若队列为空则结束，否则取出队列的头V；
（3）访问V并把所有与V相邻且未被访问的顶点插入队列；
（4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
广度搜索法的程序如下：
broad_first_search(g,v0) /*从V0开始对图g进行广度优先搜索*/
graphptr g[ ]; /*为邻接表，表头顶点指针*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入队列queue*/
while (front <=tail)/*当队列不为空*/
{
v=queue[front++]; /*取出队列中的顶点*/
printf("%d\n",v); /*访问该顶点*/
p=g[v]; /*从顶点V的链表来考虑与V相邻的顶点*/
while (p!=NULL)
{
v=p->vertex; /*从第一个结点（即边）中找出相邻的顶点*/
if (!visited(queue,tail,v))/*判断顶点是否进入队列，如进入队列
说明已被访问或将要访问*/
queue[++tail]=v;/*如果该顶点未被访问过，将此相邻顶点插入队列*/
p=p-->next;/*再考虑该结点的下一个相邻顶点*/
}
}
}
visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/
int q[ ],tail,v;/*进入队列的顶点，在front之前的顶点已被访问过打印输出，
在front和tail之间的顶点是即将要访问顶点*/
{
int i;
for(i=1;i<=tail;i++)/*扫描队列，确定v是否在队列中，在队列中返回1，否则返回0*
/
if (q[i]==v)return(1);/*队列中的顶点都认为已被访问过*/
return(0);
}
深度优先的非递归算法
/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())
{
p=stackMain.pop();
}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.
{
visit(p);
p.marked=true;
}
}while(!stackMain.isEmpty())
Ⅳ 广度优先搜索是什么
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的
算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的伫列中。一般的实作里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如伫列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
Ⅳ 深度优先搜索和广度优先搜索的区别。 请讲的详细点，最好能用例子，谢谢啦
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。
深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。
宽度优先搜索基本算法如下：
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}
望采纳
Ⅵ 广度优先搜索有什么难点
广度优先搜索难点在于每一种算法的不同，树的遍历。
扩展知识：
广度优先搜索算法又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
广度优先搜索算法主要有四个特性：
空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS已达节省空间的效果。
时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。
完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。