搜索算法可谓是在算法领域必不可少且比较基础的算法，其中搜索算法里面涉及到了很多具体的搜索算法，下面我们将会进行一一介绍。它主要用在图或者树当中，通过遍历所有可能的候选解来寻找最优解或满足条件的解。搜索算法可以应用于各种领域，包括人工智能、优化问题、路径规划等。
以下是一些常见的搜索算法：
1. 深度优先搜索（Depth-First Search, DFS）：
- 从起点开始，沿着一个方向深入搜索，一条路走到头，碰壁后返回，换一条路再走，尝试其他方向，返回的操作叫做回溯。
- 适用于目标节点较深的树结构搜索。
2. 广度优先搜索（Breadth-First Search, BFS）：
- 从起点开始，逐层搜索所有邻居节点，直到找到目标节点，类似于一个中心点向四周扩散的操作。
- 适用于目标节点距离起点较近的搜索。
3. 最佳优先搜索（Best-First Search）：
- 根据启发式信息，优先搜索最有潜力的节点。
- 常用于路径规划和人工智能中的决策过程。 - 在算法题当中一般不会使用的。
4. A*搜索算法（A* Search Algorithm）：
- 结合了广度优先搜索和最佳优先搜索的优点，使用启发式函数评估每个节点的重要性，算法较难，但是比起dfs、bfs更加有效。
- 启发式函数通常是目标函数的估计值，用于指导搜索方向。 - 算法难度比较大，可选择性学习。
5. Dijkstra算法：
- 用于图搜索，用于单源路径最短路问题，找到从起点到图中所有其他节点的最短路径。
- 适用于权重非负的图，边权为负数不可以使用，会得到错误的结果。
6. Bellman-Ford算法：
- 用于在加权图中找到从单个源点到所有其他节点的最短路径可以处理负权重边。
7. Floyd-Warshall算法：
- 计算图中所有节点对之间的最短路径，属于dijkstra算法的延申，起点可以是任意的。
- 适用于密集图。 - 时间复杂度O(n^3)，经典三重for循环遍历。
8. 贪婪算法（Greedy Algorithm）：
- 在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法，就是我们口中常说的贪心算法，每一步的最优导致全局最优。
9. 回溯算法（Backtracking）：
- 通过试错的方式尝试分步解决问题。在分步解决问题的过程中，当它通过试探发现现有的分步答案不能得到有效的正确解答时，它将回溯返回上一步或者几步，然后尝试其他可能的分步答案，在dfs算法常用，一条路走到头，需要返回，就是回溯。
10. 遗传算法（Genetic Algorithm）：
- 受自然选择和遗传学启发的搜索算法，通过迭代过程中的选择、交叉、变异等操作来优化解。
11. 模拟退火算法（Simulated Annealing）：
- 一种概率型算法，用于在给定的大解空间内寻找问题的近似最优解，通过模拟物理退火过程来避免陷入局部最优。
下面以下面的题为例子，带大家感受一下搜索算法——DFS算法的思想以及实现。
试题 算法训练 数字游戏
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
第1行为两个正整数n，sum
输出格式
一个1～N的一个排列
样例输入
4 16
样例输出
3 1 2 4
数据规模和约定
0<n<=10
这是一道搜索题，肯定会想到DFS，思路如下：
已知N与sum，就用sum反推原数字，就是求由1—N的数字顺序，如何得到最后的sum。
如n=4时，会有4个数字组成，那么我的每一个数字都从1--4去遍历一遍，得到解。
字典序问题，由于我的第一个数是从1开始搜索的，若得到一组解不成立，回溯回去，字典序也是最小的，也可以这样说，得到的第一组解向后，字典序是不断增大的，比如举个例子：1 2 3 4，回溯回去的话，下一个1 2 4 3，很明显下一个的字典序要大于前一个的字典序，再向下走1 3 2 4----1 3 4 2，......规律是不断增大的，可以得到只要找到第一组解就是最优解。
#include<stdio.h> int n, sum; int flag = 0;//判断是否找到了最优解 int a[15]; int b[15];//记录i是否被使用过 int c[15]; void dfs(int step) { int i, j; if (step == n + 1) {//一组解结束条件，下面判断这组解是否等于sum for (i = 1; i <= n; i++) {//把a[i]数组复制给c[i],防止改变a[i]数组 c[i] = a[i]; } //把相邻的两个数不断相加的操作 for ( i = 1; i <= n - 1; i++)//由于最后只得到最后一个数，所以有n-1次 { for ( j = n; j > i; j--) { c[j] = c[j] + c[j - 1]; } } //若得到的最后一个数==sum,并且之前没有找到最优解，就认定此数组为最优解 if (c[n] == sum && flag == 0) { for ( i = 1; i <= n; i++) { printf("%d ", a[i]);//输出 } flag = 1;//已经找到最优解了，不需要继续向下寻找了 } return; } //常规搜索找解 for ( i = 1; i <= n; i++) { if (b[i] == 0)//i没有被使用过 { if (flag== 1)//如果之前已经找到最优解了，不需要继续寻找，直接退出 return; a[step] = i; b[i] = 1;//标记已经使用过了 dfs(step + 1); b[i] = 0;//回溯回去，再标记未使用，用于下一组的搜索解 } } return; } int main() { scanf("%d%d", &n, &sum); dfs(1); return 0; }
搜索是算法之中最基础的部分，是每一位算法初学者的首选，文章尚有不足，若有错误的地方恳请各位大佬指出。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
