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

加权法

邦妮向东移动了七个街区，她的新住所对杰克没有影响。事实上，无论她向东移动多远，杰克现在的住处都是最理想的位置。

如果你在网格纸上画了三个以上的点，你就能体会到这种加权方法的有效性。你会发现这种方法可以快速确定点x的位置，点x到所有点的距离是最小的，但是，这些点的数量是未知的。当点数为偶数时，不能满足要求。为什么？答案是相关性加权只有在点数相等的情况下才有可能。每当这种情况发生时，计算就会停止。

请讨论以下相关问题:

1.你能找到一个适合偶数点数的方法吗？

2.在什么情况下，一个或几个点的运动不影响点X的确定？

3.如果考虑到街道的宽度，加权方法会受到影响吗？

4.如果你包括X点并且不限制街道的宽度，它会影响你吗？

5.如果笔直的街道在飞机上形成一个网格并给出方向，结果会是什么？

6.如果街道是曲折的，结果会怎样？

尽管加权法适用于任何类型的网格，但它不适用于不确定的平面，因为距离不再局限于某一条路线。一般的问题是一个平面上有几个点，点x被确定为最小化到所有点的直线距离。例如，假设有三个城市，甲，乙和丙，机场的位置在哪里，使机场离这三个城市最近？这显然不同于乘坐公共汽车的要求，换句话说，确定理想的机场位置不同于确定公共汽车站的位置。

几何学不容易证明。答案是从机场到三个城市的三条路线之间的三个夹角都是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？Kruskar建立了以下最小网络。

测量每两点之间的距离，然后将这些线段的长度逐一相加，假设最短的线段为1，第二最短的线段为2，依此类推。如果有两个长度相等的线段，它们仅被添加到第一个线段。对于线段2、3、4、5，在由线段1分隔的两点之间画一条直线...等等。不再添加直线以形成封闭系统，即连接所有点的最小树排列。

这种树木排列的性质非常有趣。例如，在某一点相交的直线不超过五条。

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

大多数人认为最短的连接线应该是一个正方形的两条对角线之和(见图5-13)，但这是错误的。图5-13显示了右边的答案。正方形的两条对角线的长度是2√2=2.82，而图5-13中右边的计算长度是1+√3=2.73，比两条对角线的和短。

如果允许添加新的顶点，我们所知的“斯坦纳”问题就是寻找最短距离来连接平面上的n个点的一般问题。虽然这个问题的解决方案是针对特定的问题，但我们不知道一个有效的算法来确定施泰纳点(新的顶点)由“最小施泰纳树方法”连接几个点在一个平面上。这个问题在工程中被广泛应用，并且是使用计算机找到铁路网、航线、电话线和其他形式的观光和通信线路的最佳方法。