灌溉問題模型

1、1灌溉問題模型的建立與分析灌溉問題模型的建立與分析AbjectAbjectToreducethecostofagriculturalactivitiesbuildtheConservationmindedSociety.Inthisarticlewesetupamathematicalmodelaboutirrigationintheagriculturalactivitiesdiscusshowtochannelsothatallth

2、efieldcanbeirrigated.Meoverwecanconfirmtheschemesthatcostsmallestinvariousofschemes.IntheaspectofalgithmswemakeuseofMinimalspanningtreeheretoobtainthewaytoconnectallthefieldsinminimumwages.Theessaywhichbasedontwoalgithms

3、:PrimKruskal.Wefmthearticleinthreeparts:FirstlyabstractthefarmerfieldintoconnectedgraphThencreatetheweightmatrixLastlywetrytofindthewaytoconnectallthefieldsinminimumcostbyPrimKruskal.IndexTerms——MinimalspanningtreePrimKr

4、uskal摘要摘要為了減少農(nóng)民生產(chǎn)活動成本，創(chuàng)造節(jié)約型社會，我們對農(nóng)業(yè)生產(chǎn)中的灌溉問題建立了數(shù)學(xué)模型，來討論怎樣開渠能使所有農(nóng)田都能被灌溉，進(jìn)一步將確定各種連接方式中最小成本的連接方案。從算法上來說，這是一個最小生成樹問題，將一個連通圖形取最小連接方式連接成一體。對于這種問題，有兩種算法：kruskal算法和prim算法。本文所描述的模型正是分別基于這兩種算法所建立的，大致分為如下三個部分：首先，將灌溉問題的農(nóng)田抽象成連通圖的形式，并將

5、連通方式輸入。其次，將輸入的矩陣轉(zhuǎn)化為邊權(quán)矩陣。最后，用kruskal算法和prim算法找出最短路徑]1[并輸出連接方案。關(guān)鍵字關(guān)鍵字：最小生成樹kruskal算法prim算法一問題的概述一問題的概述中國是世界上最大的農(nóng)業(yè)國之一，耕地面積18.37億畝，占世界現(xiàn)有耕地3?用灌溉渠將兩農(nóng)田連接上就能使農(nóng)田被灌溉，灌溉渠不會損壞，堵塞。?連接一塊農(nóng)田的每條灌溉渠灌溉效果相同。?相鄰的農(nóng)田之間邊權(quán)矩陣對應(yīng)元素為1，不相鄰表示為0。2模型建立及

6、求解模型建立及求解2.12.1模型一：基于模型一：基于kruskalkruskal算法的灌溉問題模型。算法的灌溉問題模型。2.1.12.1.1模型思路模型思路首先將n個頂點(diǎn)看成n個孤立的連通分支（n個孤立點(diǎn)）并將所有的邊按權(quán)從小大排序。按照邊權(quán)值遞增順序，如果加入邊后存在圈則這條邊不加，直到形成連通圖。以下是具體實(shí)現(xiàn)說明：首先將上圖1.1的實(shí)物圖抽象為連通圖并標(biāo)號。接下來將用kruskal算法求解上面連通圖的最小生成樹，即能將上面12個

7、節(jié)點(diǎn)連接在一起的連接方案。本模型中應(yīng)用的kruskal算法其實(shí)是貪心算法的一種，其主要的想法是：首先將連通圖的連接方式與權(quán)重表示為一個邊權(quán)矩陣，這里的邊權(quán)矩陣為一個01權(quán)值矩陣，元素是從到開鑿灌溉渠的權(quán)值??jiaij（其中為0）；接下來在邊權(quán)矩陣中從左上開始找元素為1的坐標(biāo)，并將)(iia該邊的權(quán)值改為無窮大，即又生成了一個新的邊權(quán)矩陣，在這個新的邊權(quán)矩陣中再從左上開始尋找元素為1的邊，并重復(fù)上面的步驟。其中要說明的是不能循環(huán)連接，這