算法設(shè)計與分析——輸油管道問題試驗(yàn)報告

1、題目：輸油管道問題學(xué)號00913130弓楠_,z一,學(xué)生姓名小專業(yè)（班級）09計本1班00913133朱玉婷設(shè)計題目輸油管道問題設(shè)計技術(shù)參數(shù)系統(tǒng)平臺：windows7開發(fā)工具：MicrosoftVisualC+6.0設(shè)計要求1 .掌握問題分析的方法與步驟，選擇合適的方法解決問題。2 .選擇合適的算法編寫程序。工作計劃1:熟悉題目并理解，及找尋相關(guān)資料。2:根據(jù)題目設(shè)計普分析算法。3:使用VisualC+實(shí)現(xiàn)。4:完成設(shè)計報告參考資料呂國英.算法設(shè)計與分析.北京：清華大學(xué)出版社,2009摘要本實(shí)驗(yàn)，我們通過綜合應(yīng)用算法解決了實(shí)際生活中的輸油管道問題，通過比較各種算法的時間復(fù)雜度以及解決效率，采用

2、了算法中以分治法為基礎(chǔ)的隨機(jī)劃分來解決問題，利用隨機(jī)選擇方法找到各個油井的中位數(shù)，通過討論論證了中位數(shù)即最優(yōu)管道位置。信息奧賽中一個問題有多個算法解決，通過比較不同算法解決問題的效率，選擇最高效的一個。在輸油管道問題這個實(shí)驗(yàn)中得到運(yùn)用。關(guān)鍵詞：算法設(shè)計，分治法，隨機(jī)劃分，隨機(jī)選擇，中位數(shù)1需求分析1.1實(shí)驗(yàn)內(nèi)容目錄錯誤！未定義書簽。錯誤！未定義書簽錯誤！未定義書簽。1.2 系統(tǒng)的基本邏輯模型1.3 確定目標(biāo)系統(tǒng)的功能.52總體設(shè)計錯誤！未定義書簽2.1問題分析錯誤！未定義書簽1 解題思路6.1 解題方法.71.2. 算法思想.71.2. 算法分析.73詳細(xì)設(shè)計.9.具體描述9.程序分析11程序

3、代碼.11程序結(jié)果.144總結(jié)16設(shè)計體會1.6反思總結(jié)16參考文獻(xiàn).錯誤！未定義書簽。.需求分析實(shí)驗(yàn)內(nèi)容某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置，即它們的x坐標(biāo)(東西向)和y坐標(biāo)(南北向)，應(yīng)如何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道長度總和最小的位置？證明可在線性時間內(nèi)確定主管道的最優(yōu)位置。給定n口油井的位置，編程計算各油井到主管道之間的輸油管道最小長度總和。系統(tǒng)的基本邏輯模型設(shè)給定的n口油井的位置坐標(biāo)為：(x0,y0),(x1,y1),(x2,y2)

4、,(xn-1,yn-1)。由于平面上的距離滿足三角不等式，故每個油井到主管道的最短距離就是該油井到主管道的垂直距離。由此可知，所述問題可表述為求平面上的一條直線到若干點(diǎn)的最短路徑，通過總體設(shè)計中的解題思路我們論證得出只要該條直線處在所有點(diǎn)的中間位置就能保證最后的距離最短。根據(jù)題意，給定了n個油井的位置，因此首先從文件讀取每個油井的坐標(biāo)，再在這個基礎(chǔ)上對各個油井的y坐標(biāo)進(jìn)行排序，通過隨機(jī)選擇算法找到它們的中位數(shù)，即可得到求出最短距離確定目標(biāo)系統(tǒng)的功能通過本實(shí)驗(yàn)的設(shè)計，我們可以找到一個到各個油井之間的長度總和最小的輸油管道，確定出輸油管道的位置，并且計算出長度之和。在實(shí)際生活中，本實(shí)驗(yàn)的程序設(shè)計，

5、可以節(jié)省工程的耗資，并且也可以省去人工計算的繁瑣。.總體設(shè)計系統(tǒng)設(shè)計一般分為總體設(shè)計和詳細(xì)設(shè)計。經(jīng)過需求分析階段的工作，已經(jīng)清楚系統(tǒng)必須完成的工作，下面的工作就應(yīng)該是決定“如何做”的問題，總體設(shè)計的基本目的的就是“概要地說系統(tǒng)應(yīng)該如何實(shí)現(xiàn)？”。問題分析實(shí)際上就是對輸入的數(shù)據(jù)，找出與這些數(shù)據(jù)的差絕對值的和最小的數(shù).基本的思路就是找出中位數(shù).解題思路如何確定主管道的最優(yōu)位置？由于主管道是由東向西，顯然，主管道的鋪設(shè)位置只和各油井位置的y坐標(biāo)有關(guān)，設(shè)各個油井的y坐標(biāo)為：yi,主管道的y坐標(biāo)為：dy,各油井到主管道之間的輸油管道長度總和應(yīng)是：sum,要使這個值最小，主管道的位置y坐標(biāo)應(yīng)是各個油井y坐標(biāo)

