加权法

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

　　如果你在格纸上画出多于三点的情况，你就能够欣赏出这种加权法的效能了。你会发现这种方法可以很快地确定点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右给出了答案。正方形两条对角线长度为2√2=2.82，而图5―13右所计算的长度为1+√3=2.73，短于两条对角线之和。

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