猿类的进化史

  本文关键词：搜索理论，由笔耕文化传播整理发布。

搜索理论

宽度优先搜索bfs 

一、搜索的bfs，宽度优先搜索，一般用于求最短的得到到目的地的距离，有个起始点，先把这个起始点入队列，不要忘记将这个起始点标记为已经利用，不然会走回来的，然后是与这个起始点的周围的点的监测，若可以行的通，我们一一检测这些扩展出来的点，若是目的地就结束了，若不是目的地，将改点标记为已经利用，并将该点入队列。

 二、搜索的双向bfs，双向的bfs一般来说可以用单向解决，但是单向的效率上还是差了点，适合双向bfs的题目有一些共同特点：给出起始和最终状态，让求出一条从初始到末状态的最短路。

双向bfs的实现过程： 从初始结点开始扩展，每扩展一层，在从目标节点按照产生系统相反的办法来扩展结点，直到从两端扩展出的某个结点相遇，那么中间的这条路径一定就是从初始到终点最短的路径。

注意： 双向广搜必须按层扩展，才能保证结果的正确性

无解状态就和普通bfs无异, 所以判断无解函数不可省略.  

     路径的保存：有时候除了要找到一个目标状态，还需要保存从初始结点到它的路径。路径可以随状态保存，也可以用链表穿起来。如果保存的所有结点或者路径长度不定，推荐使用链表。

int DBFS() { Queue Q[2]; Map M[2]; int now=0; Q[0].push(start); Q[1].push(end); M[0][start]=M[1][end]=true; While( !Q[0].empty() || !Q[1].empty) { int nowg=now&1,count=Q[nowg].size(); while(count--) { curstate=Q[nowg].front(); Q[nowg].pop(); if( M[nowg^1].find(curstate) != M.end() )return now; for every extstate=extend(curstate) if(M[nowg].find(extstate) == M.end()) { Q[nowg].push(extstate); M[nowg][extstate] =true; } } ++now; } return -1; }

 深度优先搜索dfs

一、深度优先搜索一般是给定搜索的深度，或者没有深度有结束条件的，可以用结束条件代替深度，都可以用dfs

二、dfs回溯用来解决搜索所有解的问题，但是纯粹的dfs回溯往往会超时，一般与剪枝联系在一起

三、剪枝一般分为可行性剪枝和最优化剪枝 

（1）可行性剪枝， 剪去不能到达终点的路径

（2）最优化剪枝， 剪去不能到达终点和不可能是第一个到达终点的路径

 迭代加深搜索

一、用于不知道最短转移次数，为了弥补广搜的空间不足的问题而产生的搜索方法

形式为：for( depth=init(); dfs() ; depth++ ) 

使用是要注意：

（1）由于不知道上界， 如果问题无解的情况下就不能用这个了

 （2）对深度较浅的层数会重复搜索，并不推荐使用

Procedure ID-dfs(dep:integer); Var J: integer; Begin If dep>深度的限界 then exit; // 如果搜索的深度大于限界，则返回上一层 For j:=1 to n do // 按照规则生成子结点 If 子结点安全 then Begin 入栈； If 子结点是目标结点 then 对目标结点进行处理，退出程序 Else id-dfs(dep+1); 退栈； End; End; For i:=1 to depmax do // 枚举深度的限界 Begin Id-dfs(i); If 运行超时 then break; End;

从上述迭代加深搜索算法的实现过程和框架，我们可以看出，迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。

既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。

A*算法

A*类似贪心的BFS 

BFS一般扩展最小消耗的点，A*算法在另一方面 扩展最有希望的点（估价函数返回值最优）

状态被保存在一个优先级队列中，按照cost*价值排列。对一个可容许的估价函数，第一个找到的状态保证是最优的。

一、A*算法属于启发式搜索，扩展结点的顺序是基于广度优先搜索，但是不同之处在于每扩展一个子结点需要计算估价函数f（s），以估算起始结点，经过该结点到达目标结点的最佳路径代价，每当扩展结点时，总是希望在所有待扩展结点中选择具有最小

f（s）值的结点作为扩展对象，以便使搜索尽量沿着最有希望的方向进行。 

假设s表示一个状态，

