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

張穎鵬陳浩忠梁德泉嚴(yán)哲李昊哲

(1.華南理工大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510006；2.華南理工大學(xué)軟件學(xué)院，廣東廣州510006)

1.引言

人類在解決實(shí)際問題的時(shí)候，往往不是一開始就從粒度最細(xì)的層次去分析問題，而是先從宏觀出發(fā)，粗略地排除一些不必要考慮的因素，鎖定一個(gè)更窄的問題規(guī)模，然后再試圖在粒度更細(xì)的層次去解決這個(gè)問題。宏觀到微觀算法模型(M2M model)就是一種模仿人類認(rèn)知思維方式的算法模型。從抽象的意義來說，宏觀微觀算法思想利用從宏觀到微觀的過程實(shí)現(xiàn)了減治的目的，探討了模擬人類解決問題從宏觀到微觀漸進(jìn)過程的新方法。

M2M算法模型從模仿人類思維方式出發(fā)研究人的認(rèn)知過程。從這個(gè)角度來看，M2M模型與粒計(jì)算的思想有異曲同工之妙。它們都是一個(gè)自頂向下的多層次模型。解決問題時(shí)都采取在各抽象層次之間逐步細(xì)化的過程。

M2M算法模型具有普適性，是一種指導(dǎo)算法設(shè)計(jì)的模型，很多經(jīng)典算法問題和一些具體領(lǐng)域上的應(yīng)用算法問題，如最近點(diǎn)對問題、凸包問題、TSP問題、聚類問題、尋徑問題、碰撞檢測問題等都可以利用M2M模型設(shè)計(jì)出高效的算法。

下面詳盡介紹了M2M算法模型及利用M2M算法模型設(shè)計(jì)的最近鄰算法、凸包算法和尋徑算法。這些問題都是經(jīng)典的算法問題。對于最近鄰問題有基于平面點(diǎn)集的最優(yōu)算法[1]、針對最近點(diǎn)對問題的隨機(jī)算法[2]、基于網(wǎng)格的方法[3]，基于四叉樹的方法[4]、基于kd樹的方法[5]和最新的研究成果，如球形樹[6]等。對于凸包算法問題，Ron Graham提出的平面凸包算法[7]是最為經(jīng)典的方法，被很多研究者作為比較對象?；诜种蔚耐拱惴╗8]和輸出敏感的凸包算法[9]也是凸包問題的有效解決方法。在實(shí)際應(yīng)用中，經(jīng)常需要在點(diǎn)集小范圍變化的情況下求凸包，動(dòng)態(tài)凸包算法也被廣泛研究；而凸包算法的隨機(jī)性研究[10]和并行性研究[11]也引起研究者的重視。

2.M 2 M數(shù)據(jù)結(jié)構(gòu)及其范式

2.1 M2M數(shù)據(jù)結(jié)構(gòu)

2.2 M2M數(shù)據(jù)結(jié)構(gòu)范式

基于M2M模型的數(shù)據(jù)結(jié)構(gòu)可以非常靈活，視乎具體情況和具體需求而變化。但需要滿足一些基本的條件：

(1)已知數(shù)據(jù)點(diǎn)，用O(1)的時(shí)間能檢索出該點(diǎn)在指定的層所屬的分塊。

(2)能夠用O(1)的時(shí)間來把該數(shù)據(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í)間能遍歷該分塊的所有子分塊，n為該分塊的子分塊數(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.M 2 M數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

為了滿足上述的基本條件，基于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)分塊是規(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)是一棵四叉樹[12](在三維的場景中是八叉樹)，并且樹的每一層都與一個(gè)橫向索引表相關(guān)聯(lián)。這個(gè)橫向索引表可以是數(shù)組也可以用hash表作為存儲(chǔ)結(jié)構(gòu)。使用hash技術(shù)后，算法的空間復(fù)雜度為O(n)，與四叉樹、KD樹等傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的空間消耗在復(fù)雜度上相同。

4.M 2 M數(shù)據(jù)結(jié)構(gòu)與常見數(shù)據(jù)結(jié)構(gòu)的比較

