亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        辦事處的設置與連接

        2017-06-06 12:05:10繆子陽李婷玉祝夢琳
        價值工程 2017年17期
        關鍵詞:枚舉法

        繆子陽+李婷玉+祝夢琳

        摘要:文章將設置辦事處個數(shù)問題轉化為辦事處覆蓋范圍問題,通過枚舉法找出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.

        關鍵詞:枚舉法;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個辦事處用專用網(wǎng)絡線連接起來,這些網(wǎng)絡線只能沿街道布置,應如何布線可使總長L最?。縇的最小值為多少?

        2 問題分析

        2.1 對問題(1)的分析

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

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

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

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

        2.2 對問題(2)的分析

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

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

        3 基本模型假設

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

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

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

        4 基本符號說明

        n:辦事處的個數(shù);

        L:專用網(wǎng)絡線的長度;

        V:辦事處;

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

        5 模型建立與求解

        5.1 對問題(1)的求解

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

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

        5.2 對問題(2)的求解

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

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

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

        基本思想:prim算法的基本思想是:設G=(V,E)是一個無向連通網(wǎng),令T=(U,TE)是G的最小生成樹。T的初始狀態(tài)為U={v0}(v0∈V)TE={},然后重復執(zhí)行下述操作:在所有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)條,從如此大的邊集中選取最短邊是不太經(jīng)濟的[3]。利用MST性質,可以用下述方法構造候選最小邊集:對應V-U中的每個頂點,保留從該頂點到U中的各頂點的最短邊,取候選邊最短邊集為V-U中的n-k個頂點所關聯(lián)的n-k條最短邊的集合。為表示候選最短邊集,需設置兩個一維數(shù)組lowcost[n]和adjvex[n],其中l(wèi)owcost用來保存集合V-U中的各頂點與集合U中頂點的最短邊的權值,lowcost[v]=0表示頂點v已經(jīng)加入最小生成樹中;adjvex用來保存依附于該邊在集合U中的頂點[1]。

        然后得出結果:

        5.3 解題補充

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

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

        6 模型的評價

        6.1 模型的優(yōu)點

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

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

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

        6.2 模型的缺點

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

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

        參考文獻:

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

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

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

        猜你喜歡
        枚舉法
        最優(yōu)切割問題研究
        科技資訊(2022年6期)2022-05-13 08:51:06
        停車位排布方式優(yōu)化設計
        枚舉法的程序實現(xiàn)及優(yōu)化
        展開學習過程突出知識本質
        培養(yǎng)解決問題能力,提升學生核心素養(yǎng)
        應重視用枚舉法解題
        淺談枚舉法在中學數(shù)學解題中的應用
        井群泵站運行優(yōu)化研究
        淺談旋轉類問題的分類方法
        對改進隱枚舉法的思考
        私人毛片免费高清影视院| 亚洲国产日韩综合天堂| 91视色国内揄拍国内精品人妻| 欧美日韩亚洲中文字幕二区| 乱码一二三入区口| 天堂av无码大芭蕉伊人av孕妇黑人| 中文日本强暴人妻另类视频 | 大屁股人妻女教师撅着屁股| 精品一品国产午夜福利视频| 无码人妻少妇久久中文字幕| 亚洲精品98中文字幕| 国产精品女人呻吟在线观看| 污污污污污污WWW网站免费| 好看午夜一鲁一鲁一鲁| 中文字幕影片免费人妻少妇| 中文字幕乱码亚洲精品一区| 国产久视频国内精品999| 丝袜美腿亚洲综合玉足| 久久熟妇少妇亚洲精品| 国产无遮挡无码视频免费软件| 国产精品27页| 国产精品自拍视频在线| 无码国产精品久久一区免费| 免费av片在线观看网站| 亚洲区精品久久一区二区三区女同| 一区二区三区国产黄色| 午夜内射中出视频| 日韩精品欧美激情亚洲综合| 国产日产高清一区二区三区| 女人被男人爽到呻吟的视频| 学生妹亚洲一区二区| 亚洲天堂av社区久久| 白嫩人妻少妇偷人精品| 久久久无码中文字幕久...| 国产乱人视频在线观看播放器 | 精品国产迪丽热巴在线| 国产自产二区三区精品| 久久精品国产亚洲av四虎| 国产高潮精品久久AV无码| 免费人成视频x8x8| 乱码一二三入区口|