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

扫码查看

原文链接

万方数据
维普

中文摘要：城际仓储选址通常可以转化为顶点覆盖问题,顶点覆盖问题是一种经典的NP难问题.针对最小权重 3 路顶点覆盖问题,设计了基于边权和顶点度的贪心策略,构建了 1 个两阶段的最小权重 3 路顶点覆盖算法.通过与 2 种较优的最小权重 3路顶点覆盖算法进行对比实验分析可知,本文提出的算法在城际物流仓储选址问题中具有较好的效果,最小权重和分别减少了3.34和1.13 个百分点.

外文标题：Minimum weight 3-path vertex cover algorithm based on edge weighting

外文摘要：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.

外文关键词：

vertex cover3-path vertex coverminimum weight 3-path vertex covercombination optimisationgraph theorystrategy with edge-weightlogistics warehousinggreedy strategy

作者：

范鼎、刘春颜、李洋、赵蕴龙

展开 >

作者单位：

南京航空航天大学计算机科学与技术学院,江苏南京 211106

南京航空航天大学无人机研究院,江苏南京 211106

关键词：

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

基金：

国家重点研发计划项目国家自然科学基金项目

项目编号：

2022ZD011540362072236

出版年：

2024

DOI：

10.11991/yykj.202311015

应用科技

哈尔滨工程大学

应用科技

CSTPCD

影响因子：0.693

ISSN：1009-671X

年,卷(期)：2024.51(4)