搜索 (计算机)
在人工智能中，搜索问题一般包括两个重要的问题：
- 搜索什么：通常指目标
- 在哪里搜索：即搜索空间，通常指一系列状态的汇集，因此也称为状态空间
目录 |
[编辑] 搜索方式
按是否使用启发式信息分
- 启发式搜索
- 盲目搜索
按问题的表示方式分
- 状态空间搜索
- 与/或树搜索
[编辑] 搜索策略
[编辑] 宽度优先搜索
宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标，则算法中止。属于盲目搜索。 宽度优先搜索的实现一般采用open-closed表。
[编辑] 深度优先搜索
深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点，然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的，也不是最优的。 有时候，某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的，当每次运用向上、向下、向左、向右移动空格的算符时，可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时，由于应用的算符基本一致，还会产生重复，所以为了节约时间和存储空间，往往在宽度优先算法中设立一个机制，用来删除这些重复的节点，以提高效率。
[编辑] 迭代加深搜索
对深度优先搜索进行了一定改进，对搜索树的深度进行控制，即有界深度优先搜索。
但是深度限制值d的选取是一个问题，因此试图尝试所有可能的深度限制，即在找到目标之前，通过迭代不断增大d以保证完备性和最优性。
[编辑] 启发式OR图搜索算法
[编辑] AND-OR图启发式搜索
一个特殊问题：博弈
[编辑] 约束满足搜索
搜索策略还可以指在使用搜索引擎中所使用的策略，它通常是搜索之母，一个好的搜索过程必定有一个好的搜索策略来支持。
[编辑] 评价准则
- 完备性
- 时间复杂性
- 空间复杂性
- 最优性
