軟件工程論文下載軟件工程論文范文基于《數(shù)字礦山》軟件中礦體平均品位

1、軟件工程論文下載軟件工程論文范文：基于數(shù)字礦山軟件中礦體平均品位自動(dòng)生成技術(shù)的研究和應(yīng)用摘 要： 以數(shù)字礦山軟件GeoView3D平臺(tái)為依托，通過改進(jìn)的深度優(yōu)先搜索算法（MDFS）來搜索現(xiàn)有克里格插值的品位所在的范圍，并用三次多項(xiàng)式曲線擬合計(jì)算平均品位，以實(shí)現(xiàn)以較快的速度計(jì)算出鼠標(biāo)所在位置的平均品位，提高軟件的可視化程度。MDFS算法通過模擬迷宮的有向圖是有向無環(huán)圖，而且對鄰接表的表頭節(jié)點(diǎn)增設(shè)一個(gè)數(shù)據(jù)域的方式降低算法的時(shí)間復(fù)雜度，提高運(yùn)算速度。關(guān)鍵詞： 數(shù)字礦山；搜索算法；曲線擬合；礦體品位0 引言中國地質(zhì)大學(xué)與紫金礦業(yè)集團(tuán)公司合作開發(fā)的數(shù)字礦山軟件，是一套功能比較完整，適合礦山儲(chǔ)量計(jì)算、設(shè)計(jì)

2、的軟件。該軟件同時(shí)擁有我國傳統(tǒng)儲(chǔ)量計(jì)算方法和國際通用的地質(zhì)統(tǒng)計(jì)學(xué)儲(chǔ)量計(jì)算兩種計(jì)算方式。由于地質(zhì)統(tǒng)計(jì)學(xué)是基于克里格法，用三維建模計(jì)算，相對更科學(xué)、更準(zhǔn)確，并能直接使用于礦山設(shè)計(jì)?，F(xiàn)在國內(nèi)儲(chǔ)量計(jì)算提倡使用地質(zhì)統(tǒng)計(jì)學(xué)方法。這套軟件仍處于開發(fā)期，本研究結(jié)合此項(xiàng)目，在已有的功能上，增加一些比較實(shí)用的功能，如點(diǎn)擊鼠標(biāo)計(jì)算區(qū)域內(nèi)平均品位。決策者往往需要估算剖面的一塊區(qū)域的平均品位，大致了解一下這一區(qū)域礦體的貧富程度，遺憾的是現(xiàn)在軟件并無這一功能。而增加這一功能后無疑會(huì)大大方便使用者。本文主要是通過改進(jìn)的深度優(yōu)先算D-BFS算法搜索現(xiàn)有克里格插值的品位所在的范圍，范圍由鼠標(biāo)所在位置的品位范圍確定。平均品位的計(jì)

3、算方法用三次多項(xiàng)式曲線擬合計(jì)算。本文的研究目的和意義就在于解決面對剖面圖無法"目測"所關(guān)注區(qū)域的平均品位的問題，增加了這個(gè)功能之后，清晰準(zhǔn)確的數(shù)據(jù)一目了解地展現(xiàn)在專家的面前，無疑會(huì)對他們的指導(dǎo)工作提供較大方便。1 D-BFS算法1.1 廣度優(yōu)先搜索算法計(jì)算機(jī)解決問題的第一步就是根據(jù)問題建立相應(yīng)的數(shù)學(xué)模型，或者說根據(jù)問題的邏輯關(guān)系設(shè)計(jì)一個(gè)較為合理的存儲(chǔ)結(jié)構(gòu)。把剖面圖中的每一個(gè)插值位置當(dāng)成一個(gè)節(jié)點(diǎn)來處理，那么整個(gè)剖面圖就會(huì)變成一張圖，只是在圖中要能區(qū)分"通"和"阻塞"兩種情況，只不過在這樣一個(gè)具體問題中，要走通整個(gè)迷宮，所關(guān)注的問題是&q

4、uot;通"，所以在圖中只要能表示"通"的情況就可以了，這樣還會(huì)減少需要處理的頂點(diǎn)的個(gè)數(shù)。圖的入口即為鼠標(biāo)所在的位置。1.2 D-BFS算法中的數(shù)據(jù)結(jié)構(gòu)為了降低空間復(fù)雜度，把圖當(dāng)成一個(gè)有向圖來處理，利用鄰接表來存儲(chǔ)這張有向圖。本文假設(shè)模擬迷宮的有向圖是有向無環(huán)圖，而且對鄰接表的表頭節(jié)點(diǎn)增設(shè)一個(gè)數(shù)據(jù)域（outdegree），即頂點(diǎn)的出度，用來判斷該頂點(diǎn)是否出口。如果一個(gè)頂點(diǎn)的出度大于1，則通過該頂點(diǎn)有多條路徑，為了避免在這多條路徑中循環(huán)遍歷，為每個(gè)節(jié)點(diǎn)設(shè)立一個(gè)訪問標(biāo)志visited，初值為假，當(dāng)訪問后該標(biāo)志為真。用一堆棧來保存成功路徑，如果沒有成功路徑，最后堆棧為空

