The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm
The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm
复制标题
寻求美术馆问题的最佳解决方案：一种实用的迭代算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. C. Souza
中科院分区：
文献类型：
--
作者：
Davi C. Tozoni;P. J. Rezende;C. C. Souza
一般的美术馆问题（AGP）在于找到足够的警卫，以确保由多边形表示的美术馆的可见性覆盖的最小数量。AGP是一个众所周知的（mathbb{NP}）-困难的问题，因此，所有的算法提出到目前为止，以解决它是无法保证最优性，除非在特殊情况下。在本文中，我们提出了一种新的方法来解决画廊问题迭代生成的上限和下限，同时寻求达到一个精确的解决方案。尽管收敛仍然是一个重要的悬而未决的问题，我们的算法已经成功地测试了一个非常大的集合的实例，从公开的基准。对几类实例进行了测试，总共有一千多个无孔多边形，大小从20到1000个顶点。该算法表现出了卓越的性能，在标准台式计算机上，在几分钟内为每个实例获得可证明的最优解。据我们所知，尽管AGP已经研究了四十年的计算几何领域内，这是第一次提出一个精确的算法，并广泛测试了这个问题。未来的研究方向，以扩大目前的工作进行了讨论。
The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon. The AGP is a well known (mathbb{NP})-hard problem and, for this reason, all algorithms proposed so far to solve it are unable to guarantee optimality except in special cases. In this paper, we present a new method for solving the Art Gallery Problem by iteratively generating upper and lower bounds while seeking to reach an exact solution. Notwithstanding that convergence remains an important open question, our algorithm has been successfully tested on a very large collection of instances from publicly available benchmarks. Tests were carried out for several classes of instances totalizing more than a thousand hole-free polygons with sizes ranging from 20 to 1000 vertices. The proposed algorithm showed a remarkable performance, obtaining provably optimal solutions for every instance in a matter of minutes on a standard desktop computer. To our knowledge, despite the AGP having been studied for four decades within the field of computational geometry, this is the first time that an exact algorithm is proposed and extensively tested for this problem. Future research directions to expand the present work are also discussed.