6、的中位數(shù)（一組數(shù)據(jù)按從小到大的順序依次排列，處在中間位置的一個數(shù)（或最中間兩個數(shù)據(jù)的平均數(shù)）。證明（反證法）：油井?dāng)?shù)目為奇數(shù)：假設(shè)主管道的最優(yōu)位置y坐標(biāo)值為y_val,不是各個油井位置y坐標(biāo)的中位數(shù)y_median,我們可以假設(shè)y_val>y_median（不失一般性），y坐標(biāo)小于y_val的油井?dāng)?shù)目為m,y坐標(biāo)大于y_val的油井?dāng)?shù)目為n,顯然有m>n。當(dāng)我們將主管道位置下移距離x時（假設(shè)此時仍滿足y_val>=y_median）,各油井到主管道之間的輸油管道長度總和應(yīng)增加nx-mx,顯然nx-mx<0（m>n）,即存在一個比y_val更優(yōu)的位置使得各油井到主管

7、道之間的輸油管道長度總和更小，這與假設(shè)矛盾。油井?dāng)?shù)目為偶數(shù)：證明情況同奇數(shù)情況。不同的是主管道的最優(yōu)位置y坐標(biāo)可以是各油井y坐標(biāo)的兩個中位數(shù)之間的任一整數(shù)。解題方法通過我們對數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計的學(xué)習(xí)，為了求得中位數(shù)，我們先通過劃分算法對所有油井y坐標(biāo)進(jìn)行排序，然后通過隨機(jī)選擇方法RandomizedSelec竹導(dǎo)至U中位數(shù)。算法思想分治算法的基本思想是將一個規(guī)模個為N的問題分解為K規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。算法分析分治算法是很多高效算法的基礎(chǔ)，如排序算法(快速排序、歸并排序)、傅立葉變換(快速傅立葉變換)?？焖倥判蚴怯蓶|尼霍爾所

8、發(fā)展的一種排序算法。在平均狀況下，排序n個項(xiàng)目要O(nlgn)次比較。在最壞狀況下則需要O(n2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他O(nlgn)算法更快，因?yàn)樗膬?nèi)部循環(huán)(innerloop)可以在大部分的架構(gòu)上很有效率地被實(shí)作出來，且在大部分真實(shí)世界的資料，可以決定設(shè)計的選擇，減少所需時間的二次方項(xiàng)之可能性。在此題中，我們考慮到時間復(fù)雜度，對于中位數(shù)這類選擇問題的解決，不一定要先排序然后遍歷(事實(shí)上這是比較慢的做法，排序的時間復(fù)雜度決定了它不可能比O(nlgn)快。通常選擇問題只是要求知道第i大/小的元素，所以我們可以將本實(shí)驗(yàn)的問題當(dāng)成排序算法的簡化。我們就以上述的

9、快速排序?yàn)槔覀円詣澐值膮^(qū)間判斷，選擇問題我們只追究可能出現(xiàn)問題解的一個區(qū)間，而快速排序要處理兩個區(qū)間。由此，我們可以清晰的明白利用隨機(jī)劃分解決此問題可以縮短時間復(fù)雜度。利用數(shù)據(jù)結(jié)構(gòu)教材中的隨機(jī)選擇算法RandomizedSelect計算出中位數(shù)median(y),然后計算n口油井到主管道的最小長度總和，則所需時間主要是隨機(jī)選擇算法RandomizedSelect用的時間，在平均情況下需要qn)計算時間。3,詳細(xì)設(shè)計具體描述詳細(xì)設(shè)計階段的根本任務(wù)是確定應(yīng)該怎樣具體實(shí)現(xiàn)所要求的輸油管道定位問題，也就是經(jīng)過這個階段的設(shè)計工作，應(yīng)該得出對輸油管道問題的精確描述，從而在輸油管道定位的實(shí)現(xiàn)階段可以把這

