基于变邻域搜索算法的边度量维数问题研究

发布时间：2022-01-25 12:39

　　图的边度量维数问题是图论和组合优化研究的重要问题之一,越来越多的领域涉及此问题,包括网络发现与核实、机器人导航和化学等.设G＝（V,E）是一个简单连通图,顶点子集B（?）V,如果图G的任意两条边被B中某些顶点区分,则称B是图G的边度量生成集.图G中基数最小的边度量生成集称为边度量基;边度量基的基数称为边度量维数.求解图的边度量维数问题在一般情况下是NP-难问题.本文研究了图的边度量维数问题,给出了整数线性规划模型,设计了变邻域搜索算法,得到了变邻域搜索算法在Hamming图、超立方体图和默比乌斯梯图上的应用结果. 

【文章来源】：河北师范大学河北省

【文章页数】：36 页

【学位级别】：硕士

【部分图文】：

基本变邻域搜索算法

必要性如果∑1=1∑=+1=0,则=0,对任意的1<.由于∑=1(,),·1,存在至少一个使得(,)=(,),则由定义知′是一个边度量生成集.限制条件(2.6)保证了|′|=,定理即证.2.2算法流程和实现本节介绍求解问题的具体算法.根据1.3.4节给出的一般变邻域搜索算法的基本步骤,先给出求解问题的算法流程图,然后对算法进一步分析.我们给出边度量维数问题的变邻域搜索算法的流程图(见图2.2).下面进一步分析算法.(1)初始解构造.一般初始解的生成可以通过随机生成或者由经验和其他算法得到,对于边度量维数问题的初始解的构造,从空集开始,依次随机选取中的一个顶点添加到中,直到为边度量生成集.(2)邻域结构.由事实可知不同的邻域结构会得到不同的可行解,一个邻域结构内的最优解不一定是另一个邻域结构的最优解,为了使得到的解更接近于最优解,因此依据不同的问题要设计不同的邻域结构.对于边度量维数问题,我们可以通过交换集合中的个元素得到需要的邻域.例如,当=1,={1,2,3,4,5},={1,2,3},={4,5},1()={{4,2,3},{1,4,3},{1,2,4},{5,2,3},{1,5,3},{1,2,5}},即1()为用中的一个元素替换中的一个元素得到的新集合所构成的一个集合.=1时邻域构造可以用图2.1表示.图2.1:邻域构造(=1时)显然,小于或等于||.不难发现,随着的增大邻域结构的基数不断增大,即||=()·()<(+1)·(+1)=|+1|,<21+2.13

3.2超立方体图本节首先介绍超立方体图,接着给出由变邻域搜索算法得到的一些结果.当Hamming图,中=2时即为超立方体图,中两个顶点的距离是对应不同坐标分量的个数.显然有2个顶点,·21条边.图3.1:超立方体图引理3.1[24]对于-正则图,dim()1+log2.利用第二章设计的变邻域搜索算法,求解超立方体图的边度量维数得到一些结果,见表3.2,其中表3.2的构造与表3.1相同.表3.2:超立方体图的算法结果||||()38123,5,830.372416326,13,1630.674532806,16,23,3042.9196641929,18,34,58,62520.65671284484,33,65,98,114,1226244.106825610241,7,27,150,169,2536328.794由表3.2,我们可以知道dim(3)3,因为3为三正则图,由引理3.1可知dim(3)1+log23,又log23=2,所以有dim(3)=3,即算法得到的边度量生成集就是边度量基.3.3默比乌斯梯梯图本节首先应用算法得到默比乌斯梯图的一些结果,然后应用组合方法给出默比乌斯梯图的边度量维数的界,并与算法得到的结果进行对比.定义3.2[17]设圈=(,),5.默比乌斯梯梯图的顶点集为,两个顶点与之间有边当且仅当两个顶点,在圈中的距离等于圈的直径.22

【参考文献】：
期刊论文
[1]变邻域搜索算法综述[J]. 董红宇,黄敏,王兴伟,郑秉霖.  控制工程. 2009(S2)



本文编号：3608552