对比三种算法解决互可见问题，发现遗传算法在实际中表现最佳。
Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem
- 用随机、超图和遗传算法求解互可见问题
- 小图时结果接近理论极限，大图时差距明显
- 遗传算法在已知最优解上表现最稳定
互可见（MV）问题是NP完全的，尽管有理论研究，但缺乏对其实际行为的实证分析。本文在多种合成图数据集上实现并评估了三种不同算法：直接随机启发式、基于超图的近似算法和遗传算法，包括具有解析已知μ(G)值的图和通用图模型。结果显示，在较小图上，各算法获得的MV集合大小与理论边界一致；但在较大实例中，解的大小显著偏离理论极限，且缺乏紧致界，使绝对质量评估困难。然而，在已知最优解的图上验证显示，遗传算法及其他启发式方法在测试中表现最佳。
原文摘要 · Abstract (English)
The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms -- a direct random heuristic, a hypergraph-based approximation, and a genetic algorithm -- on diverse synthetic graph datasets, including those with analytically known $μ(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。