在這里重點(diǎn)的比較對象是層次分解空間數(shù)據(jù)結(jié)構(gòu)，主要包括BSP樹，四叉樹，R樹與及它們的變體。相較于這些數(shù)據(jù)結(jié)構(gòu)來說，M2M數(shù)據(jù)結(jié)構(gòu)：

(1)添加和刪除操作是自底向上的，且不必判斷與劃分面的關(guān)系，時(shí)間復(fù)雜度的期望值為O(1)。

(2)不必保存劃分面，節(jié)省空間開銷。

(3)由于每層都可以利用分塊的索引在橫向索引表中查找出該分塊，所以查詢的時(shí)間復(fù)雜度也為O(1)，而且不受樹狀拓?fù)浣Y(jié)構(gòu)的不平衡性所影響。

(4)在劃分因素比較小的時(shí)候可以不保存父分塊指向子分塊的索引，從而節(jié)省內(nèi)存開銷。

(5)由于數(shù)據(jù)結(jié)構(gòu)的每一層都與一個(gè)橫向索引相關(guān)聯(lián)，從而可以快速地進(jìn)行索引搜索。其中，通過索引搜索鄰近節(jié)點(diǎn)經(jīng)常被用到。

(6)由于采用規(guī)整的分塊方式，并且可以取消父分塊對子分塊的索引表，因而插入、添加操作具有高度的并行性。

(7)由于M2M數(shù)據(jù)結(jié)構(gòu)的每一層需要維護(hù)一個(gè)橫向索引表，所以內(nèi)存開銷會(huì)比其它的樹結(jié)構(gòu)要更大一些。尤其當(dāng)場景屬于稀疏場景，而且對場景的分層的最底層粒度比較小的時(shí)候。針對這種情況，可以考慮使用哈希表作為較低層的橫向索引數(shù)據(jù)結(jié)構(gòu)。但這樣做會(huì)增加一定的查詢開銷。而各種操作的時(shí)間復(fù)雜度都保持不變。另外，使用哈希表會(huì)有損于數(shù)據(jù)結(jié)構(gòu)的并行性。

簡而言之，M2M數(shù)據(jù)結(jié)構(gòu)涵蓋了其它層次分解空間數(shù)據(jù)結(jié)構(gòu)的操作能力，基本操作的時(shí)間復(fù)雜度要更低一些，而且具備很好的并行性。此外M2M數(shù)據(jù)結(jié)構(gòu)還提供了通過橫向索引查詢鄰近分塊的操作。

5.M 2 M算法范式及實(shí)驗(yàn)結(jié)果

5.1 M2M算法范式

M2M算法一般包括兩個(gè)階段，一個(gè)是預(yù)處理階段，另一個(gè)是解決具體問題的階段。針對不同的問題具體上有不同的算法，統(tǒng)稱之為查詢階段。而更新過程會(huì)發(fā)生在需要對數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)時(shí)更改的時(shí)候。這個(gè)過程是針對數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的，所以對于不同的問題，其操作是相同的。

預(yù)處理過程：對歐幾里得空間點(diǎn)集從上層到下層建立層次表示，從粗到細(xì)劃分粒度，在每一層把解空間劃分為大小均勻的分塊。這個(gè)過程就是建立M2M數(shù)據(jù)結(jié)構(gòu)的過程。

更新過程：對已經(jīng)建立好的數(shù)據(jù)結(jié)構(gòu)實(shí)時(shí)進(jìn)行添加、刪除、更新等操作。

查詢過程：

(1)從最上層開始，把全局空間作為初始搜索空間。

(2)把當(dāng)前層搜索空間中每個(gè)分塊抽象成點(diǎn)，得到一個(gè)點(diǎn)集。根據(jù)所求解問題，用相應(yīng)的方法把明顯不屬于解空間的點(diǎn)從該點(diǎn)集中剔除。再將點(diǎn)集中剩余的點(diǎn)所代表的分塊作為粒度更細(xì)的下一層的搜索空間。

(3)進(jìn)入下一層重復(fù)2)過程，直到粒度適合的層。

(4)在粒度適合的層的搜索空間中對問題直接求解。

