度量空间的概率近似算法

J4 ›› 2013, Vol. 48 ›› Issue (09): 51-55.

度量空间的概率近似算法

蔡裕华,魏凤英*

福州大学数学与计算机科学学院, 福建福州 350108

收稿日期:2013-01-08 出版日期:2013-09-20 发布日期:2013-09-25
通讯作者: 魏凤英(1976- ),女,博士,副教授,研究方向为随机泛函微分方程及其应用. Email:weifengying@fzu.edu.cn
作者简介:蔡裕华(1987- ),男,硕士研究生,研究方向为近似算法,随机微分方程及其应用. Email:caiyuhua87@163.com
基金资助:
国家自然科学基金资助项目(11201075);福建省自然科学基金资助项目(2010J01005)

Probabilistic approximation algorithm of metric spaces

CAI Yuhua, WEI Fengying*

College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, Fujian, China

Received:2013-01-08 Online:2013-09-20 Published:2013-09-25

摘要/Abstract

摘要：

通过改进FRT算法,得到随机最小序分割算法(random minimum order partition, RMOP)。在度量空间G中,对点列V进行随机排序(设序列为π),随机选取点u∈V后,获得下标Jr(u)=inf｛j∈N:d(πj,u)≤r,πj,u∈V｝,再以点πJr(u)为球心r为半径,对度量空间G进行递归分割,进而形成一棵分层良分割树(hierarchically well separated tree, HST);同时得到E(dT(u,v))≤O(logn)d(u,v)。在RMOP算法与FRT算法具有相同的π时,RMOP算法能保证点u落入特定分割子集B(πJr(u),r)的概率最大。

关键词: HSTs;树度量;随机分割;概率近似算法

Abstract:

A new algorithm RMOP was obtained which is called random minimum order partition by improving FRT algorithm. In view of choosing a random permutation π 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))≤O(logn)d(u,v) holds. When FRT algorithm and RMOP algorithm have the same random permutation π, the probability which ensures the point u lies in the region B(πJr(u),r) is maximum in the RMOP algorithm.

Key words: HSTs; tree metrics; random partition; probabilistic approximation algorithm

蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.

CAI Yu-hua, WEI Feng-ying*. Probabilistic approximation algorithm of metric spaces[J]. J4, 2013, 48(09): 51-55.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed