kernighanlin算法

㈠ “扫描法”的名词解释是什么

名词解释：采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线。

㈡ 复杂网络理论及其应用的作品目录

第1章引论
1.1引言
1.2复杂网络研究简史
1.3基本概念
1.4本书内容简介
参考文献
第2章网络拓扑基本模型及其性质.
2.1引言
2.2规则网络
2.3随机图
2.4小世界网络模型
2.5无标度网络模型
2.6局域世界演化网络模型
2.7模块性与等级网络
2.8复杂网络的自相似性
参考文献
第3章Internet拓扑特性及建模
3.1引言
3.2Internet的拓扑特性
3.3随机图产生器
3.4结构产生器
3.5基于连接度的产生器
3.6多局域世界模型
3.7各类模型的定性比较
参考文献
第4章复杂网络上的传播机理与动力学分析
4.1引言
4.2复杂网络的传播临界值理论
4.3复杂网络的免疫策略
4.4复杂网络的传播动力学
4.5计算机病毒在Internet上的传播
4.6复杂网络中的其他传播现象
参考文献
第5章复杂网络上的相继故障
5.1引言
5.2复杂网络相继故障的动态模型分析
5.3基于耦合映象格子的相继故障模型
参考文献
第6章复杂网络中的搜索
6.1引言
6.2社会网络搜索
6.3几种复杂网络搜索策略分析
6.4P2P网络中的搜索
6.5复杂网络中的搜索和拥塞
参考文献
第7章复杂网络中的社团结构
7.1引言
7.2Kernighan—Lin算法
7.3谱平分法
7.4分裂方法
7.5凝聚算法
7.6派系过滤算法
参考文献
第8章复杂网络中的同步
8.1引言
8.2复杂网络的完全同步判据
8.3复杂动力网络的完全同步
8.4连续时间时变耦合网络完全同步
8.5其他网络完全同步判据
8.6复杂网络中各个因子与完全同步的关系
8.7改进复杂网络同步的方法
8.8复杂网络的相位同步
参考文献
第9章复杂动态网络的控制
9.1引言
9.2规则网络时空混沌的牵制控制
9.3无标度动态网络的牵制控制：鲁棒性与脆弱性
9.4一般复杂动态网络的牵制控制
9.5随机驱动下动态网络的有序性与动力学
参考文献
附录名词对照

㈢ 名词解释：扫描法。谢谢，急

Gillett和Miller于1974年所提出的求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，此方法属于先分群再排路线的方式[1]。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线[2]。扫描法分为两阶段性步骤：第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求点为起点，以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进行顾客的扫描分群。第二阶段：依据求解旅行商问题的算法，求解各顾客群的排程。

㈣ 社区检测（community detection）

社区检测（community detection）又被称为是社区发现，它是用来揭示网络聚集行为的一种技术。社区检测实际就是一种网络聚类的方法，这里的“社区”在文献中并没有一种严格的定义，我们可以将其理解为一类具有相同特性的节点的集合。

近年来，社区检测得到了快速的发展，这主要是由于复杂网络领域中的大牛Newman提出了一种模块度（molarity）的概念，从而使得网络社区划分的优劣可以有一个明确的评价指标来衡量。一个网络不通情况下的社区划分对应不同的模块度，模块度越大，对应的社区划分也就越合理；如果模块度越小，则对应的网络社区划分也就越模糊。

下图描述了网络中的社区结构：

Newman提出的模块度计算公式如下:

所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异，因为随机网络并不具有社区结构，对应的差异越大说明该社区划分越好。

Newman提出的模块度具有两方面的意义：

（1）模块度的提出成为了社区检测评价一种常用指标，它是度量网络社区划分优劣的量化指标；

（2）模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上，许多优化算法以模块度为优化的目标方程进行优化，从而使得目标函数达到最大时得到不错的社区划分结果。

当然，模块度的概念不是绝对合理的，它也有弊端，比如分辨率限制问题等，后期国内学者在模块度的基础上提出了模块度密度的概念，可以很好的解决模块度的弊端，这里就不详细介绍了。

常用的社区检测方法主要有如下几种：

（1）基于图分割的方法，如Kernighan-Lin算法，谱平分法等；

（2）基于层次聚类的方法，如GN算法、Newman快速算法等；

（3）基于模块度优化的方法，如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等

㈤ 扫描法的名词解释

