2 一家画廊需要多少保安

想象一下你是一家大型画廊安保部门的经理。画廊的墙上有许多珍贵的绘画作品。它们都挂得很低，参观者可以用眼睛水平地直视，因此它们也容易被盗窃或被破坏。画廊有不同形状和大小的房间，你如何确保每一幅画在任何时间都在保安的监视下呢？如果你有无限的资金，那么办法很简单：只要每幅画前站一名保安。但画廊很少有钱，并且捐赠者并不倾向于把他们的捐赠花在保安和他们的椅子上。因此，现实中，你会遇到一个问题，一个数学问题：要使画廊所有的墙面都能被一眼看到，你最少需要雇用多少名保安并如何安排他们的位置？

我们需要知道监视所有墙壁的最少保安人数（或监控摄像头数）。假设墙壁是平直的，站在两面墙相交的角落，保安能看到两面墙上发生的每件事。再假设保安的视线不会被阻挡，并可360度旋转。很明显，一个三角形的画廊只需要一名站在其中任何位置的保安。实际上，如果画廊地板的形状像任何有着平直墙壁、所有墙角都朝外的多边形（一个“凸”多边形，如三角形），那么一名保安就足够了。

但当有些墙角不朝外时，事情变得更有趣了。图1是一个有八面墙的画廊，如果保安位于角 O 的位置，画廊仍只需一名保安监控。然而如果保安被移到左边顶角或底角，则不然。

图1

所以，这家画廊的运行成本还是相当小的。这里另有一个怪异的十二面墙壁的画廊，需要4名保安来监视所有的墙壁，不是很有效率。

图2

要一般地解决这样的问题，就看我们如何能把画廊分成不重叠的三角形 ^[1] 。这总是可以做到的。因为三角形是这些只需要一名保安的凸多边形之一（三条边的凸多边形），我们知道如果画廊可以完全由 T 个不重叠的三角形覆盖，那么就可以由 T 名保安监控。当然，它可能还可以由更少的保安看守。例如，我们总可以连接对角线把正方形分成两个三角形，但我们不需要两名保安盯着所有的墙——一个人就行。在一般情况下，要监控有 W 面墙的画廊，必需的保安人数最多是 W /3的整数部分 ^[2] 。对于那个有12条边的锯齿状画廊，最多是12/3=4人，而对于一个八条边的画廊这个人数则是2。

不幸的是，确定是否需要用到这个最多人数并不是那么容易的，并且是所谓的“困难的”计算机问题，每次你添加一面墙，计算时间就会增加一倍 ^[3] 。在实际中，如果 W 是一个非常大的数字，这将是一个无法排除的烦恼。

你现今访问的大多数画廊不会有像这些例子中那样古怪的锯齿状墙壁，墙壁都是像这样成直角的：

图3

如果一个如上图所示的直角形画廊有多个墙角，那么它可以划分成一些矩形，每个矩形都需要不超过一名保安来监控墙壁 ^[4] 。现在，位于墙角的，必要且充分地保护画廊的保安人数是（1/4×墙角数）的整数部分：对于上面显示的有14个墙角的画廊这个数字是3。显然，从薪酬（或摄像头费用）方面看，这样设计的画廊更经济，尤其当画廊变得更大时。如果画廊有150面墙，那么非直角设计的墙可能需要50名保安，而直角设计的墙则最多需要37名保安。

另一种传统的直角形画廊将画廊分成房间。下图是一个有10间房间的画廊的例子。

图4

在这些情况下，你总是可以把画廊分成一个不重叠矩形的集合。这是权宜之计，因为如果你将一名保安安排在连接两间房间的门口，则两间房间能够同时被监控到。然而没有保安能够同时监控三间或更多的房间。所以现在充分地，有时是必要地，保持全面监控一个画廊的保安人数则是大于或等于 ×房间数的下一个整数。在上面这个例子中，这个数就是5。这是一个使用资源更经济的办法。数学家们研究了各种各样更现实的情况，有些情况中保安可以走动，有些情况中他们的视线受到局限，或者那里用了镜子来帮助他们看到被拐角遮挡的角落。数学家们对文物窃贼如何选择最佳路线穿过画廊以躲避摄像头或巡逻的保安也有研究。下次你如果打算偷窃《蒙娜丽莎》，你会有一个好的开始。

[1] 如果多边形有 S 个顶点，就会有 S -2个三角形。

[2] 我们用［W/3］来表示这个数字。最早是赫瓦塔尔（Václav Chvátal）在《组合论杂志》（ Journal of Combina tional Theory ）B系列，18，39（1975）上证明的。这个问题是克莱（Victor Klee）于1973年提出的。

[3] 这是一个NP完全问题。见奥罗克（J.O’Rourke），《艺术馆定理与算法》（ Art Gallery Theorem and Algo rithms ），牛津大学出版社，牛津（1987）。

[4] 卡恩（J.Kahn），克拉韦（M.Klawe）和克莱特曼（D.Kleitman），《工业与应用数学学会代数和离散方法SIAM学刊》（ SIAM Journal on Algebraic and Dissrete Methods ）4，194（1983）。