搜索算法

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

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

搜索功能常根据其复杂性或最大理论运行时间进行评估。例如，二分查找算法的最大复杂度为$O(\log n)$，即对数时间复杂度，这意味着查找搜索目标所需的最大操作次数是搜索空间大小的对数函数。其它评估方式包括完备性、空间复杂性、最优性。

应用

搜索算法的具体应用包括：

• 组合优化中的问题，例如：
  • 车辆路径问题，最短路径问题的一种形式
  • 背包问题：给定一组物品，每个物品都有一个重量和一个价值，确定每个物品在集合中的数量，使总重量小于或等于给定的极限，并且总价值尽可能大。
  • 护士排班问题
• 約束滿足問題，例如：
  • 地图着色问题
  • 填写数独或填字游戏
• 在博弈论中，尤其是組合博弈論中，选择下一步的最佳行动（例如极小化极大算法）
• 从一整套可能性中找到组合或密码
• 整数的因子分解（密码学中的一个重要问题）
• 搜索引擎优化（SEO）和网络爬虫的内容优化
• 通过改变工艺参数（如温度、压力和pH）来优化包括如化学反应在内的工业工艺
• 从数据库中检索记录
• 在列表或数组中查找最大值或最小值
• 检查给定值是否存在于一组值中

搜索策略

宽度优先搜索

宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标，则算法中止。属于盲目搜索。

深度优先搜索

深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点，然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的，也不是最优的。有时候，某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的，当每次运用向上、向下、向左、向右移动空格的算符时，可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时，由于应用的算符基本一致，还会产生重复，所以为了节约时间和存储空间，往往在深度优先算法中设立一个机制，用来删除这些重复的节点，以提高效率。

迭代加深搜索（ID搜索）

对深度优先搜索进行了一定改进，对搜索树的深度进行控制，即有界深度优先搜索。

在程序找到目标之前，通过迭代不断增大以保证完备性和最优性。虽然会有不少重复搜索，但是鉴于每增加一次d，则搜索的时间复杂度会以指数级别增加，所以重复搜索的时间可以忽略，亦可以与A*算法结合（即IDA*搜索算法）来剪枝。

迭代加深搜索通常用于那种搜索树又深又宽、但是解并不是很深的情况，这时广度优先搜索会超空间，而深度优先搜索会超时。这时迭代加深搜索很有用，可是说是在用递归方法在实现广度优先搜索。

啟發式OR图搜索算法

• 爬山算法
• 模拟退火算法
• 最好优先
• 通用图
• A*

AND-OR图啟發式搜索

一个特殊问题：博弈论

约束满足搜索

搜索策略还可以指在使用搜索引擎中所使用的策略，它通常是搜索之母，一个好的搜索过程必定有一个好的搜索策略来支持。

分类

对于虚拟搜索空间

主条目：求解器

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

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

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

对于给定结构的子结构

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

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

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

对于量子计算机

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