加權法

　　布妮向東搬了七個街區，她的新住所對杰克沒有影響。的確，不論她向東搬多遠，杰克現在的住所都處在最理想的位置上。

　　如果你在格紙上畫出多于三點的情況，你就能夠欣賞出這種加權法的效能了。你會發現這種方法可以很快地確定點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點距離為最短的一般問題。這個問題的解決雖然是針對具體的問題，但我們不知道在平面上連接幾點的“最小斯坦爾樹法”確定斯坦爾點(新頂點)的有效算法。這個問題在工程中有廣泛的應用，是用電子計算機尋求鐵路網、飛機航線、電話線和其他形式的游覽和通訊線路的最佳手段。