【文章內(nèi)容簡(jiǎn)介】 問題一相比，問題二沒有規(guī) 定公園內(nèi)必須通過的點(diǎn)，屬于斯坦納最小生成樹問題?？紤]到任意兩點(diǎn)之間可以直接相連，我們采用求解歐式距離的斯坦納點(diǎn)最小樹的逐步調(diào)優(yōu)法。 我們先引入斯坦納最小樹的定義： 定義 已知 歐式平面上任給 的 有限點(diǎn)集 ? ?12, , , nR v v v? ，欲求出一個(gè) 點(diǎn) 集? ?12, , , kS s s s? ， 使 點(diǎn)集 RS? 的連線 長度最短 所構(gòu)成 的圖，必然是邊數(shù)最少的連通圖，因此它為樹，稱為 斯坦納最小樹 ，記為 SRT 。 R 中的點(diǎn)為 SRT 上的固定點(diǎn)， S 中的點(diǎn)稱為 SRT 上的斯坦納點(diǎn) ，簡(jiǎn)稱為 斯坦納點(diǎn) 。 由于本問題可以自由 添 加道路交叉點(diǎn)，我們引入 SRT 的一些性質(zhì)： 性質(zhì) 1 SRT 上每個(gè)點(diǎn)之多關(guān)聯(lián)三條邊，而每個(gè)斯坦納點(diǎn)恰好關(guān) 聯(lián)三條邊。 性質(zhì) 2 SRT 上，關(guān)聯(lián)于同一點(diǎn)的任何兩邊的夾角不小于 120 ；關(guān)聯(lián)于同一斯坦納點(diǎn)的任何兩邊的夾角恰為 120 。 性質(zhì) 3 若 ? ?12, , , nR v v v? ，則 SRT 中斯坦納點(diǎn)的個(gè)數(shù)不大于 2n? 。 性質(zhì) 4 歐式斯坦納最小樹的每個(gè)斯坦納點(diǎn)都 必定包含在全部正則點(diǎn)的最小凸包內(nèi)。 添加斯坦納點(diǎn)的斯坦納最小樹，往往會(huì)比 不添加斯坦納點(diǎn)的最優(yōu)樹的長度更短些。即若以 ? ?mLR和 ? ?sLR分別表示點(diǎn)集 R 的最優(yōu)樹和斯坦納最小樹的長 12/33 度，必有 ? ? ? ?smL R L R? 。例如，給出三點(diǎn) A 、 B 、 C ， 組成邊長為 1 的正三角形。對(duì)點(diǎn)集 ? ?,R A B C? 的斯坦納最小樹的長度為 3 ，而最優(yōu)樹長度為 2。因此，? ?? ? 3 0 .8 6 62smLRLR ??。也就是說，添加斯坦納點(diǎn) 后可以節(jié)省約 13%的長度。 引入以下定理： 定理 ? ?? ? 32smLRLR? 下面我們 介紹 最小逐步調(diào)優(yōu)法的原理： 設(shè)正則點(diǎn)集 Z 中有 n 個(gè)點(diǎn) ? ?2n? ，坐標(biāo)為 ? ?, , 1, 2, ,iix y i n? 。并記? ?m in m in | 1 , 2 ,iX x i n??， ? ?m a x m a x | 1 , 2 ,iX x i n??， ? ?m in m in | 1, 2 ,iY y i n??， ? ?m a x m a x | 1 , 2 ,iY y i n??。 根據(jù)性質(zhì) 4，輔助點(diǎn)的投放范圍可以控制在矩形? ? ? ?m i n , m a x m i n , m a xR X X Y Y??之內(nèi)。 本文逐步調(diào)優(yōu)法的思路是這樣的 ： 首先求出正則點(diǎn)集 Z 的最小生成樹 0T ,相應(yīng)的樹長為 0||T 。 設(shè) k 表示輔助點(diǎn)數(shù)，讓 k 分別取值 1 到 2n? ，對(duì)于 每 一個(gè) k 值，在范圍 R 內(nèi)隨機(jī)投放 k 個(gè) 輔助點(diǎn)，產(chǎn)生輔 助 點(diǎn)集 F ， 然后用 Prim 算法計(jì)算出由 nk? 個(gè)點(diǎn)組成的集 ZU? 的最小生成樹。這樣就獲得 2n? 棵樹，根據(jù)它們的樹 長，計(jì)算出一個(gè)概率分布 ， 樹長越短者，相應(yīng)的概率越大。然后按此分布隨機(jī)抽樣，樹長越短，被抽 中 的概率就越大。對(duì)被抽中的樹，對(duì)其每個(gè)輔助點(diǎn)，在一個(gè)小領(lǐng)域范圍內(nèi)隨機(jī)作擾動(dòng)，產(chǎn)生一個(gè)新的近似解，這樣重復(fù)多次擇優(yōu)記錄最好者， 若比原來的要好，則替換它，否則不變。重 算概率分 布，再抽 樣調(diào)優(yōu)，這樣重復(fù)到預(yù)定循環(huán)次數(shù)為止。這里不直接選樹長最短者來調(diào)優(yōu)，是為了避免算法陷入 局部極值，不是 最短的樹也有機(jī)會(huì)被抽中。上述過程完成后，還需做最后的調(diào)整 ： 刪掉 1 度和 2 度的輔助點(diǎn) （ 若有的話 ） ，利用 求解斯坦納點(diǎn)坐標(biāo)的計(jì)算 式，并把 3 度輔助點(diǎn)調(diào)整到最優(yōu) 位置 ，使其變?yōu)樗固辜{點(diǎn)。 13/33 完成以上過程后，獲得一個(gè)近似最優(yōu)解 *T ，若樹長 * 0| | | |TT? ， 則輸出 *T ，否則輸出 0T 。 下面我們闡述一下 逐步調(diào)優(yōu)法的實(shí)施 步驟 ： Prim 算法求出正則點(diǎn)集 Z 的最小生成樹 0T 。 k 取值 1 到 2n? ，在矩形 R 內(nèi)隨機(jī)投放 k 個(gè) 輔助點(diǎn)， 產(chǎn)生輔 助 點(diǎn)集F ， 然后用 Prim 算法計(jì)算出由 nk? 個(gè)點(diǎn)組成的集 ZU? 的最小生成樹 ，樹長記為 ||kT 。 1||k kS T?，21kk njjSPS???? ， ? ?1, 2, , 2kn??，這樣得到了一個(gè)離散的概率分布，并記1kkiiqP???， ? ?1, 2, , 2kn??。 [0， 1]均勻分布的隨機(jī)數(shù) r ，若滿足 1kkq r q? ?? ，則對(duì) kT 的輔助點(diǎn)位置作擾動(dòng)，不是隨機(jī)重投，而是每個(gè)輔助點(diǎn)在一個(gè)半徑為 h 的鄰域內(nèi)隨機(jī)走一步（當(dāng)然不能走出 R 的范圍）。這一步重復(fù)大約 20 次，擇優(yōu)記錄最好者，若比原來的要好，則替換它，否則 kT 不變。 3 和 4，知道大道預(yù)設(shè)的最大迭代次數(shù)位置，此時(shí)的最好解記為*T 。 *T 中輔助點(diǎn)的度。 *T 的輔助點(diǎn)。若有 1 度輔助點(diǎn)，則顯然應(yīng)把該點(diǎn)連同關(guān)聯(lián)邊刪去；若有 2 度輔助點(diǎn)，則應(yīng)把該點(diǎn)連同關(guān)聯(lián)邊刪去，但要添加一條連接兩個(gè)鄰點(diǎn)的邊。若有 3 度輔助點(diǎn)，一般它不是斯坦納點(diǎn)，需要矯正。按照斯坦納點(diǎn)的坐標(biāo)計(jì)算公式，把該 3 度輔助點(diǎn)移動(dòng)到該坐標(biāo)位置上，調(diào)整后得到新的 *T 。 6 和 7，大約 10 次， 若 最后 樹長 * 0| | | |TT? ， 則輸出 *T ，否則輸出0T 。如果有 1 度輔助點(diǎn)被刪除，則會(huì)影響相鄰點(diǎn)的度；如果有兩個(gè) 3 度輔助點(diǎn)相鄰，則校正了 1 個(gè)輔助點(diǎn)成斯坦納點(diǎn)后，另一個(gè)輔助點(diǎn)可能又變得不在最佳位置。 因此，第 7 步的重復(fù)是必要的，反復(fù)多次調(diào)優(yōu)，才能逐步逼近最優(yōu)位置。 14/33 . 模型建立 與求解、檢驗(yàn) 根據(jù)上述的逐步調(diào)優(yōu)法，由本題 8n? ，隨機(jī)分布 k ? ?1,2, ,6k ? 個(gè)斯坦納點(diǎn)，通過離散概率隨機(jī)抽取相應(yīng)的斯坦納點(diǎn)進(jìn)行擾動(dòng)，直到得到最優(yōu)解 ，并解出新修路的總長度為 米 。其對(duì)應(yīng)的 公園道路設(shè)計(jì)圖 如下： 利用問題一中相同 的 Dijkstra 算法 對(duì)結(jié)果進(jìn)行驗(yàn)算，看所求得道路是否滿足 倍這一條件。所得到的 judge 矩陣為： 由于矩陣中無負(fù)元素，故 檢驗(yàn)得 所求道路滿足題目要求。 . 問題三 . 問題 解析 問題三在問題 二的基礎(chǔ)上增加了約束條件 —— 不能經(jīng)過道路的區(qū)域，這也給 15/33 題目增加了很大的難度。為此，我們?cè)诜治隽藬?shù)據(jù)特點(diǎn)及湖位置的基礎(chǔ)上，根據(jù)問題一中的計(jì)算任意兩入口間折線距離的方法，我們 確定了 在不添加道路交叉點(diǎn)的情況下 就可滿足折線距離小于兩入口直線距離 倍的條件的 幾條 邊 。 經(jīng) 過 分析 ， 只有入口 25PP? 和 入口 26PP? 在不添加道路交叉點(diǎn)的情況下不 能 滿足題中要求。故只需要添加 一個(gè) 道路交叉點(diǎn)使 2 5 6,P P P 這三點(diǎn)滿足兩入口直線距離的 倍這一條件 ，并且使新增的道路總長度最小；經(jīng)分析，該點(diǎn)即為斯坦納點(diǎn) 。在 問題二 的基礎(chǔ)上，利用 歐式距離斯坦納最小樹的逐步調(diào)優(yōu)法進(jìn)行相關(guān) 擾動(dòng) ， 最終 確定斯坦納點(diǎn) 并進(jìn)行驗(yàn)算 。 . 模型建立 與求解、檢驗(yàn) 根據(jù)問題二的理論依據(jù)，因?yàn)?有 2 5 6,P P P 三個(gè)點(diǎn)，故只需要添加一個(gè)斯坦納點(diǎn)即可。利用迭代 思想 ，在該點(diǎn)的鄰域內(nèi)進(jìn)行擾動(dòng) ，添加道路交叉點(diǎn)使 2 5 6,P P P 這三點(diǎn)滿足兩入口直線距離的 倍 ，并且使道路 總長度盡可能小 。經(jīng)多次驗(yàn)算，我們確定了一個(gè)斯坦納點(diǎn) ? ?55,80S 。計(jì)算可得道路長度和為 米， 其相應(yīng)的公園道路設(shè)計(jì)圖為： 同問題一、問題二一樣的驗(yàn)算原理，可算得此設(shè)計(jì)滿足題中各要求。 6. 結(jié)果表示 . 問題一 16/33 道路設(shè)計(jì)圖： 問題一方案 新修路的總路程： 米 . 問題二 道路設(shè)計(jì)圖： 問題二方案 新修路的總長度： 米 . 問題三 道路設(shè)計(jì)圖： 17/33 問題三方案 新修路的總長度： 米 7. 模型的評(píng)價(jià) 、優(yōu)化及 推廣 . 模型的評(píng)價(jià) 1) 問題一的求解思路是先用 kruskal 算法得到是不帶環(huán)的最小樹， 把 邊加入最小樹再利用 Dijkstra 算法 依據(jù)題中條件進(jìn)行驗(yàn)算，這樣得到的結(jié)果可能不是最優(yōu)解； 2) 問題一中，模型一 利用 kruskal 算法 和 Dijkstra 算法 分兩個(gè)步驟得到精確最優(yōu)解的前提是假設(shè)所修道路均為直線， 公園內(nèi)部有且僅有給出的四個(gè)道路交叉點(diǎn) 。而事實(shí)上 是可以再添加道路交叉點(diǎn)的 ， 此類 問題 便同問題二一樣 屬于 NP 難問題，也就是說 ,，當(dāng)問題含有其他約束條件時(shí) ,，要想求得真正的最優(yōu)解是不現(xiàn)實(shí)的，為此， 必需采取靈活多樣的方式和方法 , 求近似得最優(yōu)解； 3) 問題二在問題一的基礎(chǔ)上 可隨意添加道路交叉點(diǎn)，添加點(diǎn)的個(gè)數(shù)和位置均不確定， 成為 NP 難問題，無法找到精確最優(yōu)解。本問題中的算法都只是近似算法 , 所得最優(yōu)設(shè)計(jì)方案 也只是近似最優(yōu)解； 4) 問題二、三所用算法利用人工擾動(dòng)精度不高且效率較低； 5) 問題 三求解是在 可利用湖的四邊而不算入所修總路程的假設(shè)下，具 有一定的理想局限性。 18/33 . 模型的優(yōu)化 我們發(fā)現(xiàn)，在問題一的步驟二中用 Dijkstra 算法 對(duì)最短路徑進(jìn)行驗(yàn)算 的 時(shí)間代價(jià)較高， 若用傳統(tǒng)的方法通過掃描整個(gè)網(wǎng)絡(luò)圖的頂點(diǎn)來搜索最小值，總時(shí)間代價(jià)為 ? ?2On ，如果將模型應(yīng)用到頂點(diǎn)數(shù)多的環(huán)境中，那么效率將非常低。 經(jīng)查閱相關(guān)文獻(xiàn) [2]后，我們認(rèn)為利用二叉堆來進(jìn)行優(yōu)化，便可快速訪問到具有最小值的點(diǎn)，時(shí)間代價(jià)僅為 ? ?logOn。具體思路如下： 設(shè) S 為最短距離已確定的頂點(diǎn)集（看作紅點(diǎn)集）， VS? 是最短距離尚未確定的頂點(diǎn)集（看作藍(lán)點(diǎn)集）。初始化時(shí)，只有源點(diǎn) s 的最短距離是已知的( ( ) 0)Ds? ? ? ，其余各點(diǎn)的估計(jì)最短距離 D 值均設(shè)為無窮大。用數(shù)組 ??Dv記錄從源點(diǎn) s 到達(dá) v 外中間不經(jīng)過任何藍(lán)點(diǎn)（若有中間點(diǎn)，則必為紅點(diǎn)）的“最短”路徑長度（簡(jiǎn)稱估計(jì)距離）。經(jīng)過一次循環(huán)后，紅點(diǎn)集 ??Ss??? ，其余各點(diǎn)的估計(jì)最短距離 D 值更新為該點(diǎn)到源點(diǎn)而中間不經(jīng)過任何點(diǎn)的邊的權(quán)值。若路徑不存在則仍為無窮大； 在藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn) k 來擴(kuò)充紅點(diǎn)集是Dijkstra 算法的關(guān)鍵。若能快速訪問到具有最小 D 值的藍(lán)點(diǎn)，則可大大減少算法的時(shí)間復(fù)雜度。若用傳統(tǒng)的方法通過掃描整個(gè)網(wǎng)絡(luò)圖的頂點(diǎn)（即窮舉法）來搜索最小值，總時(shí)間代價(jià)為 ? ?2On 。在 Dijkstra 算法中，由于累計(jì)權(quán)值決定的最短路徑具有優(yōu)先程度差異特征，所以若將未被處理的頂點(diǎn)的最短路徑 D 值構(gòu)造優(yōu)先級(jí)隊(duì)列，則可大大提高算法的效率。用堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列是很自然的。 堆是一種抽 象數(shù)據(jù)結(jié)構(gòu)，由一系列元素集合構(gòu)成，每個(gè)元素有個(gè)實(shí)數(shù)類型的關(guān)鍵字。 而二叉堆是一種最普 及的數(shù)據(jù)結(jié)構(gòu)，它可被視為一棵完全二叉樹。堆有最大堆和最小堆兩種。 最小堆結(jié)構(gòu)必須滿足以下性質(zhì)：除了根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的值不小于其父節(jié)點(diǎn)的值．這樣，堆中的最小元素就存在根節(jié)點(diǎn)中 。 因?yàn)榫哂?n 個(gè)元素的二叉堆是一棵完全二叉樹，其高度為 logn 。 所以對(duì)于二叉堆的操作例如 insert (插入 )和removemin (從堆中刪除并返回最有最小關(guān)鍵字的元素 )，其作用時(shí)間至多與樹的高度成正比，為 ? ?logOn。 所以，將未被處理的頂點(diǎn)以 D 值大小為順序保存在一個(gè)最小堆中，可以使用 ? ?logOn次搜索找出下一個(gè)最近頂點(diǎn)。 每次改變 ??Dx值時(shí)， 都可以通過先刪除再重新插入的方法改變頂點(diǎn)菇在堆中的位 置。 為了實(shí)現(xiàn)優(yōu) 19/33 先更新需要將每個(gè) 頂點(diǎn)連同它的數(shù)組下標(biāo)存儲(chǔ)在堆中，其時(shí)間復(fù)雜度在算法實(shí)現(xiàn)部分分析。 對(duì)于問題二采用的求斯坦納最小樹的逐步調(diào)優(yōu)法，由于離散概率的不確定性，所以采用 迭代的 次數(shù)較多，過程較繁 ，相應(yīng)地，效率也就降低了。針對(duì)這一問題， 可以采用 多路徑并行搜索蟻群算法的并行搜索機(jī)制進(jìn)行相關(guān)優(yōu)化。其具體原理 如下： 多路徑并行搜索蟻群算法將每只螞蟻的求解過程分解為 m條路徑并行的搜索，其中 m為終端節(jié)點(diǎn)的個(gè)數(shù)。每條路徑對(duì)應(yīng)從一個(gè)終端節(jié)點(diǎn)出發(fā)，直至滿足某個(gè)條件終止。利 用該方法路徑搜索的終止條件是剛訪問過的節(jié)點(diǎn)已經(jīng)出現(xiàn)在其他路徑上，即當(dāng)前路徑與其他路徑發(fā)生相交，則當(dāng)前路徑設(shè)置為不活躍狀態(tài)，本路徑終止搜索節(jié)點(diǎn)。若當(dāng)前螞蟻的所有的路徑都終止時(shí)，螞蟻在該輪 迭代中搜索節(jié)點(diǎn)的過程也終止。螞蟻在這步操作完成之后即得到一個(gè)節(jié)點(diǎn)的集合，該集合由這 m條路徑上的所有節(jié)點(diǎn)構(gòu)成，包括了所有終端節(jié)點(diǎn)和當(dāng)前螞蟻認(rèn)為必要的一些中間節(jié)點(diǎn)，這個(gè)過程極為螞蟻選擇節(jié)點(diǎn)的過程。 . 模型的推廣 由于本題采用圖論模型的方法求解 ， 分析了在不同的限制條件下道路長度和最短的數(shù)學(xué)模型及求解， 并提出能夠找到該近似算法或原則，可 以較好的推廣到解決 交通網(wǎng)絡(luò)、輸油管道、 災(zāi)情巡視線路、投遞、旅行商等實(shí)際問題 。 8. 參考文獻(xiàn) [1] 林健良，施美珍，朱曉清，何明芳。求解歐式距離斯坦納最小樹的逐步調(diào)優(yōu)法。廣州：華南理工大學(xué)理學(xué)院， 20xx。 [2] 林小玲，何建農(nóng)，周勇。帶限制條件的最短路徑算法與實(shí)現(xiàn)。福州 ：福州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 20xx。 [3]