f（s）：启发式函数，表示从初始状态开始，经过状态s的路径上最少需要多少代价才可以找到终点之一。

g（s）：从初始状态到当前状态s的最小代价

h（s）：估价函数，从当前状态s到达终点之一最少需要多少代价

有关系式f（s）=g（s）+h（s）

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：

A*必须满足两点：

h（s）<=h*(s) 和 f（s）必须是递增的

1) 搜索树上存在着从起始点到终了点的最优路径。

2) 问题域是有限的。

3）所有结点的子结点的搜索代价值>0。

4）h(n)=<h*(n) （h*(n)为实际问题的代价值）。

当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。

对于一个搜索问题，显然，条件1,2,3都是很容易满足的，而

条件4)： h(n)<=h*(n)是需要精心设计的，由于h*(n)显然是无法知道的。

所以，一个满足条件4）的启发策略h(n)就来的难能可贵了。不过，对于图的最优路径搜索和八数码问题，有些相关策略h(n)不仅很好理解，而且已经在理论上证明是满足条件4)的，从而为这个算法的推广起到了决定性的作用。不过h(n)距离h*(n)的程度不能过大，否则h(n)就没有过强的区分能力，算法效率并不会很高。对一个好的h(n)的评价是：h(n)在h*(n)的下界之下，并且尽量接近h*(n).


当然，估值函数的设计也就就仅仅是f(n)=g(n)+h(n)一种，，另外的估值函数“变种”如：f(n)=w*g(n)+(1-w)*h(n) ，f(n)=g(n)+h(n)+h(n-1)针对不同的具体问题亦会有不同的效果。

        A*算法最为核心的过程，就在每次选择下一个当前搜索点时，是从所有已探知的但未搜索过点中(可能是不同层，亦可不在同一条支路上)，选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素（f值），对其可能子结点计算g、h和f值，直到优先队列为空(无解)或找到终止点为止。 

A*算法与广度优先和深度优先的联系就在于，当g(n)=0时，该算法类似于DFS，当h(n)=0时，该算法类似于BFS , 这一点，可以通过上面的A*搜索树的具体过程中将h(n)设为0或将g(n)设为0而得到。 

       路径最优问题，简单来说，就是在两个结点之间找一条最短路径。有的朋友不禁要问，这个问题不是已经有Dijkstra算法可以解决了吗？此话不假，但是不要忘了Dijkstra算法的复杂度是O(n^2)，一旦结点很多并且需要实时计算的话，Dijkstra就无法满足要求了。而A*来处理这类有需要实时要求的问题则显得游刃有余。

       在路径最优问题中，用来作为启发函数关键部分的h(n)其实很容易选，那便是当前结点至最终结点的距离，这个距离既可以是曼哈顿距离(|x1-x2|+|y1-y2|)，亦可以是Euclid（欧几里得或者欧式距离） 距离(直线距离)。都可以在较快的速度下达到问题的最优解。 

伪代码

主要搜索过程伪代码如下：
　　创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。　
　　算起点的估价值;
　　将起点放入OPEN表;
　　while(OPEN!=NULL)　
　　{　
　　从OPEN表中取估价值f最小的节点n;　
　　if(n节点==目标节点){　
　　break;　
　　}　
　　for(当前节点n 的每个子节点X)　
　　{
　　算X的估价值;　
　　if(X in OPEN)
　　{　
　　if( X的估价值小于OPEN表的估价值 ){　
　　把n设置为X的父亲;　
　　更新OPEN表中的估价值; //取最小路径的估价值　
　　}
　　}
　　if(X inCLOSE) {　
　　if( X的估价值小于CLOSE表的估价值 ){　
　　把n设置为X的父亲;　
　　更新CLOSE表中的估价值;　
　　把X节点放入OPEN //取最小路径的估价值　
　　}　
　　}
　　if(X not inboth){　
　　把n设置为X的父亲;
　　求X的估价值;　
　　并将X插入OPEN表中; //还没有排序　
　　}
　　}//end for
　　将n节点插入CLOSE表中;　
　　按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
　　}//end while(OPEN!=NULL)
　　保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径

posted on

  本文关键词：搜索理论，由笔耕文化传播整理发布。