全国站
奥数网

全国站
奥数网

《啊哈!灵机一动》-一个可爱的懒汉

数学E网 2007-11-09 14:49:55

  加权法

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

  如果你在格纸上画出多于三点的情况,你就能够欣赏出这种加权法的效能了。你会发现这种方法可以很快地确定点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点距离为最短的一般问题。这个问题的解决虽然是针对具体的问题,但我们不知道在平面上连接几点的“最小斯坦尔树法”确定斯坦尔点(新顶点)的有效算法。这个问题在工程中有广泛的应用,是用电子计算机寻求铁路网、飞机航线、电话线和其他形式的游览和通讯线路的最佳手段。

相关推荐

点击查看更多
首页 导航