10、個描述直接翻譯成用某種程序設(shè)計語言書寫的程序。把經(jīng)過總體設(shè)計得到的各個模塊詳細(xì)的加以描述。3-1.總體結(jié)構(gòu)圖float*a,floatp,r3-2.patition算法設(shè)計圖如果基數(shù)在中間數(shù)的左邊則重復(fù)進(jìn)行以上操作3-3.RandomizedSelectM法設(shè)計圖程序分析程序代碼主函數(shù)的作用：首先初始化油井的坐標(biāo)數(shù)組，由用戶從鍵盤輸入各個油井的總數(shù)，然后再輸入各個油井的坐標(biāo)，并且會顯示出來。intmain()(intsize=0;char*inFileName="D:in.txt"char*outFileName="D:out.txt"ifstreami

11、nput(inFileName,ios:in);/從文件讀取數(shù)據(jù)input>>size;int*a=newintsize;intreadcount=1,i=0;while(readcount<=(size*2)(inttemp=0;input>>temp;if(readcount%2=0)ai+=temp;readcount+;input.close();/獲取數(shù)據(jù)中位數(shù)，即為通道丫坐標(biāo)intlength=RandomizedSelect(a,0,size-1,(size+1)/2);printf("最佳位置y=%dn",length);pri

12、ntf("最短距離已保存在文件中！");/將總的管道長度寫入out.txt文件中write(outFileName,lengthOfPipeline(a,size,length);system("pause");return0;Patition(劃分)函數(shù)的作用：將一串?dāng)?shù)據(jù)由大到小進(jìn)行排序，最后返回劃分時所用基數(shù)的位置floatPartition(float*a,floatp,floatr)floati=p,j=r+1;floatx=ap;/將<x的元素交換到右邊區(qū)域/將>*的元素交換到左邊區(qū)域while(true)(while(a+i<

13、;x&&i<r);while(a-j>x);if(i>=j)break;swap(ai,aj);ap=aj;aj=x;returnj;/獲取劃分后基數(shù)的位置RandomizedPartition（隨機(jī)劃分優(yōu)化算法）函數(shù)的作用：在所有坐標(biāo)中隨機(jī)選擇一個，并以此作為基數(shù)進(jìn)行劃分，最后返回該基數(shù)的位置floatRandomizedPartition(float*a,floatp,floatr)(floati=Random(p,r);/產(chǎn)生隨機(jī)數(shù)swap(ai,ap);/交換基數(shù)和第一個數(shù)returnPartition(a,p,r);/返回劃分后基數(shù)的位置Random

14、izedSelect(隨機(jī)選擇)函數(shù)的作用：找到排序后數(shù)據(jù)的中位數(shù)floatRandomizedSelect(float*a,floatp,floatr,floatk)(if(p>=r)returnap;floati=RandomizedPartition(a,p,r);/將隨機(jī)基數(shù)的為位置賦給ifloatj=i-p+1;/獲取基數(shù)距第一個數(shù)的長度if(k=j)returnai;/如果基數(shù)在中間則返回基數(shù)的值if(k<j)returnRandomizedSelect(a,p,i-1,k);/如果基數(shù)在中間數(shù)的右邊則重復(fù)進(jìn)行以上操作ElsereturnRandomizedSelect

15、(a,i+1,r,k-j);/如果基數(shù)在中間數(shù)的左邊則重復(fù)進(jìn)行以上操作/此函數(shù)就是當(dāng)基數(shù)處在油井的中間時返回該值3.2.2程序結(jié)果txt-記事本-alxi文件(E)編輯格式)查看9幫助4.總結(jié)設(shè)計體會通過該課程設(shè)計，全面系統(tǒng)的理解了算法設(shè)計與分析的一般原理和基本實(shí)現(xiàn)方法。把死板的課本知識變得生動有趣，激發(fā)了學(xué)習(xí)的積極性。把學(xué)過的算法知識強(qiáng)化，能夠把課堂上學(xué)的知識通過自己設(shè)計的程序表示出來，加深了對理論知識的理解。以前對與算法的認(rèn)識是模糊的，現(xiàn)在通過自己動手做實(shí)驗(yàn)，從實(shí)踐上應(yīng)用了算法，了解了算法在一個程序中是如何起作用的，并且學(xué)會比較各種算法的優(yōu)劣。通過對本實(shí)驗(yàn)的分析，對于輸油管道實(shí)質(zhì)上就是求解

16、中位數(shù)的問題，經(jīng)過討論和總結(jié)我們得到三種解法：(1)用教材中的快速排序算法quicksort將n油井的y坐標(biāo)排序后，容易計算出中位數(shù)median(y),由此容易求得n口油井到主管道的最小長度之和；(2)用教材中最壞情況下的線性時間選擇算法select計算出中位數(shù)median(y),然后計算n口油井到主管道的最小長度之和；(3)用教材中的隨機(jī)選擇算法randomizedselect計算出中位數(shù)median(y),然后計算n口油井到主管道的最小長度之和。下面我們比較一下它們算法計算復(fù)雜性。.時間需求(1)如果用教材中的快速排序算法QuickSort將n油井的y坐標(biāo)排序后，再計算出中位數(shù)median(y),則所需時間主要是排序算法用的時間，在平均情況下需要O(nlog(n)計算時間。(2)如果用教材中的最壞情況下的線性時間選擇算法Select計算出中位數(shù)median(y),然后計算n口油井到主管道的最小長度總和，則所需時間主要是選擇算法Select用的時間，在最壞情況下需要O(n*n)計算時間。(3)如果用教材中的隨機(jī)選擇算法RandomizedSelect計算出中位數(shù)median(y),然后計算n口油井到主管道的最