5.2 最近鄰算法實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)比較基于M2M模型的最近鄰算法和基于KD樹數(shù)據(jù)結(jié)構(gòu)的最近鄰算法。其中KD樹的代碼來自于Sebastian Nowozin[13]。

5.2.1 預(yù)處理時(shí)間的比較

從圖2可以看出，實(shí)驗(yàn)結(jié)果基本上符合理論分析的結(jié)果。在KD樹的預(yù)處理過程中，由于每次都需要選擇好的pivot，需要log(n)的復(fù)雜度，所以建樹的時(shí)間復(fù)雜度是n log(n)。基于M2M模型的算法的預(yù)處理過程時(shí)間復(fù)雜度為O(n)，所以其曲線接近一條直線。

5.2.2 求最近鄰時(shí)間的比較

圖3是最近鄰算法查詢階段耗時(shí)的比較，實(shí)驗(yàn)結(jié)果符合理論分析結(jié)果。因?yàn)橐獜臉浣Y(jié)構(gòu)里找出目標(biāo)點(diǎn)所在的分塊，基于KD樹的求最近鄰算法的時(shí)間復(fù)雜度是近似于log(n)，而基于M2M思想的求最近鄰算法的時(shí)間復(fù)雜度近似O(1)。

5.3 凸包算法實(shí)驗(yàn)結(jié)果

為了更好地研究M2M凸包算法的性能，通過編程實(shí)現(xiàn)了M2M凸包算法并且與經(jīng)典凸包算法進(jìn)行比較。實(shí)驗(yàn)進(jìn)行的比較對象分別是：Graham scan[14]，quick hull[15]和Jarvis march[16]。在實(shí)驗(yàn)中隨機(jī)生成均勻分布的點(diǎn)集，并考察不同算法對不同規(guī)模同一點(diǎn)集求凸包的效率。實(shí)驗(yàn)環(huán)境與最近鄰算法相同。圖4是實(shí)驗(yàn)結(jié)果：

圖4從上到下的曲線分別是Jarvis march，quick hull，Graham scan和M2M凸包算法這4種算法預(yù)處理的耗時(shí)。從實(shí)驗(yàn)結(jié)果可以得到，當(dāng)點(diǎn)集的規(guī)模比較小的時(shí)候，Graham scan算法的耗時(shí)最少，而M2M凸包算法由于需要預(yù)處理，其耗時(shí)最多。但隨著點(diǎn)集的規(guī)模增大，M2M凸包算法的優(yōu)勢漸漸顯示出來，當(dāng)點(diǎn)集規(guī)模目到達(dá)100萬級的時(shí)候，M2M凸包算法的耗時(shí)大概是Graham scan算法耗時(shí)的一半。

6.結(jié)語

M2M模型提供了一個(gè)多層次、粒度可選的數(shù)據(jù)結(jié)構(gòu)，從而可靈活地選擇不同的抽象層次去解決不同粒度的問題。通過對M2M算法的理論和實(shí)驗(yàn)的分析，可總結(jié)出基于M2M模型的算法具有如下共同特性：

(1)預(yù)處理共享：算法的預(yù)處理過程對大部分問題是相同的。對于一些高級應(yīng)用，比如模式識別、圖形圖象處理，往往需要對于相同的圖片(點(diǎn)集)作各種處理，而很多處理都可以設(shè)計(jì)基于M2M模型的相應(yīng)算法，這些算法可以共享預(yù)處理過程。而預(yù)處理過程占算法本身大部分的耗時(shí)，以M2M凸包算法為例，實(shí)驗(yàn)結(jié)果表明，預(yù)處理時(shí)間占據(jù)整個(gè)算法95%以上的時(shí)耗，當(dāng)多個(gè)算法都共享共同的預(yù)處理過程時(shí)，可以大大地提高整體處理的效率。

(2)高度并行性：M2M算法的預(yù)處理過程可以并行執(zhí)行。此外，很多M2M算法也可以并行執(zhí)行，可以通過GPU、多CPU、多核等技術(shù)來大幅提高M(jìn)2M算法的效率。

