辦事處的設置與連接

繆子陽+李婷玉+祝夢琳

摘要：文章將設置辦事處個數問題轉化為辦事處覆蓋范圍問題，通過枚舉法找出10種方案，使得辦事處數量n最少為7。然后運用prim算法在最少辦事處數量為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.

關鍵詞：枚舉法；prim算法；最小生成樹

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

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

1 問題重述

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

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

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

2 問題分析

2.1 對問題（1）的分析

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

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

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

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

2.2 對問題（2）的分析

①專用網絡線連接的理解：不是兩兩互聯，一條線串在一起即可。

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

3 基本模型假設

①題中的基本參數設定正確。

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

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

4 基本符號說明

n：辦事處的個數；

L：專用網絡線的長度；

V：辦事處；

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

5 模型建立與求解

5.1 對問題（1）的求解

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

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

5.2 對問題（2）的求解

以圖2的方案為例。使用prim算法求解專用網絡線的最小總長。

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

其次使用prim算法計算結果。為了更方便地說明相關計算細節，我們重述一下prim算法的原理。

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

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

然后得出結果：

5.3 解題補充

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

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

6 模型的評價

6.1 模型的優點

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

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

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

6.2 模型的缺點

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

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

參考文獻：

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

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

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