导航：首页 > 互联网科技 >

LNS该如何理解

发表于：2025-01-25 作者：千家信息网编辑

千家信息网最后更新 2025年01月25日，本篇文章给大家分享的是有关LNS该如何理解，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。今天小编为大家讲解大规模邻域搜索(Large N

千家信息网最后更新 2025年01月25日LNS该如何理解

本篇文章给大家分享的是有关LNS该如何理解，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

今天小编为大家讲解大规模邻域搜索(Large NeighborhoodSearch 简称LNS)算法，接下来小编不绕弯子直奔主题，LNS实质上是通过交替使用destroy和repair两个方法逐步改善初始解。

那么究竟什么是destroy，什么是repair，这两个方法究竟怎么使用，别着急且听小编慢慢道来：

destroy顾名思义是"毁坏"的意思，repair是"修复"的意思。小编还是以5个城市的TSP问题为例讲解，假设初始解是12345。

第一步，我们对这个初始解使用destroy方法，小编使用最基本的随机选择几个城市的方法对初始解进行破坏，例如选择2和5，那么就把2和5这俩个城市从初始解拿掉，剩下的城市按照初始顺序依次排列，则变成134；第二步，我们使用repair方法对destroy后的解进行修复，即对134这个解进行修复，也就是将2和5这两个城市重新安排进134当中，这里可以从2和5种随机选择一个城市插入到134中，比如说我们选择2插入到134中，一共有3种可能：2134、1234、1324（1342和2134效果相同，故不重复），从这3个可能解中选择一个最好的，比如说1324最好，那我们就选择1324，然后再将5插入到1324中，则有4种可能：51324、15324、13524、13254，然后从这4个解中选择一个最好的解。当然小编讲解的都是最最最基本的destroy和repair思想。

下面小编给出LNS求解TSP问题的流程图