【正文】 四周的邊， 即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)）； 2) 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍； 3) 公園內(nèi)新修的道路只能 通過 8 個(gè)路口 與四周 相連 ； 4) 公園內(nèi) 總的道路長(zhǎng)度和最小 。 . 問題提出 從實(shí)際情況及上述要求出發(fā)，依據(jù)相關(guān)條件和數(shù)據(jù) 解決 ： 問題一 ：假定公園內(nèi)確 定要使用 4個(gè)道路交叉點(diǎn)為： A(50,75)， B(40,40)，C(120,40)， D(115,70）。問如何設(shè)計(jì)道路可使公園內(nèi)道路的總路程最短。建立模型并給出算法。畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。 問題二 ：現(xiàn) 公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點(diǎn)的坐標(biāo)，畫出道路設(shè)計(jì)，計(jì)算新修路的總 2/33 路程。 問題三 ：若 公園內(nèi)有一條矩形的湖，新修的道路不能通過，但可以到達(dá)題中湖四周的邊 。重復(fù)完成問題二 的任務(wù)。 其中矩形湖的相關(guān)坐標(biāo)： R1(140,70) , R2(140,45) , R3=(165,45) , R4=(165,70). 2. 問題分析 從人性化角度考慮，公園道路應(yīng)滿足 讓任意兩個(gè)入口相連 ，以保證游人不管怎樣都可以走出公園 。另外， 由于公園內(nèi)部設(shè)有觀賞景點(diǎn)或是休息座椅，所建設(shè)道路要經(jīng)過這些地點(diǎn)。而這些地點(diǎn)又分為修公園前就有的和公園建好后才修建的，還可分為道路可以通過的和不可以通過的（如湖、花壇等），這些情況都對(duì)應(yīng)于不同的道路設(shè)計(jì)方案。 對(duì)于校方而言，所建道路在滿足上述設(shè)計(jì)需要的基礎(chǔ)上，道路長(zhǎng)度和越短則消耗的資金越少。 故道路長(zhǎng)度和為主要考察的對(duì)象。 . 問題一 的 分析 問題一規(guī) 定了一些必須經(jīng)過的點(diǎn) 。 這來源于實(shí)際中所修道路要通向那些在公園建設(shè)之前就已存在 的 觀賞景點(diǎn) 的 情況。用數(shù)學(xué)模型分析解決這一問題對(duì)此類情況有重要意義。 問題一屬于有限制條件的最小樹生成問題。解決 最小樹 問題，一般采用kruskal 算法和 prim 算法。根據(jù)所學(xué)知識(shí)、題中數(shù)據(jù)特點(diǎn)和結(jié)果要求，我們選擇使用 kruskal 算法解決最小樹問題。為 驗(yàn)算是否滿足題中所給兩點(diǎn)間 倍直線距離的要求，我們采用 Dijkstra 算法 解決最短路徑問題 。 . 問題二的分析 同問題一相比，問題二沒有規(guī)定公園內(nèi)必須通過的點(diǎn)。 這來源于實(shí)際中公園內(nèi)的景點(diǎn)及設(shè)施都是在設(shè)計(jì)公園道路后才建的情況。用數(shù)學(xué)模型分析解決這一問題對(duì)此類情況有重要意義。 問題二屬于斯坦納最小生成樹問題?？紤]到任意兩點(diǎn)之間可以直接相連，我 3/33 們采用求解歐式距離的斯坦納點(diǎn)最小樹的逐步調(diào)優(yōu)法。 . 問題三的分析 問題三在問題二的基礎(chǔ)上增加了限制條件，考慮到實(shí)際中公園等休閑場(chǎng)所在道路規(guī)劃前即有人工湖等情況，問題三即 是 從這一情形中抽象出來的。 因 此對(duì)于問題三的研究很有現(xiàn)實(shí)意義。 問題三屬于約束條件下的斯坦納最小樹問題。 顯然，在問題二的基礎(chǔ)上，道路是不能通過人工湖的，因此，問題二可看作問題三的簡(jiǎn)化。 考慮 到 重建模型的復(fù)雜性和時(shí)間的緊迫性， 我們利用了問題二所建模型， 針對(duì)問題二得到的結(jié)果，在此基礎(chǔ)上進(jìn)行 了 相關(guān)優(yōu)化，直到 獲得 最優(yōu)解。 3. 模型 假設(shè) 1) 假設(shè)所有道路均為直線； 2) 假設(shè) 任意兩點(diǎn)間均可 修建 道路 ，即公園內(nèi)土質(zhì)及其它條件對(duì)修路不產(chǎn)生影響（第三問的湖泊除外）； 3) 假設(shè)所有道路均為無向的， 不存在單行道， 即道路 ? ? ? ?,i j j iP P P P和 道 路為同一 條路； 4) 對(duì)于問題一，假設(shè)除了 題中 所給 道路交叉 點(diǎn)外，不 再 另 外添加點(diǎn)。 5) 對(duì)于問題三，假設(shè)矩形湖的四周也可以 利用， 即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)。 4. 符號(hào)說明及名詞解釋 . 基本符號(hào) 符號(hào) 意義 iP 第 i 個(gè)入口 ijPP? 從第 i 個(gè)入口到第 j 個(gè)入口的行走路線 4/33 5. 模型建立 與求解、檢驗(yàn) . 問題一 . 問題 解析 該問題給出了 四個(gè) 道路交叉點(diǎn) ： A、 B、 C、 D，在 ○ 1 所設(shè)計(jì) 道路 要 讓任意兩個(gè)入口相連 （可以利用公園的矩形邊）， ○ 2 道路只能與公園的 8 個(gè)入口相連而不能與四周其他點(diǎn)相連， ○ 3 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍 ， ○ 4 兩點(diǎn)間所建道路為直線的前提下，我們所關(guān)心的問題是，如何設(shè)計(jì)出公園內(nèi)道路設(shè)計(jì)的最優(yōu)方案，使得道路長(zhǎng)度和最短。 我們將問題一的求解分為兩個(gè)步驟： 一、 使用 kruskal 算法解決最小樹問題 ；二、 采用 Dijkstra 算法 驗(yàn)算步驟一生成的樹是否滿足題中所給的兩點(diǎn)間 倍直線的距離要求 并進(jìn)行人工 微調(diào) 修正 。 . 步驟 一： 通過分析道路長(zhǎng)度和最短的要求， 我們發(fā)現(xiàn)這個(gè)問題和最小生成樹問題聯(lián)系最為緊密，于是考慮用 貪心法求解最小生成樹 的 kruskal 算法 的一些研究成果以及相關(guān)的圖論知識(shí)來建立該問題的數(shù)學(xué)模型。 我們先引入 最小生成樹的簡(jiǎn)單定義： 給定一 個(gè) 無向 連 通帶權(quán)圖 ? ?,GVE 中的每一條邊 ? ?,VW 權(quán)值 為 ? ?,CVW 。如果 G 的子圖 G 39。是一個(gè)包含 G 中所有定點(diǎn)的子圖，那么 G 39。稱為 G 的 生成樹 ，如果G 39。的邊的權(quán)值最小 ， 那么 G 39。稱為 G 的 最小生成樹 。 對(duì)于 kruskal 算法，其中心思想是每次添加權(quán)盡可能小的邊，使新的圖無圈，直到生成最優(yōu)樹為止，其步驟如下： 1) 把 N 內(nèi)的所有邊按照權(quán)的非減次序排列； 2) 按 1)排列的次序檢 查 N 中的每一條邊，如果這條邊與已得到的邊不產(chǎn)生圈，則取這一條邊為解的一部分； 3) 若已取得 n1 條邊，算法終止。此時(shí)以 V 為頂點(diǎn)集，以取到的 n1條邊為邊集的圖即為最優(yōu)樹。 5/33 對(duì)于問題一，題中僅給定幾個(gè)固定點(diǎn)的坐標(biāo)，并不知道相應(yīng)的邊。為簡(jiǎn)單起見，我們先假設(shè)任意兩點(diǎn)之間都是可以相連的，通過相關(guān)程序，即可算出任意兩點(diǎn)間的距離，并作為距離矩陣輸出。 其中，將任意兩點(diǎn)間的距離即作為該邊的權(quán)。 此時(shí)，可將距離 矩陣作為 kruskal 算 法 的加權(quán)矩陣，進(jìn)行輸入，即可得到由 kruskal 算法處理的最小樹。附注：利用該算法時(shí)，不考慮由外矩形邊框所引入的圈。 . 步驟二： 通過分析題中要求， 任意的兩個(gè)入口之間的最短路徑 不大于兩點(diǎn) 間 連線的 倍，我們采用 Dijkstra 算法 對(duì)于步驟一生成的樹進(jìn)行驗(yàn)算 。 我們先引入 Dijkstra 算法的簡(jiǎn)單定義： Dijkstra 算法 是解決關(guān)于帶權(quán)圖 (權(quán)為非負(fù)數(shù) )的單源最短路徑問題的一種貪心算法，它要一個(gè)一個(gè)地按路徑長(zhǎng)度遞增序找出從某個(gè)源點(diǎn)出發(fā)到所有其他頂點(diǎn)的最短路徑 。 Dijkstra 算法是按長(zhǎng)度遞增的次序生成從源點(diǎn) s 到其他定點(diǎn)的最短路徑，則當(dāng)前正在生成的最短路徑上除終點(diǎn)以外，其余的頂點(diǎn)的最短路徑均已生成（將源點(diǎn)的最短路徑看作是已生成的源點(diǎn)到其自身的長(zhǎng)度為 0 的路徑）。 可利用 Dijkstra 算法對(duì)步驟一所生成的道路中任意兩入口間的 最短 距離進(jìn)行求解得 到 一 個(gè) 矩陣，再與這兩入口間距離 的矩陣的 倍 進(jìn)行作差，找出負(fù)數(shù)（即不符合要求）對(duì)應(yīng)的道路，進(jìn)行人工合理化調(diào)整修改 后即可得到最優(yōu)結(jié)果 。 6/33 對(duì) 問題一的 求解過程 用流程圖表示 如下 ： 形成 距離矩陣 利用程序求任意兩點(diǎn) 間的距離 由 kruskal 算法程序 最小樹 最短路徑矩陣 Dijkstra 算法 倍距離矩陣 差距 作為輸入 輸出 作差 ? 倍 最優(yōu)解 調(diào)整 7/33 . 模型建立 與求解、檢驗(yàn) . 步驟一： 將數(shù)據(jù)輸入由 kruskal 算法對(duì)應(yīng)的程序（見附錄）， 僅僅考慮 生成最小樹 ，得到如下結(jié)果： kruskal 算出來的結(jié)果 ： 邊端點(diǎn) 距離 是否在最小支撐樹 (1,2) 30 √ (1,3) 140 (1,4) +002 (1,5) +002 (1,6) +002 (1,7) +002 (1,8) +001 √ (1,9) +001 (1,10) +001 (1,11) +002 (1,12) +002 (2,3) 110 (2,4) +002 (2,5) +002 (2,6) +002 (2,7) +002 (2,8) +001 (2,9) 75 (2,10) +001 √ (2,11) +001 (2,12) +001 (3,4) +001 √ (3,5) +002 (3,6) +002 (3,7) +002 (3,8) +002 (3,9) +002 (3,10) +002 (3,11) +001 √ (3,12) +001 (4,5) +001 (4,6) +002 (4,7) +002 (4,8) +002 (4,9) +002 8/33 (4,10) +002 (4,11) +001 (4,12) +001 (5,6) 85 (5,7) 110 (5,8) +002 (5,9) +001 (5,10) 100 (5,11) 60 (5,12) +001 √ (6,7) 25 √ (6,8) +001 (6,9) +001 √ (6,10) +001 (6,11) +002 (6,12) +001 (7,8) +001 (7,9) +001 (7,10) +001 (7,11) +002 (7,12) +002 (8,9) +001 (8,10) +001 (8,11) +002 (8,12) +002 (9,10) +001 √ (9,11) +001 (9,12) +001 √ (10,11) 80 (10,12) +001 (11,12) +001 √ （其中，“ √”表示兩端點(diǎn)是連通的，“ ”表示兩端點(diǎn)不連通） 由 上述數(shù)據(jù)， 可得初步 公園道路圖： 9/33 . 步驟二： 步驟一生成的只是 最小樹 ，而不一定滿足題中的要求 —— 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍。 下面先 對(duì)步驟一所生成的 各 道路中任意兩入口間 最短 的 折線距離 利用Dijkstra 算法進(jìn)行 求解，儲(chǔ)存到矩陣中，設(shè)這個(gè)矩陣用 D 表示 ， D = 設(shè)儲(chǔ)存這兩入口間 直線 距離的矩陣用 distance 表示 ， distance = 將 D 矩陣和 倍的 distance 矩陣 進(jìn)行作差， 得到矩陣 judge ， 將矩陣 D 和 倍的 矩陣 distance 作差得到矩陣 judge ， judge = 找出 judge 中的 負(fù)數(shù)（即不符合要求）對(duì)應(yīng)的道路， 即 15PP? 和 25PP? 兩kruskal 算法得出的最小樹 對(duì)應(yīng)的 路徑圖 （初步結(jié)果） 10/33 條折線道路大于兩入口直線距離的 倍，需要進(jìn)行 人工合理化調(diào)整修改。 經(jīng)過合理地 分析與嘗試， 我們將 修改后的 公園內(nèi)道路 確定 為： 下面對(duì)修改后的道路進(jìn)行合理化 的 驗(yàn)證。 修改后再 利用 Dijkstra 算法新生成的公園道路中任意兩入口間的最短距離進(jìn)行求解，得到新的矩陣，記為 39。D ， 39。D = 任意兩入口的直線距離所儲(chǔ)存的矩陣 distance 不變，仍為 distance = 同理，再 將 39。D 矩陣和 倍的 distance 矩陣進(jìn)行作差，得到矩陣 39。judge ， 修正后的公園道路設(shè)計(jì)圖（優(yōu)化結(jié)果） 11/33 39。judge = 由 39。judge 中再無負(fù)數(shù)元素，可驗(yàn)證得到修改后的道路滿足 題中各 條件， 即為最優(yōu)解。 . 問題二 . 問題 解析 同