一个艺术画廊看守问题的启发式算法

摘要

艺术画廊问题来源于人们的现实生活，已经吸引了越来越多的学者对其进行研究。如今，它在现实生活的很多领域中都有着重要的应用。由于求任一简单多边形所需看守的最少数目”这一算法是NP-难的，所以人们尝试着给出求简单多边形所需看守数目相对比较优的算法。本文提出了大部分具有k个凹点的简单多边形所需看守数目的一个启发式算法，一般情况下，此看守数目要要优于k。因此，无论在理论上还是在实际应用中，对其研究都具有一定的意义。主要研究内容如下： (1)由艺术画廊定理可知，对于任意的多边形Pn，其最小看守数为|n/3|。在研究多边形所需监视器的数目中，多边形中的凹点起着非常重要的作用。由于对绝大多数的具有k个凹点的简单多边形来说，k台监视器并不是最优的。所以，通过分析简单多边形的剖分及其算法，从凹点的角度出发，提出简单多边形的M形剖分以及M形剖分的算法，并在此剖分及其算法的基础上给出了艺术画廊看守问题的启发式算法，得出大部分具有七个凹点的简单多边形需要的看守数目G，满足|k/2|≤G≤k的结论。 (2)在正交艺术画廊看守问题中，Kahn，klawe和Kleitman得出了正交艺术画廊的最小看守数g⊥(n)为[n/4].本文利用任意正交多边形可进行凸四角剖分的性质，得到了正交多边形的一个特殊的三角剖分，通过对这种三角形的邻接关系的分析，运用了一种四染色方案，给出了正交艺术画廊定理一种新的证明。

目录

文摘

英文文摘

声明

第1章绪论

1.1引言

1.2发展现状

1.2.1多边形的剖分

1.2.2艺术画廊问题

1.2.3其它艺术画廊问题

1.3本文的研究内容与安排

第2章预备知识

2.1基本概念

2.2艺术画廊问题相关概念与性质

2.3几种典型的艺术画廊看守问题的性质

第3章艺术画廊看守问题的启发式算法

3.1多边形的剖分

3.1.1多边形的三角剖分

3.1.2多边形的梯形剖分

3.1.3多边形的凸剖分

3.2艺术画廊看守问题的启发式算法

3.2.1多边形M形剖分及其算法

3.2.2看守数目的启发式算法

第4章正交艺术画廊看守问题

4.1引言

4.2正交艺术画廊看守定理

第5章结束语

5.1本文研究的主要工作

5.2待研究的问题

参考文献

致 谢