局部搜索（local search），理学-计算机科学技术-人工智能-机器学习-知识表示-案例推理-约束满足问题，一种基于迭代修改的求解优化问题的算法。局部搜索是一种求解最优化问题的启发式算法，在求解离散优化问题时往往有很好的性能。许多重要的最优化问题都是难解的，其中很多是NP难问题。对NP难问题，对进行精确求解需要的时间是随问题规模呈指数增长的。在实践中，人们一般使用启发式算法来近似求解这些困难问题，局部搜索就是最常见的方法之一。局部搜索的工作原理需要用几个概念来解释：解空间是一个包含所有候选解的集合（候选解具备解的形式但不一定要求是可解）。邻域关系是候选解集合上的一个二元对称关系，满足邻域关系的两个候选解互为邻居解。如果一个解的目标函数值比它所有的邻居解都更好或相等，则称它是局部最优解。如果一个解的目标函数值比任何其他解更好或相等，则称它是全局最优解。