從離散測地問題到動(dòng)態(tài)有序集.pdf

1、浙江大學(xué)理學(xué)院博士學(xué)位論文從離散測地問題到動(dòng)態(tài)有序集姓名：辛士慶申請學(xué)位級(jí)別：博士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：王國瑾20080415從離散測地問題到動(dòng)態(tài)有序集間復(fù)雜度卻變壞了在第一個(gè)研究方向上，我們做了以下幾項(xiàng)工作：(1)基于惠更斯的波動(dòng)原理，我們把“最短”信號(hào)在網(wǎng)格農(nóng)面上的傳播分作七種具體形式，從而成功地改造了著名的FastMarchingMethod(FMM)，得到了一個(gè)更好的求解單源多終點(diǎn)離散測地問題的近似算法(2)對jj：指定的￡，

2、我們可以在XW算法中使用以E為參數(shù)的過嚴(yán)格的窗元過濾定理，從而誘導(dǎo)出一個(gè)精度可調(diào)的近似算法當(dāng)E=0時(shí)，該近似算法恰好就是XW算法；當(dāng)E_oo時(shí)，它退化為Dijkstrw算法(3)受費(fèi)馬的光路最路原理的肩發(fā)，我們提出了一個(gè)基于可視性求解邊序列上精確最短路的高效算法在此基礎(chǔ)，卜，我們可以通過有限次的迭代把近似的初始路徑收斂到精確的局部最短路徑；在初始路徑足夠短的情況下，我們求出的路徑也是精確的全局最短路(4)從CH算法或哲XW算法中我們誘導(dǎo)

3、出。。個(gè)精確求解單源單終點(diǎn)的離散測地問題的”算法至于第二個(gè)研究方向，我們仔細(xì)分析了使用優(yōu)先隊(duì)列的經(jīng)典算法，發(fā)現(xiàn)了相似的悖論以Dijkstra算法為例，如果我們避免維護(hù)優(yōu)先隊(duì)列、代之以層次派生，則在圖接近于樹形結(jié)構(gòu)或者各邊權(quán)值非常接近的情況下，算法將由O(mnlogn)變?yōu)?(m)，其中m為圖中的有向邊的數(shù)目，n為圖巾頂點(diǎn)的數(shù)月這意味著此時(shí)維護(hù)優(yōu)先隊(duì)列是一種負(fù)擔(dān)!這有悖于我們通常的認(rèn)識(shí)一維護(hù)優(yōu)先隊(duì)列是一個(gè)普遍適應(yīng)的算法優(yōu)化技巧所以我們猜測

4、，維護(hù)優(yōu)先隊(duì)列只是一個(gè)常數(shù)時(shí)間的行為，并不會(huì)增加相關(guān)算法的復(fù)雜度為了求證這個(gè)猜測，我們思考了一個(gè)更大的問題，就是如何有效地維持關(guān)鍵字為位串的動(dòng)念有序集，以支持以下五種操作：求取最大(小)關(guān)鍵字，求取次大(小)關(guān)鍵字，查找給定的關(guān)鍵寧，插入一個(gè)關(guān)鍵字和刪除指定的關(guān)鍵字可喜的是，我們確實(shí)找到了一種巧妙的數(shù)據(jù)結(jié)構(gòu)，不妨稱之為RBT(RichBinary仉e)，它同時(shí)具備二叉搜索樹和數(shù)字查找樹的性質(zhì)；并且，所有結(jié)點(diǎn)都保存了它與祖先結(jié)點(diǎn)巾次人者和

5、次小者的最高差別位更進(jìn)一步，我ffJ提出了一套基于RBT的算法，它們可以在O(L)時(shí)間內(nèi)完成中這五種操作中的任意一個(gè)，從而維持了一個(gè)O(L)時(shí)『開J的動(dòng)態(tài)有序集，其中工為關(guān)鍵字的長度所以，RBT支持O(L)時(shí)間的查找，O(nt)時(shí)間的排序，以及O(L)時(shí)間的優(yōu)先隊(duì)列在L為常量的情況下，我們可以認(rèn)為維持優(yōu)先隊(duì)列確實(shí)不會(huì)增加相關(guān)算法的復(fù)雜度這在一定程度上詮釋了上面提出的悖論事實(shí)上，RBT可被視為一種通用的數(shù)據(jù)結(jié)構(gòu)，它能夠高效解決大多數(shù)與“序