最优搜索算法

‘壹’ Matlab神经网络原理中可以用于寻找最优解的算法有哪些

若果对你有帮助，请点赞。
神经网络的结构（例如2输入3隐节点1输出）建好后，一般就要求神经网络里的权值和阈值。现在一般求解权值和阈值，都是采用梯度下降之类的搜索算法（梯度下降法、牛顿法、列文伯格-马跨特法、狗腿法等等），这些算法会先初始化一个解，在这个解的基础上，确定一个搜索方向和一个移动步长（各种法算确定方向和步长的方法不同，也就使各种算法适用于解决不同的问题），使初始解根据这个方向和步长移动后，能使目标函数的输出（在神经网络中就是预测误差）下降。 然后将它更新为新的解，再继续寻找下一步的移动方向的步长，这样不断的迭代下去，目标函数（神经网络中的预测误差）也不断下降，最终就能找到一个解，使得目标函数（预测误差）比较小。
而在寻解过程中，步长太大，就会搜索得不仔细，可能跨过了优秀的解，而步长太小，又会使寻解过程进行得太慢。因此，步长设置适当非常重要。
学习率对原步长（在梯度下降法中就是梯度的长度）作调整，如果学习率lr = 0.1,那么梯度下降法中每次调整的步长就是0.1*梯度，
而在matlab神经网络工具箱里的lr,代表的是初始学习率。因为matlab工具箱为了在寻解不同阶段更智能的选择合适的步长，使用的是可变学习率，它会根据上一次解的调整对目标函数带来的效果来对学习率作调整，再根据学习率决定步长。
机制如下：
if newE2/E2 > maxE_inc %若果误差上升大于阈值
lr = lr * lr_dec; %则降低学习率
else
if newE2 < E2 %若果误差减少
lr = lr * lr_inc;%则增加学习率
end
详细的可以看《神经网络之家》nnetinfo里的《[重要]写自己的BP神经网络(traingd)》一文，里面是matlab神经网络工具箱梯度下降法的简化代码

‘贰’ A*算法 和 最佳优先搜索算法（Best-First-Search）

最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。 BFS算法不能保证找到的路径是一条最短路径，但是其计算过程相对于Dijkstra
算法会快很多 。

最佳优先搜索是一种启发式搜索算法。广度优先搜索和深度优先搜索都属于穷举类型的搜索，需要依次遍历所有的节点，当空间非常大的时候，这种方式的效率就会非常差。而启发式的搜索是对状态控件中的每个点进行评估，然后选出最好的位置。

启发估价函数公式为：

n表示当前的点，g(n)为从起始点到点n的实际代价，h(n)为从点n到目标点的估价。

（图片来源于网络）

A*算法将BFS算法和Dijkstra算法结合在一起，结合两算法的优点，既可以查找最短路径的，有拥有和BFS差不多的效率。

（图片来源于网络）

A*算法详解

模拟寻路的地址

‘叁’ 数据结构中，查找算法最优的是哪一种

折半查找法的平均查找长度随n增大而呈现对数增长趋势，因此折半查找法为最优查找算法

‘肆’ dfs算法是什么

DFS是深度优先搜索算法。

深度优先搜索算法，又称DFS(Depth First Search)。DFS算法是一种搜索算法，而搜索算法实质上是一种枚举，即借助计算机的高性能来有目的地枚举一个问题的部分情况或这个问题的所有情况，进而求出问题的解的一种方法。

分类：

1. 顺序性剪枝

若一些题的搜索顺序对答案无影响，那么搜索顺序的不同会导致搜索树形态的改变，优先搜索分支较少的阶段，此时能减少搜索的规模。

2. 重复性剪枝

在搜索的时候如果有多种方式可以到达一个状态，那么只需要搜索一个分支就可以了。

3. 可行性剪枝

可行性剪枝是对搜索正确性的一个保证，当分支在递归边界的时候回溯。

4. 最优性剪枝

在搜索过程中，如果当前阶段的代价已经超过我们已知的最小代价，那么此时继续搜索下去就失去了意义。

5. 记忆化剪枝

