{< katex />}

一、基础搜索算法 #

1. 线性搜索 #

• 顺序搜索
• 哨兵线性搜索
• 概率线性搜索

2. 二分搜索 #

• 标准二分搜索
• 插值搜索
• 指数搜索
• 三分搜索

3. 哈希搜索 #

• 直接地址法
• 除留余数法
• 开放地址法
• 链地址法

二、树结构搜索算法 #

1. 二叉搜索树 #

• 平衡二叉搜索树
• AVL树
• 红黑树
• B树与B+树

2. 多路搜索树 #

• 2-3树
• 2-3-4树
• B*树
• Trie树

3. 空间划分树 #

• 四叉树
• 八叉树
• KD树
• R树

三、图搜索算法 #

1. 深度优先搜索 #

• 递归DFS
• 迭代DFS
• 回溯算法
• 记忆化搜索

2. 广度优先搜索 #

• 标准BFS
• 双向BFS
• 多源BFS
• 0-1 BFS

3. 启发式搜索 #

• A*算法
• IDA*算法
• 最佳优先搜索
• 波束搜索

四、字符串搜索算法 #

1. 单模式匹配 #

• 朴素算法
• KMP算法
• Boyer-Moore算法
• Sunday算法

2. 多模式匹配 #

• AC自动机
• Wu-Manber算法
• Commentz-Walter算法

3. 近似匹配 #

• 编辑距离算法
• 模糊匹配
• 正则表达式匹配

五、高级搜索技术 #

1. 剪枝优化 #

• Alpha-Beta剪枝
• 分支限界法
• 约束传播
• 对称性剪枝

2. 局部搜索 #

• 爬山算法
• 模拟退火
• 禁忌搜索
• 遗传算法

3. 元启发式搜索 #

• 粒子群优化
• 蚁群算法
• 人工蜂群算法
• 差分进化算法

六、并行与分布式搜索 #

1. 并行搜索算法 #

• MapReduce搜索
• 多线程搜索
• GPU加速搜索
• 向量化搜索

2. 分布式搜索 #

• 倒排索引
• 布隆过滤器
• 一致性哈希
• 分布式哈希表

七、应用领域特定搜索 #

1. 数据库搜索 #

• 索引扫描
• 全表扫描
• 连接查询优化
• 查询重写

2. 信息检索 #

• 向量空间模型
• 概率模型
• 语言模型
• 语义搜索

3. 游戏AI搜索 #

• 极小化极大算法
• 蒙特卡洛树搜索
• 期望极大化搜索
• 实时启发式搜索

八、搜索算法复杂度分析 #

1. 时间复杂度分析 #

• 最坏情况分析
• 平均情况分析
• 摊还分析
• 渐进分析

2. 空间复杂度分析 #

• 辅助空间需求
• 内存访问模式
• 缓存友好性
• 空间-时间权衡

3. 实际性能考量 #

• 常数因子优化
• 分支预测优化
• 预取技术
• 算法工程实践