【摘要】：圖劃分具有廣泛的應(yīng)用,例如,應(yīng)用于VLSI(大規(guī)模集成電路)設(shè)計(jì),并行計(jì)算,數(shù)據(jù)挖掘和圖像分割等,兒乎涵蓋了科學(xué)與工程的各個(gè)領(lǐng)域,因此得到了國內(nèi)外學(xué)者的普遍關(guān)注和大量研究。這些研究主要分為兩類,一類是專注于圖劃分算法的研究,另類關(guān)注的是圖劃分應(yīng)用于不同領(lǐng)域存在的問題。由于圖劃分是NP-完全問題,所以促使人們不斷給出更好的劃分方法,本文系統(tǒng)地研究了圖劃分算法和劃分工具。針對圖劃分在分布式網(wǎng)絡(luò)環(huán)境下應(yīng)用于并行計(jì)算、工業(yè)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)和路網(wǎng)(空間網(wǎng)絡(luò))數(shù)據(jù)有效存儲(chǔ)存在的問題,引入了0-1規(guī)劃理論、非線性規(guī)劃理論、組合優(yōu)化理論、聚類圖模型、聚類超圖模型以及數(shù)據(jù)聚合技術(shù)等,給出了改進(jìn)的方法和模型,并提出了相應(yīng)的驗(yàn)證算法。通過大量實(shí)驗(yàn)驗(yàn)證了所提方法和模型的正確性和有效性,解決了圖劃分在這些應(yīng)用中存在的關(guān)鍵問題。本文主要工作包括以下幾個(gè)方面： (1)對圖劃分算法進(jìn)行了系統(tǒng)、全面地概括和總結(jié),隨著圖劃分問題的不斷發(fā)展和人們研究的深入,給出了圖劃分算法當(dāng)前一些較新的研究成果,以及目前比較流行的圖劃分工具。 (2)針對圖劃分應(yīng)用于分布式并行計(jì)算只能表達(dá)對稱和雙向依賴關(guān)系的問題,提出了基于O-1規(guī)劃方法的并行計(jì)算圖劃分模型,該模型能夠表達(dá)非對稱和單向依賴關(guān)系的問題,克服了圖劃分模型表達(dá)問題的局限性,并且該模型能夠準(zhǔn)確區(qū)分通信的發(fā)送方與接收方。在一些數(shù)據(jù)集上的實(shí)驗(yàn)表明,該模型在負(fù)載均衡系數(shù)相對小的情況下比標(biāo)準(zhǔn)圖劃分模型平均減少了5%的通信量。 (3)針對標(biāo)準(zhǔn)圖劃分模型應(yīng)用于并行計(jì)算不能準(zhǔn)確表達(dá)通信量,也不能考慮通信延遲和通信量的分布情況對并行性能的影響,提出了改進(jìn)的圖劃分模型,該模型采用邊界割度量,準(zhǔn)確地表達(dá)了通信量,并使用多目標(biāo)代價(jià)函數(shù),綜合考慮了通信延遲和通信量的分布情況對并行性能的影響。在此基礎(chǔ)上,提出了更復(fù)雜的改進(jìn)超圖劃分模型,該模型既能克服圖劃分模型應(yīng)用的局限性,也能考慮通信延遲和通信量的分布情況對并行性能的影響。對提出的模型給出了相應(yīng)的驗(yàn)證算法,實(shí)驗(yàn)結(jié)果表明所提模型是正確和有效的。 (4)針對分布式網(wǎng)絡(luò)控制中的工業(yè)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)問題,提出了基于非線性0—1規(guī)劃理論對其進(jìn)行建模,然后通過互聯(lián)網(wǎng)上求解優(yōu)化問題常用的求解器NEOS服務(wù)器進(jìn)行求解,克服了使用圖劃分策略得到的結(jié)果需要進(jìn)一步近似才能得到最終問題求解的不足。在一些數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,所提方法是有效的,并且對于一些小規(guī)模的數(shù)據(jù)集要優(yōu)于圖劃分得到的結(jié)果。同時(shí),提出了非線性0—1規(guī)劃與圖劃分相結(jié)合的方法解決工業(yè)網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)問題。 (5)為了在分布式交通控制中有效的聚合查詢處理,路網(wǎng)數(shù)據(jù)應(yīng)該有效的組織和存儲(chǔ),針對這一問題提出了基于聚類圖模型的改進(jìn)方法,使用邊界割衡量后繼搜索操作的磁盤訪問代價(jià),解決了先前基于聚類圖模型不能正確表達(dá)后繼搜索操作磁盤訪問代價(jià)的不足。同時(shí)利用了磁盤記錄先前的訪問日志來估計(jì)每個(gè)網(wǎng)絡(luò)元素將來的訪問頻率和磁盤的訪問模式,然后使用圖劃分分配路網(wǎng)數(shù)據(jù)到磁盤頁,這樣可以有效地進(jìn)行路網(wǎng)數(shù)據(jù)的組織和存儲(chǔ),從而使聚合查詢處理的磁盤訪問代價(jià)最小化,并通過實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。
[Abstract]:......
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2012
【分類號】：TP333.35;TP301.6

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 楊月輝;車聯(lián)網(wǎng)路側(cè)單元?jiǎng)討B(tài)聯(lián)盟形成算法研究[D];大連理工大學(xué);2013年

，

本文編號：2457826