xdhu 3
5.5 局部搜索
基于局部搜索的算法的主要思想是：从一个初始可行解
开始，在一定范围内寻找一个更好的解；然后再从这个可行
解开始，不断地重复这个过程，直到无法找到更好的解为止。
一般来讲，任给一个可行解 x ，我们称 z 是它的一个相邻可
行解如果 z 与 x 的几何距离很近，或者它们具有非常相似的
离散结构。
给定一个可行解 x，局部搜索算法试图在它的所有相邻可行
解中找到一个具有更好的度量函数（比如优化问题的目标函数）
的解。当算法找到了一个可行解，与它相邻的可行解的度量函
数值都不比它的度量函数值好，算法就终止，并输出这个可行
解。然而，尽管输出的可行解无法再改进（没有比它更好的相
邻可行解），但是通常它只是一个局部最优解，而非全局最优
解。
评论0