宏觀到微觀模型范式及其應(yīng)用.pdf

《宏觀到微觀模型范式及其應(yīng)用.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、宏觀到微觀模型范式及其應(yīng)用張穎鵬1陳浩忠2梁德泉2嚴(yán)哲2李昊哲2(1．華南理工大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510006；2．華南理工大學(xué)軟件學(xué)院，廣東廣州510006)【摘要]宏觀到微觀模型源于粒計(jì)算的思想。該模型的數(shù)據(jù)結(jié)構(gòu)用O(n)時(shí)間建成，并具備高度的并行性，足夠的處理器可使之在o(1)時(shí)間內(nèi)建成(n為點(diǎn)集規(guī)模)。由于插入、刪除、查詢等操作都在常數(shù)時(shí)間內(nèi)完成，且不會(huì)引起樹結(jié)構(gòu)不平衡，因此數(shù)據(jù)結(jié)構(gòu)具有良好的動(dòng)態(tài)性。此外，M2M模型的數(shù)據(jù)結(jié)構(gòu)及其預(yù)處理過程，能夠被所有基于M2M模型的算法所共享，從而大大地提高了需要多種算法共同處理的操作效率。實(shí)驗(yàn)結(jié)果表明，基于該模型的最近鄰算法和凸包算法較之對(duì)

2、應(yīng)的傳統(tǒng)算法有很大優(yōu)勢。[關(guān)鍵詞】宏觀到微觀；最近鄰算法；凸包算法；尋徑算法；層次分解1．引言人類在解決實(shí)際問題的時(shí)候，往往不是一開始就從粒度最細(xì)的層次去分析問題，而是先從宏觀出發(fā)，粗略地排除一些不必要考慮的因素，鎖定一個(gè)更窄的問題規(guī)模，然后再試圖在粒度更細(xì)的層次去解決這個(gè)問題。宏觀到微觀算法模型(M2Mmodel)就是一種模仿人類認(rèn)知思維方式的算法模型。從抽象的意義來說，宏觀微觀算法思想利用從宏觀到微觀的過程實(shí)現(xiàn)了減治的目的，探討了模擬人類解決問題從宏觀到微觀漸進(jìn)過程的新方法。M2M算法模型從模仿人類思維方式出發(fā)研究人的認(rèn)知過程。從這個(gè)角度來看，M2M模型與粒計(jì)算的思想有異曲同工之妙。它

3、們都是一個(gè)自頂向下的多層次模型。解決問題時(shí)都采取在各抽象層次之間逐步細(xì)化的過程。M2M算法模型具有普適性，是一種指導(dǎo)算法設(shè)計(jì)的模型，很多經(jīng)典算法問題和一些具體領(lǐng)域上的應(yīng)用算法問題，如最近點(diǎn)對(duì)問題、凸包問題、TSP問題、聚類問題、尋徑問題、碰撞檢測問題等都可以利用M2M模型設(shè)計(jì)出高效的算法。下面詳盡介紹了M2M算法模型及利用M_2M算法模型設(shè)計(jì)的最近鄰算法、凸包算法和尋徑算法。這些問題都是經(jīng)典的算法問題。對(duì)于最近鄰問題有基于平面點(diǎn)集的最優(yōu)算法lI】、針對(duì)最近點(diǎn)對(duì)問題的隨機(jī)算法I習(xí)、基于網(wǎng)格的方法13]，基于四叉樹的方法【4】、基于kd樹的方法【咒和最新的研究成果，如球形樹c6l等。對(duì)于凸包算

