程序设计

 翻译样例中心 >> 电信翻译样例 >> 程序设计

翻译样例: 大规模邻域搜索技术调查
版权信息   版权信息

邻域搜索算法设计中的一个关键问题是邻域结构的选择,即邻域是如何确定的。选择方式大体上就确定了这个邻域搜索算法是否能得到高精度的解,还是仅仅得到比较差的局部最优解。据粗略的计算,邻域越大,得到的局部最优解越好,而得到的最终解的精确度越高。同时,邻域越大,每步迭代的时间越长。由于人们常常从不同的起始点多次运行邻域搜索算法,较长的执行时间将使单位时间的运行次数降低。因此除非可以以一种更加有效的方法进行搜索,一个较大的邻域不一定能够产生一个更有效的启发式算法。

例如,若将解线性规划问题的单纯型法视为一种邻域搜索算法,则列变换就是一种很大规模邻域的搜索方法。同样的,用于解决网络流问题的增量技术也可以归于很大规模邻域的搜索方法。解决最小费用流问题取消负费用回路的算法,以及解决指派问题的增广路径技术就是两例。

在从路径S到T路径的转移中,Lin-Kernighan启发式算法允许更换n条边,即武断地说d(S,T)等价于k=2n。算法开始时,从原路径T1删除一边得到一条Hamiltonian回路T2。此后,T2的一个末节点保持不变,直到迭代结束。选择另一个末节点开始进行搜索。偶数次操作插入一边进入Hamiltonian回路T2j,该回路与不固定的径与环T2j+1的末端节点相近。迭代的奇数次操作从当前径与环T2j-1删除一边得到一条Hamiltonian回路T2j。从任意Hamiltonian回路T2j,通过加入2个末节点可以暗中得到一个可行路S2j。在Lin-Kernighan算法结束时,得到了一个新的基本路径Si,使对于所有j都有f(Si)=f(S2j)。

收稿邮箱: sotrans@126.com
QQ: 1169561052    MSN: jesczhao@hotmail. com

最新翻译样例

相关翻译样例

专业英语词汇频道