宏观到微观模型范式及其应用.pdf

《宏观到微观模型范式及其应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、宏观到微观模型范式及其应用张颖鹏1陈浩忠2梁德泉2严哲2李昊哲2(1．华南理工大学计算机学院，广东广州510006；2．华南理工大学软件学院，广东广州510006)【摘要]宏观到微观模型源于粒计算的思想。该模型的数据结构用O(n)时间建成，并具备高度的并行性，足够的处理器可使之在o(1)时间内建成(n为点集规模)。由于插入、删除、查询等操作都在常数时间内完成，且不会引起树结构不平衡，因此数据结构具有良好的动态性。此外，M2M模型的数据结构及其预处理过程，能够被所有基于M2M模型的算法所共享，从而大大地提高了需要多种算法共同处理的操作效率。实验结果表明，基于该模型的最近邻算法和凸包算法较之对

2、应的传统算法有很大优势。[关键词】宏观到微观；最近邻算法；凸包算法；寻径算法；层次分解1．引言人类在解决实际问题的时候，往往不是一开始就从粒度最细的层次去分析问题，而是先从宏观出发，粗略地排除一些不必要考虑的因素，锁定一个更窄的问题规模，然后再试图在粒度更细的层次去解决这个问题。宏观到微观算法模型(M2Mmodel)就是一种模仿人类认知思维方式的算法模型。从抽象的意义来说，宏观微观算法思想利用从宏观到微观的过程实现了减治的目的，探讨了模拟人类解决问题从宏观到微观渐进过程的新方法。M2M算法模型从模仿人类思维方式出发研究人的认知过程。从这个角度来看，M2M模型与粒计算的思想有异曲同工之妙。它

3、们都是一个自顶向下的多层次模型。解决问题时都采取在各抽象层次之间逐步细化的过程。M2M算法模型具有普适性，是一种指导算法设计的模型，很多经典算法问题和一些具体领域上的应用算法问题，如最近点对问题、凸包问题、TSP问题、聚类问题、寻径问题、碰撞检测问题等都可以利用M2M模型设计出高效的算法。下面详尽介绍了M2M算法模型及利用M_2M算法模型设计的最近邻算法、凸包算法和寻径算法。这些问题都是经典的算法问题。对于最近邻问题有基于平面点集的最优算法lI】、针对最近点对问题的随机算法I习、基于网格的方法13]，基于四叉树的方法【4】、基于kd树的方法【咒和最新的研究成果，如球形树c6l等。对于凸包算

4、法问题，RonGraham提出的平面凸包算法川是最为经典的方法，被很多研究者作为比较对象。基于分治的凸包算法嘲和输出敏感的凸包算法唧也是凸包问题的有效解决方法。在实际应用中，经常需要在点集小范围变化的情况下求凸包，动态凸包算法也被广泛研究；而凸包算法的随机性研究【-01和并行性研究【“】也引起研究者的重视。2．M2M数据结构及其范式2．1M2M数据结构图1数据结构示意图2．2M_2M数据结构范式基于M_2M模型的数据结构可以非常灵活，视乎具体情况和具体需求而变化。但需要满足一些基本的条件：(1)已知数据点，用o(1)的时间能检索出该点在指定的层所属的分块。(2)能够用O(1)的时间来把该数

5、据点插入到M2M数据结构中，也能够用O(1)的时间把该数据点从M2M数据结构中删除。(3)已知某分块的索引，用O(n)的时间能遍历该分块的所有子分块，11为该分块的子分块数。(4)已知某分块的索引，用O(n)的时间遍历所有属于该分块的数据点，n为属于该分块的数据点数。(5)已知某分块的索引，用O(1)的时间得到指定层的祖先分块索引。(6)预处理时间复杂度为O(n)，同时支持并行处理。满足上述条件意味着算法的基本操作，包括建树、查询、添加、删除、更新等操作都达到时间复杂度的平凡下界。3．M2M数据结构的实现作者简介：张颖鹏。男。广东江门人．硕士研究生。研究方向：人工智能。基金项目：华南理工大

6、学国家大学生创新性实验计划资助项目，项目编号：081056128。一26—为了满足上述的基本条件，基于M2M模型的二维空间最近邻算法和凸包算法数据结构如下：(1)每一层用一个二维数组来保存所有属于该层的分块的索引。由于访问、添加、删除数组元素只需要常数时间，所以满足条件1，2。(2)每一个分块拥有其子分块的索引列表。(3)最下层的分块保存属于该分块的所有数据点的列表。如果要遍历任意一层的任意分块所包含的数据点，可以通过广度优先搜索来遍历以该分块作为根节点的树，从而得到所有属于该分块的数据点的索引。算法还采用了额外的一些优化措施，使到这个过程的时间复杂度接近O(n)，从而满足条件4。(4)分

7、块是规整的。可以通过某一分块自身的坐标来换算出其祖先分块的坐标，并通过这个坐标得出该祖先分块的索引，这是在常数时间内完成的，满足条件5。(5)由于预处理是调用n次插入操作，把n个点插入到数据结构里，而每个插入操作的时间复杂度是O(1)，所以预处理的时间复杂度为O(n)，满足条件6。简而言之，基本的M2M数据结构是一棵四叉树㈣(在三维的场景中是八叉树)，并且树的每一层都与一个横向索引表相关联。这个横向索引表可以是数组也可以