基于局部搜索原理的近似算法；基于动态规划的近似算法。

编辑中

基于局部搜索的近似算法

原理

工作过程：

1. 从任意可行解出发，搜索其邻域（通过对其进行局部修改），检查是否有更优的解存在（具有更优的解代价）

2. 如存在则移动至该解并继续执行局部搜索

3. 反之则意味着达到了一个局部优化解，输出局部优化解作为近似解。

关键：

1. 在搜索空间中如何定义邻域（邻居关系的选择和定义）；需要保证每次的局部搜索在多项式时间内完成。

   即怎么来得到邻域。

2. 在每一步中选择相邻解的规则。

   即怎么从获得的邻域中选择最优的。

   这决定了迭代次数，以及可否在有限步内找到局部最优解。

3. 初始的可行解如何选择。

与基于贪心的近似算法比较:

1. 相同：

   • 均是启发式规则

   • 均是做局部优化选择，不一定保证全局最优

2. 不同

   • 贪心的解是一步步构建的，每步通过选择当前最优来决定下一步

   • 局部搜索则是已经得到一个可行解，从这个解出发，通过对其局部、小的修改来产生新的可行解，使代价更优。

     局部搜索无法保证一定能够在多项式时间内找到局部最优解.

优缺点：

1. 优点：

   简单、灵活、易于实现

   对于大多数难计算问题不难设计一个局部搜索算法。

2. 缺点 ：

   容易陷入局部最优

   有随机的可能——解的质量难以保证，与初始解、邻域结构密切相关。

问题

1. 最大割问题

   问题描述：

   输入： 加权无向图$G(V,E)$，权值函数$W:E \to N$

   输出： $S \subseteq V$ ， 使得$\sum_{u \in S , v \in V - S}W(uv)$最大

   这里，就是把顶点集分为两个集合，$S$ 和$V-S$ ， 这就是一个割。 将$S$到$V-S$中的边的权值相加，就是割的代价。最大割就是找一个割，使得割的代价最大。

   最大割问题是一个NP完全问题。

   近似算法 ：

   需要定义$Cost(v , S)$ :

   v是一个顶点，S是一个顶点集合。

   如果v在S中，则$Cost(v,S)$表示v到S中其余顶点的权值和，减去v到$V - S$中顶点的权值和。（当然这些顶点间是要有边的）

   如果v在$V-S$中，则$Cost(v,S)$就表示v到$V-S$中其余顶点的权值和，减去v到S中顶点的权值和。

   如果$Cost(v,S)$为正，则说明如果我们交换v在两个集合的位置，得到的割的权值将变大！（因为第一项是内部权值和，第二项是到外部的权值和，如果交换，相比与未交换，到外部的权值就大了，割就更大了）

   1. 初始S集合，随意放入一个顶点到S中。

   2. 在所有顶点中，找$Cost(v,S) \gt 0$的顶点$v$，交换$v$在$S$ , $V-S$中的位置。

   3. 重复步骤2，直到找不到这样的顶点，则返回集合S，为近似解。