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

2、效率，采用了算法中以分治法為基礎的隨機劃分來解決問題，利用隨機選擇方法找到各個油井的中位數(shù)，通過討論論證了中位數(shù)即最優(yōu)管道位置。 信息奧賽中一個問題有多個算法解決，通過比較不同算法解決問題的效率，選擇最高效的一個。在輸油管道問題這個實驗中得到運用。關鍵詞：算法設計，分治法，隨機劃分，隨機選擇，中位數(shù)目錄1 需求分析41.1 實驗內(nèi)容41.2 系統(tǒng)的基本邏輯模型41.3 確定目標系統(tǒng)的功能.52 總體設計52.1問題分析52.2解題思路62.3解題方法.72.3.1算法思想.72.3.2算法分析.73 詳細設計93.1 具體描述93.2 程序分析113.2.1程序代碼.113.2.2程序結果.1

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

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

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

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

7、優(yōu)的位置使得各油井到主管道之間的輸油管道長度總和更小，這與假設矛盾。油井數(shù)目為偶數(shù)：證明情況同奇數(shù)情況。不同的是主管道的最優(yōu)位置y坐標可以是各油井坐標的兩個中位數(shù)之間的任一整數(shù)。2.3.解題方法通過我們對數(shù)據(jù)結構和算法設計的學習，為了求得中位數(shù)，我們先通過劃分算法對所有油井y坐標進行排序，然后通過隨機選擇方法RandomizedSelect得到中位數(shù)。2.3.1算法思想分治算法的基本思想是將一個規(guī)模個為N的問題分解為K規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。2.3.2算法分析分治算法是很多高效算法的基礎，如排序算法（快速排序、歸并排序）、傅立

8、葉變換（快速傅立葉變換）。快速排序是由東尼霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要(n lg n)次比較。在最壞狀況下則需要(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他(n lg n) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。在此題中，我們考慮到時間復雜度，對于中位數(shù)這類選擇問題的解決，不一定要先排序然后遍歷（事實上這是比較慢的做法，排序的時間復雜度決定了它不可能比O（nlgn）快。通常選擇問題只是要求知道第i大/小的元素，所

9、以我們可以將本實驗的問題當成排序算法的簡化。我們就以上述的快速排序為例，我們以劃分的區(qū)間判斷，選擇問題我們只追究可能出現(xiàn)問題解的一個區(qū)間，而快速排序要處理兩個區(qū)間。由此，我們可以清晰的明白利用隨機劃分解決此問題可以縮短時間復雜度。利用數(shù)據(jù)結構教材中的隨機選擇算法RandomizedSelect計算出中位數(shù)median(y)，然后計算n 口油井到主管道的最小長度總和，則所需時間主要是隨機選擇算法RandomizedSelect用的時間，在平均情況下需要O(n)計算時間。3.詳細設計3.1具體描述詳細設計階段的根本任務是確定應該怎樣具體實現(xiàn)所要求的輸油管道定位問題，也就是經(jīng)過這個階段的設計工作，應

10、該得出對輸油管道問題的精確描述，從而在輸油管道定位的實現(xiàn)階段可以把這個描述直接翻譯成用某種程序設計語言書寫的程序。把經(jīng)過總體設計得到的各個模塊詳細的加以描述。根據(jù)油井的y坐標求出中位數(shù) 打開文件從文件讀取油田數(shù)目將各個油井的坐標賦給指針a根據(jù)中位數(shù)求出最短距離 3-1.總體結構圖返回劃分后基數(shù)的位置N將各個油井的y坐標按從大到小的順序排列float i=p,j=r+1float x=apA+ix&ixi=jSwap(ai=aj)YYNNYAj=xReturn jap=ajfloat*a,float p,r 3-2.patition算法設計圖獲取劃分后隨機基數(shù)的位置如果基數(shù)在中間數(shù)的左邊則重復進

11、行以上操作如果基數(shù)在中間數(shù)的右邊則重復進行以上操作如果基數(shù)在中間則返回基數(shù)的值獲取基數(shù)距第一個數(shù)的長度NYFloat*a, floatp,r,kprReturn api=randomizepatition(a,p,r)Floatj=i-p+1K=jReturn ajKsize;int *a=new intsize;int readcount=1,i=0;while(readcounttemp;if(readcount%2=0)ai+=temp;readcount+;input.close();/獲取數(shù)據(jù)中位數(shù)，即為通道Y坐標int length=RandomizedSelect(a,0,siz

12、e-1,(size+1)/2); printf(最佳位置y=%dn,length); printf(最短距離已保存在文件中！);/將總的管道長度寫入out.txt文件中write(outFileName,lengthOfPipeline(a,size,length);system(pause);return 0;Patition（劃分）函數(shù)的作用：將一串數(shù)據(jù)由大到小進行排序，最后返回劃分時所用基數(shù)的位置float Partition(float *a,float p,float r)float i = p, j = r + 1;float x = ap;/將x的元素交換到左邊區(qū)域while(t

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

14、擇）函數(shù)的作用：找到排序后數(shù)據(jù)的中位數(shù)float RandomizedSelect(float *a,float p,float r,float k)if(p=r)return ap;float i = RandomizedPartition(a,p,r);/將隨機基數(shù)的為位置賦給i float j = i-p+1;/獲取基數(shù)距第一個數(shù)的長度if (k = j) return ai;/如果基數(shù)在中間則返回基數(shù)的值if(kj) return RandomizedSelect(a,p,i-1,k);/如果基數(shù)在中間數(shù)的右邊則重復進行以上操作Else return RandomizedSelect(

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

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