查看“︁搜索算法”︁的源代码

{{NoteTA
|T=zh-hans:搜索算法; zh-hant:搜尋演算法;
|G1=IT}}

{{多個問題|
{{request translation}}
{{copyedit|time=2018-03-29T03:32:43+00:00}}
}}
在[[计算机科学]]中，'''搜索算法'''是解决'''搜索问题'''的任何[[算法]]，即检索存储在某个[[数据结构]]中的信息，或者在问题的[[可行域]]中计算的信息。这种结构的例子包括但不限于[[链表]]，[[数组]]或[[搜索树]]。合适的搜索算法通常取决于正在搜索的[[数据结构]]，并且还可能包括有关[[数据]]的先前知识。搜索还包含查询数据结构的算法，例如[[连接|SQL SELECT]]命令<ref>{{Cite web|title=How Search Engine Algorithms Work: Everything You Need to Know|url=https://www.searchenginejournal.com/search-engines/algorithms/|access-date=2022-05-05|last=Shares|first=1 7k|work=Search Engine Journal|language=en|archive-date=2022-06-11|archive-url=https://web.archive.org/web/20220611034418/https://www.searchenginejournal.com/search-engines/algorithms/}}</ref>。

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

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

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

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

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

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

===[[迭代加深搜索]]（ID搜索）===
对深度优先搜索进行了一定改进，对搜索树的深度进行控制，即[[有界深度优先搜索]]。

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

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

===啟發式OR图搜索算法===
*[[爬山算法]]
*[[模拟退火算法]]
*[[最好优先]]
*[[通用图]]
*[[A*]]

===AND-OR图啟發式搜索===

'''一个特殊问题'''：[[博弈论]]

===约束满足搜索===

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

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

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

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

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

一个重要且广泛研究的子类是图算法，特别是图遍历算法，用于查找给定图中的特定子结构 - 例如子图，路径，电路等。例子包括[[Dijkstra算法]]，[[克鲁斯克尔演算法|Kruskal算法]]，[[K-近邻算法|最近邻算法]]和[[普林姆算法|Prim算法]]。

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

<!--
==搜索功能的最大值==

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

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

== 引用 ==
[[Category:搜尋演算法| ]]