4、法問題，RonGraham提出的平面凸包算法川是最為經(jīng)典的方法，被很多研究者作為比較對(duì)象?；诜种蔚耐拱惴ǔ昂洼敵雒舾械耐拱惴ㄟ笠彩峭拱鼏栴}的有效解決方法。在實(shí)際應(yīng)用中，經(jīng)常需要在點(diǎn)集小范圍變化的情況下求凸包，動(dòng)態(tài)凸包算法也被廣泛研究；而凸包算法的隨機(jī)性研究【-01和并行性研究【“】也引起研究者的重視。2．M2M數(shù)據(jù)結(jié)構(gòu)及其范式2．1M2M數(shù)據(jù)結(jié)構(gòu)圖1數(shù)據(jù)結(jié)構(gòu)示意圖2．2M_2M數(shù)據(jù)結(jié)構(gòu)范式基于M_2M模型的數(shù)據(jù)結(jié)構(gòu)可以非常靈活，視乎具體情況和具體需求而變化。但需要滿足一些基本的條件：(1)已知數(shù)據(jù)點(diǎn)，用o(1)的時(shí)間能檢索出該點(diǎn)在指定的層所屬的分塊。(2)能夠用O(1)的時(shí)間來把該數(shù)

5、據(jù)點(diǎn)插入到M2M數(shù)據(jù)結(jié)構(gòu)中，也能夠用O(1)的時(shí)間把該數(shù)據(jù)點(diǎn)從M2M數(shù)據(jù)結(jié)構(gòu)中刪除。(3)已知某分塊的索引，用O(n)的時(shí)間能遍歷該分塊的所有子分塊，11為該分塊的子分塊數(shù)。(4)已知某分塊的索引，用O(n)的時(shí)間遍歷所有屬于該分塊的數(shù)據(jù)點(diǎn)，n為屬于該分塊的數(shù)據(jù)點(diǎn)數(shù)。(5)已知某分塊的索引，用O(1)的時(shí)間得到指定層的祖先分塊索引。(6)預(yù)處理時(shí)間復(fù)雜度為O(n)，同時(shí)支持并行處理。滿足上述條件意味著算法的基本操作，包括建樹、查詢、添加、刪除、更新等操作都達(dá)到時(shí)間復(fù)雜度的平凡下界。3．M2M數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)作者簡介：張穎鵬。男。廣東江門人．碩士研究生。研究方向：人工智能?；痦?xiàng)目：華南理工大

6、學(xué)國家大學(xué)生創(chuàng)新性實(shí)驗(yàn)計(jì)劃資助項(xiàng)目，項(xiàng)目編號(hào)：081056128。一26—為了滿足上述的基本條件，基于M2M模型的二維空間最近鄰算法和凸包算法數(shù)據(jù)結(jié)構(gòu)如下：(1)每一層用一個(gè)二維數(shù)組來保存所有屬于該層的分塊的索引。由于訪問、添加、刪除數(shù)組元素只需要常數(shù)時(shí)間，所以滿足條件1，2。(2)每一個(gè)分塊擁有其子分塊的索引列表。(3)最下層的分塊保存屬于該分塊的所有數(shù)據(jù)點(diǎn)的列表。如果要遍歷任意一層的任意分塊所包含的數(shù)據(jù)點(diǎn)，可以通過廣度優(yōu)先搜索來遍歷以該分塊作為根節(jié)點(diǎn)的樹，從而得到所有屬于該分塊的數(shù)據(jù)點(diǎn)的索引。算法還采用了額外的一些優(yōu)化措施，使到這個(gè)過程的時(shí)間復(fù)雜度接近O(n)，從而滿足條件4。(4)分

7、塊是規(guī)整的?？梢酝ㄟ^某一分塊自身的坐標(biāo)來換算出其祖先分塊的坐標(biāo)，并通過這個(gè)坐標(biāo)得出該祖先分塊的索引，這是在常數(shù)時(shí)間內(nèi)完成的，滿足條件5。(5)由于預(yù)處理是調(diào)用n次插入操作，把n個(gè)點(diǎn)插入到數(shù)據(jù)結(jié)構(gòu)里，而每個(gè)插入操作的時(shí)間復(fù)雜度是O(1)，所以預(yù)處理的時(shí)間復(fù)雜度為O(n)，滿足條件6。簡而言之，基本的M2M數(shù)據(jù)結(jié)構(gòu)是一棵四叉樹㈣(在三維的場景中是八叉樹)，并且樹的每一層都與一個(gè)橫向索引表相關(guān)聯(lián)。這個(gè)橫向索引表可以是數(shù)組也可以