摘要
图的度量维数问题(MDP)是一类在机器导航、声呐系统布置、化学、数据分类等领域有重要应用的组合优化问题.针对该问题,本文通过引入图的分辨表存储结构,建立了非线性求解模型;同时,通过改进现有蚁群算法的参数设计,利用全局搜索和局部搜索相结合的策略,建立了求解模型的改进型蚁群算法.数值对比分析验证了算法的有效性:全局搜索和局部搜索的结合较大程度的改进了算法求解质量;在规则图上提高算法求解质量具有一定挑战;与遗传算法计算结果相比较,本文提出的算法不仅在求解质量方面有所提升,而且在最坏的情况下能为图提供极小分辨集.最后,本文探索了部分算法参数对算法求解质量的影响,并给出了进一步研究课题.
The metric dimension problem(MDP)of graphs is a kind of combinatorial optimization problem which has important applications in the fields such as machine navigation,sonar system layout,chemistry,and data classification.To solve this problem,we establish a non-linear model by introducing a resolving table storage structure for the considered graphs;simultaneously,an improved ant colony algorithm for solving the proposed model is established,by improving the parameters design of existing ant colony algorithms and leveraging the strategy of global search and local search.Numerical comparison analysis verifies the efficiency of the new algorithm:the combination of global search and local search improves the solution quality of the proposed algorithm to a large extent;it is a great challenge to improve the solution quality of the algorithm on regular graphs;compared with the results of genetic algorithm on MDP,the algorithm proposed in this paper not only improves the solution quality,but also provides the minimal resolving set for graphs in the worst case.Furthermore,we examine the influences of some parameters on the solution quality of the algorithm,and propose a further research topic.
作者
武建
赵海霞
WU Jian;ZHAO Hai-xia(School of Information and Computer Science,Taiyuan University of Technology,Taiyuan 030600;School of Applied Mathematics,Shanxi University of Finance and Economics,Taiyuan 030006;School of Statistics,Shanxi University of Finance and Economics,Taiyuan 030006)
出处
《工程数学学报》
CSCD
北大核心
2020年第6期699-718,共20页
Chinese Journal of Engineering Mathematics
基金
国家自然科学基金(11801335,11801334,11671296).
关键词
距离
度量维数
分辨集
蚁群算法
分辨表
分辨域
分辨度
0-1着色
distance
metric dimension
resolving set
ant colony algorithm
resolving table
resolving neighbour
resolving degree
0-1 coloring