局部搜索算法
组合问题由于其可能的解的数量十分庞大，无法用穷举法求解最优解。
局部搜索算法旨在减少复杂度的情况下寻找最优解，尽管其不一定能够找到全局最优解，但是往往可以找到满意的局部最优解。
爬山法
类似于盲人爬山，无法看到全局的景象，但是有拐杖可以探测临近的区域。
每一次使用拐杖在周围扫一圈，把这一圈上每一个点的高度与自己脚底的高度比较，找到距离脚底最高的那个点所在的方向前进。
重复以上过程。直到扫描周围的一圈，发现都低于自己脚底的高度。
此时位于局部最高点。
核心思想
邻域内找一个最优的结果，接受它，再以此为新的起点，重复这个过程。
领域的概念
上文中对于领域的现实类比案例是容易理解的， 但是在组合优化问题中，领域是指什么呢？
对解 (S) 经过一些简单变换后，得到的另一个解称作解 (S) 的邻居，解 (S) 所有邻居的集合称作解 (S) 的邻域。
邻域举例
-
皇后问题：每行每列有且只有一个皇后，每对角线至多一个皇后。
(S={S_i}) 表示一个可能解，其中 (S_i) 表示在第 (i) 行，第 (S_i) 列有一个皇后。
如四皇后问题的一个解： (S=(2, 4, 1, 3))
任意交换两个皇后的位置获得一个解的邻居，则((2,4,1,3))的所有邻居，也就是邻域为：
({(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)})
-
旅行商问题
-
常规交换法
序列 (S) 是对于 (n) 个城市的访问顺序，将其中两个城市的访问顺序进行调换，则得到一个邻居 (S’).
常规交换法的路线改变示例图：
-
逆序交换法
选取两个城市 (x_i) 和 (x_j) ，将这两个城市之间的序列进行逆序操作。( (x_i) 和 (x_j) 是不变的 )
逆序交换法的路线改变示例图：
-
局部搜索算法描述
- 随机的选择一个初始的可能解 (x_0in D) ，(x_b=x_0) ，(P=N(x_b)) ；
- 如果 (P) 不为空，则
- Begin
- 选择 (P) 的一个子集 (P’) ，(x_n) 为 (P’) 中的最优解
- 如果 (f(x_n)，则 (x_b = x_n)，(P=N(x_b))，转2；
- 否则 (P=P-P’)，转2.
- End
- 输出计算结果
- 结束
其中：
-
(N(x))函数用于获取组合 (x) 的邻域。
-
这里的算法比上文的爬山法更具一般性，没有直接在领域中寻找局部最优解，而是在邻域的子集中寻找最优解。
-
(f(x))用于计算并比较组合 (x) 的优良性，从而最终可以选出局部最优解。在旅行商问题中可以是路径的长度，在0-1背包中可以是背包中物品的价格。
机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
