辦事處的設(shè)置與連接

繆子陽+李婷玉+祝夢琳

摘要：文章將設(shè)置辦事處個數(shù)問題轉(zhuǎn)化為辦事處覆蓋范圍問題，通過枚舉法找出10種方案，使得辦事處數(shù)量n最少為7。然后運用prim算法在最少辦事處數(shù)量為7的條件下對各個方案算出最小生成樹從而得出連線總長最小為15。

Abstract： The article will set the number of office problems into the office coverage problem， through the enumeration method to find 10 kinds of programs， making the number of office n at least 7. Then use the prim algorithm to calculate the minimum spanning tree for each program in the minimum number of office for 7 to achieve the minimum length of the connection is 15.

關(guān)鍵詞：枚舉法；prim算法；最小生成樹

Key words： enumeration method；prim algorithm；minimum spanning tree

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1006-4311（2017）17-0228-02

1 問題重述

某城市為東西長5公里，南北長4公里的矩形，每隔0.5公里有一條南北（或東西）方向的道路，參見圖1。

（1）某公司要在該市設(shè)置n個辦事處，要求該市內(nèi)每一點到它最近的辦事處的距離d不超過d0=1.5公里。問這些辦事處應(yīng)如何設(shè)置可使n最??？n最小為多少？（“距離d”如下定義：市內(nèi)一居民只能沿水平或垂直線路到某一街道，然后再沿街道到達離他最近的辦事處，他所走的最短路程即為“距離d”）

（2）若要將這n個辦事處用專用網(wǎng)絡(luò)線連接起來，這些網(wǎng)絡(luò)線只能沿街道布置，應(yīng)如何布線可使總長L最小？L的最小值為多少？

2 問題分析

2.1 對問題（1）的分析

第一小問要求設(shè)置n個辦事處使得市內(nèi)每一點到它最近的辦事處的距離d不超過d0=1.5公里。

①此問題不適用于目標(biāo)函數(shù)模型，盡管可以在這張圖上建立坐標(biāo)系，將目標(biāo)函數(shù)確定為最小個數(shù)n，但約束條件無法確定市內(nèi)某一點到某個辦事處是否到的是最近的辦事處，因此無法具體化約束條件，所以本題放棄了建立目標(biāo)函數(shù)模型。

②此問題也不適用范圍圓的交叉點來確定最小個數(shù)n，一來距離的定義是沿水平或者垂直路線到某一街道，以半徑為1.5公里來劃圓會將一些不滿足d0=1.5公里的點劃進去，二來有99個點，劃99個圈無法識別。

③由劃范圍圓想到密鋪方法，一個辦事處可以覆蓋一定范圍的點，然后通過枚舉法列出方案，可行且較簡單。

2.2 對問題（2）的分析

①專用網(wǎng)絡(luò)線連接的理解：不是兩兩互聯(lián)，一條線串在一起即可。

②采用prim算法，可以求得最小生成樹，從而可以算出L的最短長度。

3 基本模型假設(shè)

①題中的基本參數(shù)設(shè)定正確。

②若市內(nèi)某一點距離兩個辦事處距離相等，且最短，則選擇任一個。

③街道暢通，不考慮交通堵塞對選擇最短距離的影響。

4 基本符號說明

n：辦事處的個數(shù)；

L：專用網(wǎng)絡(luò)線的長度；

V：辦事處；

注：局部符號會在引用處說明。

5 模型建立與求解

5.1 對問題（1）的求解

要求設(shè)立辦事處，使得市內(nèi)每一點到它最近的辦事處的距離d不超過d0=1.5公里。將問題轉(zhuǎn)化為辦事處的覆蓋范圍。

首先保證四個頂點要在辦事處的覆蓋范圍之內(nèi)。以左上方的頂點為例，一開始有10個點可以選擇設(shè)置辦事處。其次采取四個頂點對稱的方式，依次取遍10個頂點作為第一個辦事處。得到幾組解。然后采取四個頂點不對稱的方式，依次取遍10個頂點作為第一個辦事處。得到幾組解。本文中做了10組解，沒有全部解完。小黑點表示辦事處的位置，小灰點表示可供選擇的辦事處的位置，小方塊表示正好距離辦事處1.5公里的點。

5.2 對問題（2）的求解

以圖2的方案為例。使用prim算法求解專用網(wǎng)絡(luò)線的最小總長。

首先繪制加權(quán)連通圖：將各個辦事處連接起來，為了方便作圖，將沿水平或者垂直路線到某一辦事處的距離簡化為一條線。

其次使用prim算法計算結(jié)果。為了更方便地說明相關(guān)計算細(xì)節(jié)，我們重述一下prim算法的原理。

基本思想：prim算法的基本思想是：設(shè)G=（V，E）是一個無向連通網(wǎng)，令T=（U，TE）是G的最小生成樹。T的初始狀態(tài)為U={v0}（v0∈V）TE={}，然后重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價最小的邊（u，v）并入集合TE，同時v并入U，直至U=V為止[2]。

算法關(guān)鍵：prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來擴充生成樹T。設(shè)當(dāng)前T中有k個點（即T的頂點集U中有k個頂點）則所有滿足u∈U，v∈V-U的邊最多有k×（n-k）條，從如此大的邊集中選取最短邊是不太經(jīng)濟的[3]。利用MST性質(zhì)，可以用下述方法構(gòu)造候選最小邊集：對應(yīng)V-U中的每個頂點，保留從該頂點到U中的各頂點的最短邊，取候選邊最短邊集為V-U中的n-k個頂點所關(guān)聯(lián)的n-k條最短邊的集合。為表示候選最短邊集，需設(shè)置兩個一維數(shù)組lowcost[n]和adjvex[n]，其中l(wèi)owcost用來保存集合V-U中的各頂點與集合U中頂點的最短邊的權(quán)值，lowcost[v]=0表示頂點v已經(jīng)加入最小生成樹中；adjvex用來保存依附于該邊在集合U中的頂點[1]。

然后得出結(jié)果：

5.3 解題補充

根據(jù)所畫的最小生成樹圖，將每條線的長度相加，就可以得到L的最短長度。

需要注意的是，上述求解只是第一問中的一種方案的求解，其他九種方案求解過程類似，唯一的不同就是根據(jù)加權(quán)連通圖所寫的權(quán)矩陣不同，在此不再贅述。

6 模型的評價

6.1 模型的優(yōu)點

①簡單清晰，無論是加權(quán)連通圖還是最小生成樹，都給人直觀的印象。

②對于建模的要求不高，可以直接用算法求解出答案。

③本模型選擇的算法可以快速得出不同方案下的最小程度，從而做出比較。

6.2 模型的缺點

①本文第一問采用的枚舉法具有一定的局限性，對于較小的區(qū)域可以適用，對于大范圍的設(shè)置辦事處就難以適用了。

②本文認(rèn)為是只需要將這幾個辦事處連接起來，而不用兩兩相連，沒有考慮兩兩互連的情況。

參考文獻：

[1]江波，張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計算機工程與設(shè)計，2009（13）：3244-3247.

[2]江波，張黎. 基于Prim算法的最小生成樹優(yōu)化研究[J].計算機工程與設(shè)計，2009（13）.

[3]陳新.基于最小生成樹的聚類分析方法研究[D].重慶大學(xué)，2013.