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

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

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

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

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

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