.png){kind=icon}
返回
Revisiting search methods for the Bounded-Diameter Minimum Spanning Tree Problem
.png){kind=icon}
PRE
AI
DOI：10.1051/ro/2025008.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
有界直径最小生成树问题（BDMSTP）的定义如下：给定一个图G，其中每条边xy具有正成本wxy，目标是找到一个最优生成树，其直径不超过给定的正整数D≤2。BDMSTP的应用出现在电信网络和光纤项目中、数据压缩问题以及分布式系统设计中。本研究重新审视了BDMSTP的搜索方法，并提出了局部搜索移动的不同组合，旨在选择高效的移动集合并改进文献中找到的解的质量。对于来自广泛使用的OR-Library的小型50节点和100节点实例，我们获得了精确解，其最优值此前未知。解决这些较简单案例后，我们随后集中精力解决更具挑战性的OR-Library图实例，包含250、500和1000个节点。选择高效搜索移动集合的过程是通过将不同的局部搜索版本（基于变邻域下降法）封装在ILS方法中进行的。还提出了一些新的邻域。计算测试表明，这些邻域使所提出的ILS方法能够获得比文献中呈现的更好的结果。
Keyword:
Spanning tree
Bounded-Diameter Minimum Spanning Tree
Iterated Local Search (ILS)
heuristics
期刊
R
IF:
2.1
论文数:
103
被引数:
0
机构
引用论文
分享收藏(Meta-)Heuristic Separation of Jump Cuts in a Branch&Cut Approach for the Bounded Diameter Minimum Spanning Tree Problem(元-)启发式方法在分支切割法中的应用，用于解决有界直径最小生成树问题中的跳跃切割分离
PREAI
分享收藏Serial and parallel memetic algorithms for the bounded diameter minimum spanning tree problem.png)
EXPERT SYSTEMS
EXPERT SYSTEMSIF2.3
PREAI
分享收藏
查看更多内容