加權(quán)法

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

　　如果你在格紙上畫出多于三點的情況，你就能夠欣賞出這種加權(quán)法的效能了。你會發(fā)現(xiàn)這種方法可以很快地確定點X的位置，點X到所有點的距離為最小，然而這些點的數(shù)量是未知數(shù)。當(dāng)點的數(shù)量為偶數(shù)時，不能滿足要求。為什么？答案是，如果點的數(shù)量為偶數(shù)的相關(guān)加權(quán)才有可能。這種情況無論何時發(fā)生，計算都會停止。

　　請你討論下列有關(guān)問題：

　　1．你能找出一種適用于點數(shù)為偶數(shù)的方法嗎？

　　2．一點或若干點的移動，在什么情況下不影響點X的確定？

　　3．如果考慮街的寬度，加權(quán)法會受影響嗎？

　　4．如果包括點X，不限制街寬，會有影響嗎？

　　5．如果在平面上由直的街道組成格子，并且給出方向，結(jié)果怎樣？

　　6．如果街道是曲折的或弧線形的，結(jié)果怎樣？

　　雖然加權(quán)法適用于任何種類的網(wǎng)格，但它不適用于未確定的平面，因為路程不再限于一定的途徑。一般的問題是，在一平面上有幾個點，確定點X，使之到所有點的直線距離為最小。例如，假設(shè)有三個城市，A、B和C，機(jī)場的位置在何處，才能使機(jī)場到三個城市的距離最近？這顯然與乘汽車的要求不同，換句話說，確定理想的機(jī)場位置與確定汽車站位置不同。

　　用幾何學(xué)的方法不容易得到證明。答案是，從機(jī)場到三個城市的三條航線之間的三個夾角均為120°。如果有四個城市，分別作為一個凸四邊形的頂點，那么機(jī)場應(yīng)位于兩條對角線的交點處，這不難證明。當(dāng)給出若干點時，確定點X的位置就比較困難了。

　　一種簡單的儀器(權(quán)重儀)能夠迅速地確定平面上點X相對任意三點的位置嗎？假設(shè)一張桌子的表面為一平面，我們在桌面的三點上鉆三個孔，將三根繩頭系在一起，三根繩的另一頭各自穿過一個孔，每根繩頭上分別掛上等量重的砝碼。繩子上等量重的砝碼相當(dāng)于居民們在三點的三個等量加權(quán)，點X的位置可由桌面上繩子的結(jié)點表示出來。這種證明方法，采用了數(shù)學(xué)結(jié)構(gòu)問題與物理模型的同型性。

　　現(xiàn)在我們來解答我們的難題。假設(shè)用A、B、C三點代表原先三個女孩居住的位置，并且假定這三點分別代表學(xué)生宿舍樓，有20名學(xué)生住在A樓，30名學(xué)生住在B樓，40名學(xué)生住在C樓，所有的學(xué)生同在一所學(xué)校上學(xué)，這所學(xué)校應(yīng)該建在什么位置，才能使90名學(xué)生步行上學(xué)的距離為最近？

　　如果學(xué)生們上學(xué)的路線是確定的，我們可以像前題一樣采用加權(quán)法，允許每個學(xué)生加權(quán)。這樣能夠迅速地確定學(xué)校應(yīng)處的位置。假如三座宿舍樓在一個平面上，學(xué)生們可以走直線去上學(xué)(就像鄉(xiāng)村的孩子們可以穿過田野去上學(xué)那樣)，我們能夠利用權(quán)重儀得到答案嗎？

　　是的，可以。我們以不等重的砝碼代替等量重砝碼，不等重的砝碼質(zhì)量分別與每座宿舍樓中學(xué)生的數(shù)量成正比，繩子的結(jié)點將表示出學(xué)校所在的位置。

　　如果一座宿舍樓中學(xué)生人數(shù)比其他兩座的總和還多，權(quán)重儀是否還能工作？比如：A樓里有20名學(xué)生，B樓里有30名，C樓里有100名。回答是肯定的，權(quán)重儀仍然工作。相當(dāng)于100名學(xué)生的那個砝碼將拉動繩子，使繩子的結(jié)點位于C孔上。它證明學(xué)校的位置應(yīng)在C點。

　　多于三點的情況，權(quán)重儀還正常工作嗎？是的。它也同樣適用于幾個點不是凸多邊形的頂點的一般情況。但是，如有摩擦力，多于三點，權(quán)重儀將不再有效地工作。

　　圖解理論是一個新的數(shù)學(xué)分支，它與被線段連接頂點的理論有關(guān)。有的圖解理論采用了選擇最短路徑的方法，便使問題得以解決。請看下面的一個著名例題。

　　在一個平面上有幾個點，把它們用直線連接起來，并且使這些線段的總長度盡可能地短，我們在平面上不再增加新點，這樣的一個網(wǎng)絡(luò)被稱為“最小排列樹”。你能通過這種網(wǎng)絡(luò)發(fā)明一種算法嗎？

　　“克魯斯卡爾規(guī)則”(以第一個發(fā)明者J?B?克魯斯卡爾命名)建立了以下最小網(wǎng)絡(luò)。

　　在每兩點之間量出距離，然后將這些線段長度逐一相加，假定最短的線段為1，第二短的為2，以此類推。如果有兩條線段等長，則只加在第一條線段上。在被線段1分開的兩點間畫一直線，對于線段2，3，4，5……以此類推。不再增加直線，形成一個封閉系統(tǒng)，即一個連接所有點的最小排列樹。

　　這種排列樹的性質(zhì)很有趣。例如，在某點上相交的直線，在該點上不多于五條。

　　最小排列樹法不要求連接n點的連線為最短，但限制增加新頂點。如果允許增加頂點，連線可能會更短。以一個單位邊長的正方形為例，最小排列樹包括正方形的任意三邊(圖5―13中)。假設(shè)我們被允許增加新頂點，請問連接四個頂點的連線能否小于3？

　　多數(shù)人認(rèn)為最短連線應(yīng)為正方形的兩條對角線之和(圖5―13中)，但這不對。圖5―13右給出了答案。正方形兩條對角線長度為2√2=2.82，而圖5―13右所計算的長度為1+√3=2.73，短于兩條對角線之和。

　　如果允許增加新頂點，我們所知道的“斯坦?fàn)枴眴栴}就是在平面上尋求連接n點距離為最短的一般問題。這個問題的解決雖然是針對具體的問題，但我們不知道在平面上連接幾點的“最小斯坦?fàn)枠浞ā贝_定斯坦?fàn)桙c(新頂點)的有效算法。這個問題在工程中有廣泛的應(yīng)用，是用電子計算機(jī)尋求鐵路網(wǎng)、飛機(jī)航線、電話線和其他形式的游覽和通訊線路的最佳手段。