加權(quán)法

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

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

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

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

　　2．一點(diǎn)或若干點(diǎn)的移動(dòng)，在什么情況下不影響點(diǎn)X的確定？

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

　　4．如果包括點(diǎn)X，不限制街寬，會(huì)有影響嗎？

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

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

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

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

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

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

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

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

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

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

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

　　在一個(gè)平面上有幾個(gè)點(diǎn)，把它們用直線連接起來，并且使這些線段的總長度盡可能地短，我們?cè)谄矫嫔喜辉僭黾有曼c(diǎn)，這樣的一個(gè)網(wǎng)絡(luò)被稱為“最小排列樹”。你能通過這種網(wǎng)絡(luò)發(fā)明一種算法嗎？

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

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

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

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

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

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