每日 Arxiv

本页面整理了世界各地发表的人工智能相关论文。
本页面使用 Google Gemini 汇总而成，并以非盈利为基础运营。
论文版权归作者及相关机构所有，分享时请注明出处。

互可见性问题的启发式和近似算法的实证分析

Created by
  • Haebom

作者

Vanja Stojanovi c, Bor Panger\v{s}i\v{c}

大纲

为了解决 NP 完全相互可见性 (MV) 问题缺乏实证分析的问题，本文实现了三种算法（直接随机启发式、基于超图的近似和遗传算法），并在各种合成图数据集（包括具有分析已知 $\mu(G)$ 值的数据集）上对它们进行评估。

Takeaways, Limitations

•
对于小图，该算法始终能够实现符合理论界限的 MV 集大小。
•
对于大型实例，解决方案的大小与理论极限有显著偏差。
•
缺乏严格的界限使得绝对的质量评估变得困难。
•
已知最优图的验证结果表明，遗传算法和其他启发式算法表现最佳。
👍
Made with Slashpage