记录搜索状态的结果，当重复遍历一个状态的时候就可以直接返回这个状态的答案，避免重复的搜索。

‘伍’ 宽度优先搜索算法(pascal)

宽度优先搜索（BFS，BreadthFirstSearch）是一种搜索算法，其主要用来解决最优解问题。原型是图的宽度优先遍历问题，即从源顶点s出发，遍历每一个节点，它的基本思路是：先扩展当前节点所有邻接的节点，然后再从这些顶点出发，遍历所有顶点，即分层处理，将遍历路径表示成树，就是按层次遍历。

宽度优先搜索实现要依赖队列，即先进先出表（FIFO），这样保证了搜索的顺序正确。下面以图的遍历为例，写出标准算法（伪代码）

BFS(G,s)

foreachvertexuexceptsdo//对除源顶点外的所有节点进行初始化

begin

visited[u]:=false;//是否访问过

distance[u]:=infinite;//距源顶点距离

parent[u]:=NIL;//父节点

end;

visited[s]:=true;//对源顶点进行初始化

distance[s]:=0;

parent[s]:=NIL;

ENQUEUE(Q,s);//入队；Q为队列

whilenot(empty(Q))do //队列不空

begin

u:=DEQUEUE(Q);//队首元素出队

foreachvertexVbelongstoAdj[u]do//扩展每个邻接节点

ifvisited[v]=falsethen//如果未访问

begin

visited[v]:=true;//标记已访问

distance[v]:=distance[u]+1;//距离更新

parent[v]:=u;//父节点记录

ENQUEUE(Q,v);//入队

end;

end;

实际运用时要注意在达到结果后就要加一个break退出并输出。为什么宽度优先搜索能解决最优问题呢？因为根据宽搜的策略，被搜索到的顶点被戳上的distance标记就是到源顶点的最短路径的距离，因此可以解决无权图的最短路径问题以及由其抽象而来的最优问题。

题目要求并不一样，有的要求最优解大小，就可以直接输出distance；有的要输出最优解路径、方法，可以用循环将parent层层取出，入栈调整顺序输出，这也算一个技巧。

也许你还看不懂算法，可以找本算法导论好好读读，上面的图示对于理解很有帮助。

PS：敲完之后看了看网络，发现上面的内容完全改成了算法导论，可以去看看。尤其图示，很有帮助的。

‘陆’ 九宫格标注法中的A是什么意思

A*算法是寻找最优路径的搜索算法之一。常见的最优路径搜索算法有大英博物馆过程、分支界限搜索等。与其它搜索算法相比，A*算法具有较高的搜索效率。本质上，A*搜索过程是带低估值的分支限界搜索过程与动态规划搜索过程的结合。
A*算法的核心是一个估价函数:f(x)=g(x)+h(x)，它是对从初始状态So经过当前状态x到达目标状态S的整个路径的估计长度。其中 gx)是对已走距离的估计函数，h(x)是对当前状态到目标状态距离的估计。在A*搜索过程中，用整个路径的估计长度对部分路径进行排序，每次选择具有最短估计长度的部分路径进行扩展。

‘柒’ 广度优先搜索怎么保证最优解啊（新手不懂，求指导）

尽可能广的遍历图的结点，类似于树的层序遍历。遍历顺序不唯一，但确定的遍历顺序，对应确定的生成树。

‘捌’ 搜索算法的运算原理

搜索算法实际上是根据初始条件和扩展规则构造一棵“解答树”并寻找符合目标状态的节点的过程。所有的搜索算法从最终的算法实现上来看，都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。
由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。

‘玖’ 常见算法5、广度优先搜索 Breadth-First Search

1、定义

广度优先搜索 （Breadth-First Search）是最简便的图的搜索算法之一，又称 宽度优先搜索 ，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

2、应用

广度优先搜索被用于解决 最短路径问题（shortest-path problem） 。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

3、图简介

既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。

图由 节点 和 边 组成。一个节点可能与多个节点相连，这些节点被称为邻居。

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。

例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：

而使用广度优先搜索工作原理大概如下 ：

1、Python 3 ：

2、php ：

1、《算法图解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue类： https://www.php.net/manual/zh/class.splqueue.php