基于边权的最小权重3路顶点覆盖算法  

Minimum weight 3-path vertex cover algorithm based on edge weighting

作　　者：范鼎 刘春颜 李洋 赵蕴龙 FAN Ding;LIU Chunyan;LI Yang;ZHAO Yunlong(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China;Unmanned Aerial Vehicles Research Institute,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,江苏南京211106 [2]南京航空航天大学无人机研究院,江苏南京211106

出　　处：《应用科技》2024年第4期69-74,共6页Applied Science and Technology

基　　金：国家重点研发计划项目(2022ZD0115403);国家自然科学基金项目(62072236).

摘　　要：城际仓储选址通常可以转化为顶点覆盖问题,顶点覆盖问题是一种经典的NP难问题。针对最小权重3路顶点覆盖问题,设计了基于边权和顶点度的贪心策略,构建了1个两阶段的最小权重3路顶点覆盖算法。通过与2种较优的最小权重3路顶点覆盖算法进行对比实验分析可知,本文提出的算法在城际物流仓储选址问题中具有较好的效果,最小权重和分别减少了3.34和1.13个百分点。Inter-city warehousing site selection can usually be transformed into vertex cover problem,which is a classical NP-hard problem.For the minimum weight 3-path vertex cover problem,this paper designs a greedy strategy based on edge weight and vertex degree,and constructs a two-stage minimum weight 3-path vertex cover algorithm.By comparative experiment and analysis with two better minimum weight 3-path vertex cover algorithms,it can be seen that the algorithm proposed in this paper has a better effect in the inter-city logistics warehousing site selection problem,and the sum of minimum weight is reduced by 3.34 and 1.13 percentage points respectively.

关 键 词：顶点覆盖 3路顶点覆盖 最小权重3路顶点覆盖 组合优化 图论 边权策略 物流建仓 贪心策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]