论文标题
基于群集最短树的启发式申请算法
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem
论文作者
论文摘要
随机贪婪算法（RGAS）是解决问题的有趣方法，其结构尚不清楚，以及组合优化的问题，结合了随机过程和贪婪的算法。本文介绍了一种新算法，该算法结合了RGA的主要特征和最短的路径树算法（SPTA），以处理群集的最短Path树问题（库）。在我们的算法中，SPTA用于确定每个群集中的最短路径树，而RGA的特征与SPTA的搜索策略之间的组合用于构建连接簇的边缘。为了评估所提出的算法的性能，选择了欧几里得基准。实验研究表明，与某些现有算法相比，该算法的优势。我们还分析了参数对算法性能的影响。
Randomized Greedy Algorithms (RGAs) are interesting approaches to solve problems whose structures are not well understood as well as problems in combinatorial optimization which incorporate the random processes and the greedy algorithms. This paper introduces a new algorithm that combines the major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the Clustered Shortest-Path Tree Problem (CluSPT). In our algorithm, SPTA is used to determine the shortest path tree in each cluster while the combination between characteristics of the RGAs and search strategy of SPTA is used to constructed the edges connecting clusters. To evaluate the performance of the proposed algorithm, Euclidean benchmarks are selected. The experimental investigations show the strengths of the proposed algorithm in comparison with some existing algorithms. We also analyze the influence of the parameters on the performance of the algorithm.