5、。以圖的入口為開始頂點(diǎn)（如圖1中頂點(diǎn)A）進(jìn)行廣度優(yōu)先遍歷該有向圖。本文對深度優(yōu)先搜索算法作了以下改進(jìn).。首先，利用訪問標(biāo)志visited來避免對經(jīng)過同一頂點(diǎn)的多條路徑進(jìn)行重復(fù)訪問；其次，圖中可能存在入度（indegree）大于1的頂點(diǎn)，即存在多條路徑進(jìn)入同一頂點(diǎn)，稱這樣的頂點(diǎn)為匯點(diǎn)（meetvertex，MV）。為了找到迷宮中所有可行路徑，在一個(gè)頂點(diǎn)出棧時(shí)，要恢復(fù)經(jīng)過該頂點(diǎn)所能到達(dá)頂點(diǎn)的訪問標(biāo)志；第三，在圖路徑中存在絕路頂點(diǎn)（impasse vertex，IV），如圖1中頂點(diǎn)L，在尋找更多可行路徑時(shí)，不對絕路頂點(diǎn)及經(jīng)過絕路頂點(diǎn)的路徑進(jìn)行重復(fù)探索，因此在第一次尋找可行路徑時(shí)要對絕路頂點(diǎn)作絕路頂點(diǎn)

6、標(biāo)記，結(jié)合訪問標(biāo)志visited來實(shí)現(xiàn)。所以，在迷宮較復(fù)雜、絕路頂點(diǎn)較多時(shí)，D-BFS較傳統(tǒng)算法會(huì)有更好的搜索效率。根據(jù)上述修改可得如下M-BFS算法思想：假設(shè)堆棧棧頂節(jié)點(diǎn)為V，則鄰接于V的所有節(jié)點(diǎn)位于以V為頭節(jié)點(diǎn)的單鏈表中，所以只要在這根單鏈表中搜索一個(gè)未被訪問的節(jié)點(diǎn)V1，如果V1的出度為0，則V1可能是出口或絕路頂點(diǎn)，否則V1進(jìn)入堆棧繼續(xù)訪問。如果鄰接于V的所有節(jié)點(diǎn)都已被訪問，則V出棧，恢復(fù)鄰接于V的非絕路節(jié)點(diǎn)的訪問標(biāo)志，如果鄰接于V的所有節(jié)點(diǎn)都是絕路節(jié)點(diǎn)，則V也是絕路節(jié)點(diǎn)（如圖1中L，鄰接于L的兩個(gè)節(jié)點(diǎn)M和N都是絕路節(jié)點(diǎn)，則L也是絕路節(jié)點(diǎn)），當(dāng)再尋找其它可行路徑時(shí)，經(jīng)過D就不再到L，更不

7、可能到M和N，當(dāng)迷宮中絕路節(jié)點(diǎn)很多時(shí)，這會(huì)節(jié)省大量的搜索時(shí)間，應(yīng)作相應(yīng)的絕路標(biāo)志，同時(shí)V的訪問標(biāo)志置為（1）以新的棧頂節(jié)點(diǎn)繼續(xù)訪問。相應(yīng)的算法描述D-BFS算法。2 加權(quán)平均品位值計(jì)算2.1 加權(quán)平均品位計(jì)算公式視單工程品位為沿某一直線方向品位指標(biāo)值的直方圖和多形圖，設(shè)圖中的直方圖間距分別為Ll，L2，Ln。L=Ll+L2+=Ln（L為取樣品位跨度），與其相對應(yīng)的品位指標(biāo)值分別為C，q，Cn?，F(xiàn)按常規(guī)的加權(quán)平均值計(jì)算法計(jì)算品位平均值，有：2.2 算法分析對有n個(gè)頂點(diǎn)的迷宮圖，在傳統(tǒng)的解法中，所需要的存儲(chǔ)空間至少是O（n2）。如果用有向圖來表示一個(gè)迷宮，而采用鄰接表可大大降低空間復(fù)雜度，因?yàn)猷徑?/p>

8、表中不會(huì)存放障礙節(jié)點(diǎn)以及永遠(yuǎn)不能到達(dá)的離散的通路節(jié)點(diǎn)。雖然存在一定的結(jié)構(gòu)性的開銷，當(dāng)迷宮很復(fù)雜而且規(guī)模較大時(shí)，鄰接表較數(shù)組有良好的空間復(fù)雜度。由于對DFS算法進(jìn)行了適當(dāng)改進(jìn)，只需調(diào)用一次D-BFS算法就能找出迷宮中所有的可行路徑，而且在找更多可行路徑時(shí)，搜索效率較數(shù)組有較大改善。另外，當(dāng)某個(gè)頂點(diǎn)被標(biāo)志為絕路頂點(diǎn)，就不會(huì)再從它出發(fā)進(jìn)行搜索，尋找迷宮路徑的過程就是查找其鄰接點(diǎn)的過程，用鄰接表作為其存儲(chǔ)結(jié)構(gòu)，搜索鄰接點(diǎn)所需時(shí)間為O（e），其中e為有向圖弧的條數(shù)，因此在迷宮規(guī)模較大而且很復(fù)雜時(shí)，絕路頂點(diǎn)可能會(huì)很多，這時(shí)M-DFS算法會(huì)有更好的搜索效果。參考文獻(xiàn)：1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）M.北京：清華大學(xué)出版社，2001.2 李俊英，等.熱液金屬礦床特高品位問題