文档介绍：: .
路径技术就是
两例。
在本调查中我们将很大规模邻域搜索算法分成互相重叠的3种。我们研究的第一种邻域
搜索算法是深度变量方法。该方法邻域成指数级增大，并利用启发式算法局部搜索这些邻域。
第二类包括基于改进算法的网络流理论。该邻域搜索算法使用网络流技术确定改善的相邻
解。最后，在第三类中我们将要讨论由子类或者在多项式时间内可解问题的约束引起的NP
难题。尽管我们通过解线性规划问题的单纯型法，以及解决网络流问题的增量技术介绍了大
第 2 页规模邻域搜索算法的概念，我们将不再论述线性规划问题。我们的问卷调查是将重点放在应
用很大规模邻域搜索算法解决NP难题的优化问题上。
本文结构如下。在第2部分，简要介绍局部搜索。第3部分讨论深度变量方法。第4部分
讨论基于网络流技术的很大规模邻域搜索算法。第5部分，给出一些可有效解决的NP难题的
组合优化问题特例，以及基于这些特例的很大规模邻域搜索算法。第6部分，将描述对给定
邻域进行局部搜索算法可能有所帮助的邻域指标。最后第7部分，介绍前面部分中一些算法
的计算性能。
：简述
首先，我们介绍一个组合优化问题以及邻域的概念。组合优化问题有不同的表述方式，
这都依靠可行解集的表示方法。这里，我们将可行解集表示为一个有限集的子集。形式化表
述如下：
令E={1，2，…，m}表示一个有限集合。一般地，对于集合S，令|S|表示集S的势。令
F⊆ 2E，其中2E表示集合E的全部子集的集合。F的元素叫做可行解。令f: → RF 。函数 f 叫
做目标函数。那么一个组合优化问题(COP)的例子可以表示为：
Minimize {f (S): ∈ FS }
假定F族没有将其元素完全列举出来，而是通过m次多项式的形式表示的。一个组合优
化问题的例子可用(F，f )表示。对于我们考虑的大多数问题，费用函数为线性，即有一个向
量f1，f2，…fm使所有可行集S，f (S)= f 。
∑ ∈Si i
假定是(F，f )表示一个组合优化问题。邻域函数是建立映射N: F → 2 E 的点。在该函
数下，每个∈ FS 都有对应的E的子集N(S)。不失一般性，假定 ∈ SNS )( ，那么集合N（S）
叫做解S的邻域。解* ∈ FS 叫做对于邻域函数N的局部最优解，若对于所有 ∈ SNS * )( 都有
* ≤ SfSf )()( 。若| N(S)|随着m的增加呈指数增长，邻域N(S)为指数邻域。在本文中，我们
将把重点放在指数邻域上，同时我们也讨论由于太大实际中不能精确搜索的邻域。例如，随
着m的增加（如大于100万），实际上并不能搜索有m3个元素的全部邻域。我们将应用很大规
模邻域搜索算法等邻域搜索技术。
对于两个解集 S 和 T，令 S-T 表示在 S 而不在 T 中的元素的集合。定义距离 d(S，
T)=|S-T|+|T-S|，即 E 中仅仅属于 S 或者 T 中的元素个数。有时，我们允许邻域含有不可行解。
例如，对于旅行销售员问题，可以允许邻域中含有删除一条边的路径。为了强调邻域中比实
际路径数量更多，我们常常在搜索中给出不可行解的一个组合描述。我们将这些不可行组合
结构叫做参考结构。例如，一条 Hamiltonian 路径可能就是一个参考结构。
邻域搜索算法（最小费用问题）可以用下面的3部分概念组成：
1) 根据具体问题定义的一个邻域图NG，NG为有向图，其每个节点对应于一个可行解
（并且/或者是非可行参考结构的例子），图的一条弧(S，T)满足T∈N(S)。
2) 每步迭代搜索邻域图的方法。
3) 确定在步骤2中选择