一个可爱的懒汉

一个可爱的懒汉

	a．杰克幻想成为世界上最可爱的人，他计划在华盛顿特区租一套公寓。
	b．杰克有三个女朋友都居住在市内，他想让自己的住所到三个女朋友的住所一样近。
	c．杰克在市区地图上标出了女朋友们住所的位置。杰克：现在我看清了，要我选择自己的住所并非易事。
	d．杰克选来选去，准备放弃他的计划。杰克：啊哈!我发现了一个简单方法，能够找到我要住的地方。
	e．杰克的好办法是，在他搬家之前，先取得女朋友们的同意。他找了一处，看起来很合理，只是在街区的东边。
	f．杰克：我住得离安妮塔和布妮近了，她们会投赞成票，肯迪也许会反对，因为离她远了。我得站在多数人一边。
	g．只要多数人同意，杰克就决定搬家，有人反对，他就再搬一次，直到没有人反对了，他才决定住下。
	h．很幸运，杰克能够在这个合适的地点租一套公寓了。可是一星期之后，布妮搬到七街区以外的地方去了。
	i．杰克：我的天呀!现在我又得重搬家了。但是，当杰克查看了地图以后，他惊奇地发现，他无须再搬一次家。你能够解释这是为什么吗?

加权法

布妮向东搬了七个街区，她的新住所对杰克没有影响。的确，不论她向东搬多远，杰克现在的住所都处在最理想的位置上。

如果你在格纸上画出多于三点的情况，你就能够欣赏出这种加权法的效能了。你会发现这种方法可以很快地确定点X的位置，点X到所有点的距离为最小，然而这些点的数量是未知数。当点的数量为偶数时，不能满足要求。为什么?答案是，如果点的数量为偶数的相关加权才有可能。这种情况无论何时发生，计算都会停止。

请你讨论下列有关问题：

1．你能找出一种适用于点数为偶数的方法吗?

2．一点或若干点的移动，在什么情况下不影响点X的确定?

3．如果考虑街的宽度，加权法会受影响吗?

4．如果包括点X，不限制街宽，会有影响吗?

5．如果在平面上由直的街道组成格子，并且给出方向，结果怎样?

6．如果街道是曲折的或弧线形的，结果怎样?

虽然加权法适用于任何种类的网格，但它不适用于未确定的平面，因为路程不再限于一定的途径。一般的问题是，在一平面上有几个点，确定点X，使之到所有点的直线距离为最小。例如，假设有三个城市，A、B和C，机场的位置在何处，才能使机场到三个城市的距离最近?这显然与乘汽车的要求不同，换句话说，确定理想的机场位置与确定汽车站位置不同。

用几何学的方法不容易得到证明。答案是，从机场到三个城市的三条航线之间的三个夹角均为120°。如果有四个城市，分别作为一个凸四边形的顶点，那么机场应位于两条对角线的交点处，这不难证明。当给出若干点时，确定点X的位置就比较困难了。

一种简单的仪器(权重仪)能够迅速地确定平面上点X相对任意三点的位置吗?假设一张桌子的表面为一平面，我们在桌面的三点上钻三个孔，将三根绳头系在一起，三根绳的另一头各自穿过一个孔，每根绳头上分别挂上等量重的砝码。绳子上等量重的砝码相当于居民们在三点的三个等量加权，点X的位置可由桌面上绳子的结点表示出来。这种证明方法，采用了数学结构问题与物理模型的同型性。

现在我们来解答我们的难题。假设用A、B、C三点代表原先三个女孩居住的位置，并且假定这三点分别代表学生宿舍楼，有20名学生住在A楼，30名学生住在B楼，40名学生住在C楼，所有的学生同在一所学校上学，这所学校应该建在什么位置，才能使90名学生步行上学的距离为最近?

如果学生们上学的路线是确定的，我们可以像前题一样采用加权法，允许每个学生加权。这样能够迅速地确定学校应处的位置。假如三座宿舍楼在一个平面上，学生们可以走直线去上学(就像乡村的孩子们可以穿过田野去上学那样)，我们能够利用权重仪得到答案吗?

是的，可以。我们以不等重的砝码代替等量重砝码，不等重的砝码质量分别与每座宿舍楼中学生的数量成正比，绳子的结点将表示出学校所在的位置。

如果一座宿舍楼中学生人数比其他两座的总和还多，权重仪是否还能工作?比如：A楼里有20名学生，B楼里有30名，C楼里有100名。回答是肯定的，权重仪仍然工作。相当于100名学生的那个砝码将拉动绳子，使绳子的结点位于C孔上。它证明学校的位置应在C点。

多于三点的情况，权重仪还正常工作吗?是的。它也同样适用于几个点不是凸多边形的顶点的一般情况。但是，如有摩擦力，多于三点，权重仪将不再有效地工作。

图解理论是一个新的数学分支，它与被线段连接顶点的理论有关。有的图解理论采用了选择最短路径的方法，便使问题得以解决。请看下面的一个著名例题。

在一个平面上有几个点，把它们用直线连接起来，并且使这些线段的总长度尽可能地短，我们在平面上不再增加新点，这样的一个网络被称为“最小排列树”。你能通过这种网络发明一种算法吗?

“克鲁斯卡尔规则”(以第一个发明者J·B·克鲁斯卡尔命名)建立了以下最小网络。

在每两点之间量出距离，然后将这些线段长度逐一相加，假定最短的线段为1，第二短的为2，以此类推。如果有两条线段等长，则只加在第一条线段上。在被线段1分开的两点间画一直线，对于线段2，3，4，5……以此类推。不再增加直线，形成一个封闭系统，即一个连接所有点的最小排列树。

这种排列树的性质很有趣。例如，在某点上相交的直线，在该点上不多于五条。

最小排列树法不要求连接n点的连线为最短，但限制增加新顶点。如果允许增加顶点，连线可能会更短。以一个单位边长的正方形为例，最小排列树包括正方形的任意三边(图5—13中)。假设我们被允许增加新顶点，请问连接四个顶点的连线能否小于3？

图5-13

多数人认为最短连线应为正方形的两条对角线之和(图5—13中)，但这不对。图5—13右给出了答案。正方形两条对角线长度为2√2=2.82，而图5—13右所计算的长度为1+√3=2.73，短于两条对角线之和。

如果允许增加新顶点，我们所知道的“斯坦尔”问题就是在平面上寻求连接n点距离为最短的一般问题。这个问题的解决虽然是针对具体的问题，但我们不知道在平面上连接几点的“最小斯坦尔树法”确定斯坦尔点(新顶点)的有效算法。这个问题在工程中有广泛的应用，是用电子计算机寻求铁路网、飞机航线、电话线和其他形式的游览和通讯线路的最佳手段。