(3)多層結(jié)構(gòu)，粒度可選：M2M數(shù)據(jù)結(jié)構(gòu)提供了不同粒度的抽象層次，以便在解決具體問題的時(shí)候可以選擇粒度恰當(dāng)?shù)膶哟稳ソ鉀Q，而不必每次都關(guān)注粒度最細(xì)的層次。該算法在宏觀到微觀的過程中，在粒度較粗的層中僅保留有可能包含解的分塊，因此每一層求解后都縮小了解的搜索空間，從而逐步細(xì)化，最終求出精確的解。

(4)效率與精確度的互轉(zhuǎn)換：犧牲解的精確度從而縮短算法解決問題的時(shí)間。經(jīng)過簡單的調(diào)整而成為一個(gè)近似算法，可以靈活地實(shí)現(xiàn)算法效率和解的精確性互轉(zhuǎn)換。

(5)效率與空間消耗的互轉(zhuǎn)換：宏觀－微觀算法的層次數(shù)目及分塊方式可以自定義。一般來說分層越充分，上下層之間的分塊數(shù)目比越小，算法的空間消耗越大，算法的效率越高，這樣就可以靈活地實(shí)現(xiàn)算法效率和內(nèi)存空間之間的互轉(zhuǎn)換。

(6)層次空間分解：M2M數(shù)據(jù)結(jié)構(gòu)屬于一種層次空間分解技術(shù)，尤其適用于大規(guī)模場景中相關(guān)問題的求解。M2M模型兼?zhèn)淞烁咝浴?dòng)態(tài)性和并行性等性質(zhì)，能夠很好地解決大規(guī)模場景中的相關(guān)問題。

；

[1]SHAMOS，M.I，AND HOEY，D.Closest-point problems Proc 16th IEEE Syrup.Foundatmns of Computer Scwnce，pp.151-162，Oct 1975.

[2]RABIN，MO.Probabilistic algorithms，in Algorithms and Complexity：New Dwectmns and Recent Results，J.F.Traub(Ed.)，Academic Press，New York，pp.21-39，1976.

[3]BENTLEY，J.L.，WEIDE，B.W.，AND YAO，A.C.Optimal expected-time algorithms for closest point problems.ACM Trans.Math.Softw.6，4，563-580，1980.

[4]BERN，M.1993.Approximate closest-point queries in high dimensions.Inf.Proc.Lett.45，95-99.

[5]J.H.Friedman，J.L.Bentley，and R.A.Finkel.An algorithm ffor finding best matches in logarithmic expected time.ACM Transactions on Mathematical Software，3(3)：209-226，September 1977.

[6]T.Liu，A.W.Moore，and A.Gray.Efficient exact k-NN and nonparametric classification in high dimensions.In S.Thrun，L.Saul，and B.Sch olkopf，editors，Advances in Neural Information Processing Systems 16.MIT Press，Cambridge，MA，2004.

[7]T.H.Cormen，C.E.Leiserson，R.L.Rivest，and C.Stein，Introduction to Algorithms(2 nd E.)，MIT Press，McGraw-Hill，New York，USA，2001.

[8]Sebastian Nowozin.A vanilla k-d tree implementation 2004.

[9]R.L.Graham，An efficient algorithm for determining the convex hull of a finite planar set，Information Processing Letters 1(1972)132-133.

[10]Clarkson，K.L.New applications of random sampling in computational geometry.Discrete Comput.Geom.2(1987)：195-222.

[11]M.H.Overmars and J.van Leeuwen.Maintenance of configurations in the plane.J.Comput.System Sci.，23(2)：166，204，1981.

[12]邱建華，唐學(xué)兵，黃華國.一種基于四叉樹和R～*-樹的索引結(jié)構(gòu)——QR～*-樹[J].計(jì)算機(jī)應(yīng)用，2003，(08).

[13]Sebastian Nowozin.A vanilla k-d tree implementation 2004.

[14]R.L.GrahamAn efficient algorithm for determining the convex hull of a finite planar set，Information Processing Letters 1(1972)132-133.

[15]F.P.Preparata，S.J.Hong，Convex hulls of finite point sets in two and three dimensions，Communications of the ACM 2(20)(1977)87-93.

[16]A.Jarvis，On the identification of the convex hull of a finite set of points in the plane，Information Processing Letters 2(1973)18-21.