搜索算法详解

EraYes2023-07-132023-12-08

#搜索算法

搜索算法，即对当前的状态空间进行枚举，以找到对于某一问题的特殊解或最优解，这类算法被广泛应用在图遍历，寻路,算法竞赛等之中，在信息学竞赛中，搜索算法是十分重要的一类算法，通常涉及图论和组合数学等复杂问题的求解。对于大范围的枚举，又衍生出各种各样的优化算法，通过剪枝、压缩空间、双向搜索等

搜索寻路可视化

网页嵌入如下

点击查看

文献
A*，Dijkstra，BFS算法性能比较及A*算法的应用
 彻底理解Dijkstra算法
 Dijkstra算法(一)之 C语言详解
 路径规划之 A* 算法
 常用距离算法详解

DFS

**DFS（Depth-First-Search）**即深度优先搜索。具体来说，DFS算法从起点开始遍历图，尽量沿着深度方向遍历下去，直到无法前进时回溯到上一个节点，继续遍历其它分支。DFS一般用于遍历或搜索一些树形结构或图结构的问题。在信息学竞赛中，DFS算法常用于解决排列、组合、路径搜索等一些组合问题，例如全排列、八皇后问题等。

BFS

BFS（Breadth-First-Search）即广度优先搜索。BFS算法会按照层次分别访问每个节点，可以得到所有可能的路径中最短路径。BFS算法一般用于图上最短路径等问题上。在信息学竞赛中，BFS算法常用于解决图上的最短路问题、迷宫路径搜索等问题。

Dijkstra

Dijkstra可以看成时加权的BFS，在引入权值之后，算法在拓展时就可以考虑到不同的收益带来的效果，这图论搜索时，求解有向图和无向图的最短路径问题时就相对很优秀了，实际上在实际应用中，Dijkstra算法常用于解决网络路由最短路径问题、制作地图应用程序、优化电路设计、以及示例中的游戏寻路等问题。
但是相对的，在权值都为1时，Dijkstra就和BFS差不多了

动画1
动画2

A*

**A***是一种基于Dijkstra启发式搜索算法，能够有效地搜索最短路径，其目标是最小化当前路径的代价，同时通过加入启发函数剪枝掉明显不优的状态节点，从而尽可能降低搜索的时间复杂度。A算法需要启发式函数的支持，因此在对路径搜索灵活度要求比较高的情况下，可以使用A算法。
启发函数时A算法中最重要的一部分，启发函数的选择直接关系到A算法的效率和结果。它是一种能够对当前状态节点与目标状态距离进行有效估算的，用于衡量当前节点在搜索过程中离目标节点还有多远，从而选择合适的路径。
- 需要注意的是，当h(x)为0时，A算法退化为Dijkstra算法，而当h(x)不为0时，A算法具有更好的搜索效率。

启发函数

**OI wiki**中这样介绍，定义起点s，终点t，从起点（初始状态）开始的距离函数g(x)，到终点（最终状态）的距离函数h(x)，h*(x)，以及每个点的估价函数f(x)=g(x)+h(x)。
但说实话，这些确实比较抽象，而且OI wiki讲的还不够详细，下面我来讲讲我的理解：
- f(x) = g(x) + h(x)
- 综合评价函数f(x) 其实就是当前状态的地位或效益，这个值更具题意当然总是越小越好，但在一些较抽象的数论题里，它也许还能代表操作的价值、目前的做法和接下来的做法，当然，这还是抽象，我们接着往下看
- 路径长度g(x) 最好理解，其实就是走过的步数、进行过的操作，这个值用以储存其实状态到当前状态的路径长度
- 启发函数估价函数h(x) 表示当前状态x到达目标状态的最短路径估计值，在图论里，它可以是节点数和权值，在八数码里，它则是与目标码不同的数字的个数
在链接中，你可以很清楚的看到在地图里这启发函数是如何运行的。这是一篇很好的文章，我也是在CSDN疯狂“转载” 包浆中发现的

关于距离

在二维平面坐标系中的格点搜索问题中，选择怎样的距离尤其重要，但本人认为对于算法竞赛而言并不直接，因为大部分搜索题是图和数的关系
我也查询一些有意思的距离函数，如果感兴趣的话你可以点开来看看，因为我也很感兴趣

点击查看

曼哈顿距离（Manhattan Distance)

**曼哈顿距离（Manhattan Distance)**即两点之间在网络格子上的距离，它是无法通过对角线移动到达目标点时，两点坐标差的绝对值之和，即x轴上的距离和y轴上的距离的和。在二维平面坐标系中，曼哈顿距离可以表示为：

h(p,q) = |p_x - q_x|+|p_y - q_y|

####欧几里得距离（Euclidean Distance）
**欧几里得距离（Euclidean Distance）**则是两点之间的直线距离，它是在平面直角坐标系上连接点两点之间的线段的长度，即两点距离的平方根。在二维平面坐标系中，欧几里得距离可以表示为：

h(p,q) = \sqrt{(p_x - q_x)^2 + (p_y - q_y2}

曼哈顿距离和欧几里得距离的平均值

切比雪夫距离

切比雪夫距离或是 $L_∞$ (无穷范数) 度量是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。
若二个向量或二个点 $p$ 、 $q$ ，其座标分别为 $p_i$ 及 $q_i$ 则两者之间的切比雪夫距离定义如下：

D_{Chebyshev}(p, q) := max_i(|p_i - q_i|)

这也等于以下 $L_p$ 度量的极值：

\lim_{k\to0}(\sum_{i=1}^n{|p_i-q_i|}^k)^{1/k}

因为笔者实力有限，对于切比雪夫距离理解不够，其他有错的地方还请您见谅，您可以参阅**这篇文章**

总结BFS、Dijkstra、A*

总的来说，BFS算法适用于无加权图或权值相等的有加权图，Dijkstra算法适用于权值为正的有加权图，A*算法虽然时间复杂度较高，但可以更快地找到最短路径或近似最短路径，适用于一些对路径搜索灵活度和效率要求较高的情况下

IDA*

**IDA***本质上就是A*加上了迭代加深的方式，每次限制深度，在每个深度上进行搜索，以尽可能地搜索所有可能的组合。与A*不同的是，它更像是DFS的一种优化，在处理较宽或无限宽的树时，A*就显得力不从心了，IDA*虽然在迭代加深时会重复多次搜索，但带来的收益也是不容小觑的，在信息学竞赛中，IDDFS算法常用于解决搜索深度未知或搜索深度很深的问题。