搜索算法

在计算机科学中，搜索算法是解决搜索问题的任何算法，即检索存储在某个数据结构中的信息，或者在问题域的搜索空间中计算的信息。这种结构的例子包括但不限于链表，数组数据结构或搜索树。合适的搜索算法通常取决于正在搜索的数据结构，并且还可能包括有关数据的先前知识。搜索还包含查询数据结构的算法，例如SQL SELECT命令^[1]。

搜索算法可以根据搜索机制进行分类。线性搜索算法以线性方式检查每个与目标关键字关联的记录。二进制或半间隔搜索，重复定位搜索结构的中心，并将搜索空间分成两半。比较搜索算法通过基于键的比较相继地消除记录来改进线性搜索，直到找到目标记录为止，并且可以按照定义的顺序应用于数据结构。数字搜索算法基于使用数字键的数据结构中的数字属性工作。最后，哈希根据散列函数直接将键映射到记录。在线性搜索之外进行搜索需要以某种方式对数据进行排序。

搜索功能也根据其复杂性或最大理论运行时间进行评估。例如，二进制搜索函数的最大复杂度为${\displaystyle {\mathsf {O}}\log({\text{n}})}$或对数时间。这意味着查找搜索目标所需的最大操作次数是搜索空间大小的对数函数。

对于虚拟搜索空间

主条目：Solver

在约束满足问题中使用搜索虚拟空间的算法，其目标是找到一组赋值给某些变量的值赋值，以满足特定的数学方程和不等式 。当目标是找到一个可以最大化或最小化这些变量的某个函数的变量赋值时，也会使用它们。针对这些问题的算法包括基本的强力搜索（也称为“天真”或“非信息”搜索）以及尝试利用关于该空间结构的部分知识的各种启发式算法，如线性松弛，约束生成，和约束传播。

一个重要的子类是局部搜索方法，它将搜索空间的元素视为图的顶点，其边由适用于该案例的一组启发法定义; 并且通过沿着边缘从物品移动到物品来扫描空间，例如根据最速下降或最佳优先标准，或者在随机搜索中。这一类包括各种通用的启发式方法，如模拟退火，禁忌搜索，A-团队和遗传编程，它们以特定的方式结合了任意的启发式方法。该类还包括各种树搜索算法，将元素视为树的顶点，并以某种特定顺序遍历树。后者的例子包括深度优先搜索和广度优先搜索等详尽的方法，以及各种基于启发式的搜索树修剪方法，如回溯和分支定界。与一般的metaheuristics不同，后者至多只能以概率的方式工作，如果给予足够的时间，许多这些树搜索方法都能保证找到确切的或最优的解决方案。这被称为“ 完整性 ”。

另一个重要的子类包括用于探索多玩家游戏（例如国际象棋或西洋双陆棋）的游戏树的算法，其中节点包括可能由当前情况导致的所有可能的游戏情况。这些问题的目标是找到提供最佳赢球机会的举措，同时考虑到对手的所有可能举措。当人类或机器必须作出连续的决定，其结果不完全在其控制之下时，例如在机器人指导或营销，财务或军事战略规划中，就会出现类似的问题。这种问题 - 组合搜索- 在人工智能的背景下进行了广泛的研究。这个类的算法的例子是极小极大算法，alpha-beta修剪，*信息搜索和A *算法。

对于给定结构的子结构

名称“组合搜索”通常用于查找给定离散结构的特定子结构的算法，例如图形，字符串，有限组等。术语组合优化通常用于当目标是找到具有某个参数的最大值（或最小值）的子结构时。（由于子结构通常在计算机中用一组带有约束的整数变量来表示，所以这些问题可以看作是约束满足或离散优化的特例;但它们通常是在一个更抽象的情况下制定和解决的，内部表示没有明确提及。）

一个重要且广泛研究的子类是图算法，特别是图遍历算法，用于查找给定图中的特定子结构 - 例如子图，路径，电路等。例子包括Dijkstra算法，Kruskal算法，最近邻算法和Prim算法。

这个类别的另一个重要子类是字符串搜索算法，它搜索字符串内的模式。两个着名的例子是Boyer-Moore和Knuth-Morris-Pratt算法，以及一些基于后缀树数据结构的算法。

搜索功能的最大值

1953年，美国统计学家杰克基弗设计了斐波纳契搜索，它可以用来找到单峰函数的最大值，并且在计算机科学中有很多其他应用。

对于量子计算机

还有为量子计算机设计的搜索方法，如Grover算法，即使没有数据结构或启发式的帮助，它在理论上也比线性或强力搜索更快。

引用

1. Shares, 1 7k. . Search Engine Journal. [2022-05-05]. （原始内容存档于2022-06-11） （英语）.