启发式和近似算法在相互可见性问题中的经验分析-计算机科学-机器学习-遗传算法.pdf

启发式和近似算法在相互可见性问题中的经

验分析

VanjaStojanović∗BorPangeršič

vs66277@student.uni-lj.sibp52226@student.uni-lj.si

FacultyofMathematicsandPhysics,FacultyofMathematicsandPhysics,

UniversityofLjubljanaUniversityofLjubljana

Jadranskaulica21Jadranskaulica21

SI-1000Ljubljana,SloveniaSI-1000Ljubljana,Slovenia

本摘要则我们说顶点是X-可见。这样的集合被称

为互视集合，如果每对都是X-可见的。

译NP完全的相互可见性(MV)问题目前缺乏对其实际行互视决策问题如下所述；给定一个图

中为的经验分析，尽管已有理论研究。本文通过实现并和集合，是否为一个互视集？DiStefano

2评估三种不同的算法——直接随机启发式算法、基于推导并证明了一个基于BFS的多项式时间算法来解决

v超图的近似算法和遗传算法——在各种合成图数据集

6这个问题。然而，一般来说，找到最大的这样的集合，

7上填补了这一空白，包括那些具有解析已知值和

0一般图模型的数据集。我们的结果显示，对于较小的即找到一个图的相互可见性数量是被证明为NP完全

1[4]。

0图，这些算法一致实现了与理论界限相符的MV集合

.对于相互可见性和相关问题，Bilò等人证明了强

7大小。然而，对于较大的实例，实现的解的大小显著偏

0不可近似性结果，表明对于直径至少为3的图，其不可

5离了理论限制；这一点，加上紧界缺失，使得绝对质量13

2评估复杂化。尽管如此，在已知最优图上的验证表明在内近似，并且对于直径为2的图是APX-Hard。

:

v虽然一些特定图类的确切解已知，但也有一个针对一

i遗传算法和其他启发式方法在测试的方法中表现最好。

x般图的多项式时间近似算法[1]。关于找到集合大小

r

a的精确下限在ApproximationAlgorithmUsingHyper-

KEYWORDS

graphs节中有详细讨论。

图论，相互可见性问题，贪婪启发式算法，遗传算法，

经验分析1.1动机

尽管对MV问题进行了理论分析，但尚未有公开尝试

1介绍对其进行实践中的经验性分析或系统地实现和评估各

本工作的所