摘要
通过改进FRT算法,得到随机最小序分割算法(random minimum order partition,RMOP)。在度量空间G中,对点列V进行随机排序(设序列为π),随机选取点u∈V后,获得下标J r(u)=inf{j∈N:d(πj,u)≤r,πj,u∈V},再以点πJr(u)为球心r为半径,对度量空间G进行递归分割,进而形成一棵分层良分割树(hierarchically well separated tree,HST);同时得到E(d T(u,v))≤O(log n)d(u,v)。在RMOP算法与FRT算法具有相同的π时,RMOP算法能保证点u落入特定分割子集B(πJr(u),r)的概率最大。
A new algorithm RMOP was obtained which is called random minimum order partition by improving FRT algorithm. In view of choosing a random permutation 7r for all points of the given metric space G, randomly selecting point u ∈ V, then the order Jr(u)=inf{j∈N:d(πj,u)≤r,πj,u∈V} was derived. Therefore, a hierarchically well separated tree (short for HST) was constructed by recursively partitioning G via some clusters B(πJr(u),r), which πJr(u)is the center and r is the radius of the cluster. Moreover, the expectation expression E(dT(u,v))≤0(logn)d(u,v) holds. When FRT algorithm and RMOP algorithm have the same random permutation π, the probabil- ity which ensures the point u lies in the region B(πJr(u),r) is maximum in the RMOP algorithm.
出处
《山东大学学报(理学版)》
CAS
CSCD
北大核心
2013年第9期51-55,共5页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目(11201075)
福建省自然科学基金资助项目(2010J01005)
关键词
HSTs
树度量
随机分割
概率近似算法
HSTs
tree metrics
random partition
probabilistic approximation algorithm