扫描法 扫描法（Sweep Algorithm） 什么是扫描法 Gillett和Miller于1974年所提出的求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，此方法属于先分群再排路线的方式[1]。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线[2]。 扫描法的步骤 扫描法分为两阶段性步骤： 第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求点为起点，以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进行顾客的扫描分群。 第二阶段：依据求解旅行商问题的算法，求解各顾客群的排程。 Solomon于1983年将此方法应用于求解时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW），与原扫描法不同点在于第二阶段的求解各顾客群排程，其以插入法进行各顾客群的排程，并检查时间可行性，若有顾客点无法满足时间窗的约束，则先排除此顾客点。若所有的顾客群都以排入行程，则所有的顾客点都已被服服务，则完成路线的建构；若有顾客点尚未被服务，则沿原扫描方向，将剩余的尚未服务的顾客点重复进行扫描与插入的步骤，直到所有的顾客点都被服务。

㈥ 关于TSP，lin-kernighan的算法

此算法是把服务带你的集合分为2堆，如何通过计算从两堆中选取元素的方法计算成本。可以优化物流中的TSP问题。

㈦ 扫描法的介绍

Gillett和Miller于1974年所提出的求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，此方法属于先分群再排路线的方式[1]。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线[2]。

㈧ 社区检测算法（Community Detection）

社区检测（community detection）又被称为是社区发现，它是用来揭示网络聚集行为的一种技术。社区检测实际就是一种网络聚类的方法，这里的“社区”在文献中并没有一种严格的定义，我们可以将其理解为一类具有相同特性的节点的集合。

近年来，社区检测得到了快速的发展，这主要是由于复杂网络领域中的大牛Newman提出了一种模块度（molarity）的概念，从而使得网络社区划分的优劣可以有一个明确的评价指标来衡量。一个网络不通情况下的社区划分对应不同的模块度，模块度越大，对应的社区划分也就越合理；如果模块度越小，则对应的网络社区划分也就越模糊。

下图描述了网络中的社区结构：

Newman提出的模块度计算公式如下:

所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异，因为随机网络并不具有社区结构，对应的差异越大说明该社区划分越好。

Newman提出的模块度具有两方面的意义：

（1）模块度的提出成为了社区检测评价一种常用指标，它是度量网络社区划分优劣的量化指标；

（2）模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上，许多优化算法以模块度为优化的目标方程进行优化，从而使得目标函数达到最大时得到不错的社区划分结果。

当然，模块度的概念不是绝对合理的，它也有弊端，比如分辨率限制问题等，后期国内学者在模块度的基础上提出了模块度密度的概念，可以很好的解决模块度的弊端，这里就不详细介绍了。

常用的社区检测方法主要有如下几种：

（1）基于图分割的方法，如Kernighan-Lin算法，谱平分法等；

（2）基于层次聚类的方法，如GN算法、Newman快速算法等；

（3）基于模块度优化的方法，如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等

㈨ 什么是发现社区

究实际上是从子图分割问题演化而来，Kernighan-Lin 提出的二分算法使得子图分割问题逐渐成为当时图挖掘领域关注的重点。另外，在社会学领域，社会学家也发现社区结构在各种复杂网络中的普遍存在性。进入21世纪后，社区的研究开始被研究者所重视，而近年来随着社交网络的崛起，这一领域的关注度已大大提升。

是一种算法 来自职Q用户：董立

㈩ LKH（Lin-Kernighan heuristic ）一种求TSP的邻域搜索策略

PART I 引入

题主应该指的是1973年的针对TSP的LKH算法。LKH算法类似于k-opt方法，常见的2-opt作为一种local search的思想题主应该是知道的，（2-opt的基本变换2-interchange如下图）。

那么k-opt的过程，也可以element by element，也就可以通过不计顺序的δ-path之间的uv-switch来实现，每个合适的k-opt里面的exchange都是总和为正的增益值，那么其每一个合适的exchange的一部分都可以被uv-switch达到，所以可以令每次的G*都大于0，作为stoppingcriteria，从逻辑上来说是合理的，符合作者的element by element，在启发式所谓的exploitation上也有好的表现力。END

P.S element by element这种思想在其他的算法也有体现，比如遗传算法的改进上也有比如单位点交叉防止收敛解震动。

其他算法效能上的提升考虑，请依次阅读文献[2][1]及其他相关的资料。

综上，LKH是可以认为基于k-opt成功的改进，无论是运行的速度上，还是搜索的精度上。它在解决TSP问题上，速度和精度上仍旧有较好的表现。

水平有限，随缘回答，若有错误，请指出评论，谢谢！

参考文献：

理解算法框架内容，文献[1]是较好的参考资料，理解算法细节、讨论，可以参考文献[2]，其指出了backtracking的要求（从数值实验/作者思考的philosophy上指出：应该从最多几层开始backtracking，每层y_1, y_2contenders的数量如何，如何进一步refinements，每一次δ-path 变换中y_i怎么高效选取等问题）

[1] Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.Combinatorial Optimization

[2] S. Lin, B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem