计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
9期
234-236,253
,共4页
最小闭包球%核心集%积极集策略%大规模数据集
最小閉包毬%覈心集%積極集策略%大規模數據集
최소폐포구%핵심집%적겁집책략%대규모수거집
Minimum enclosing ball%Core set%Active set strategy%Large-scale date sets
首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法.对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε).然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点.将该策略结合到提出的算法中,得到一个基于积极集策略的算法.最后,实验结果表明基于积极集策略的算法能够快速、有效地求解m》n的大规模数据集的近似最小闭包球.
首先,基于每次迭代計算距離噹前毬心最遠的兩箇點,提齣一種求解n維空間中m箇點的最小閉包毬問題的(1+ε)-近似算法.對于ε∈(0,1),建立瞭該算法的覈心集大小和計算複雜度,分彆為O(1/ε)和O(mn/ε).然後,給齣一種積極集策略,每次迭代計算距離噹前毬心最遠的N箇點.將該策略結閤到提齣的算法中,得到一箇基于積極集策略的算法.最後,實驗結果錶明基于積極集策略的算法能夠快速、有效地求解m》n的大規模數據集的近似最小閉包毬.
수선,기우매차질대계산거리당전구심최원적량개점,제출일충구해n유공간중m개점적최소폐포구문제적(1+ε)-근사산법.대우ε∈(0,1),건립료해산법적핵심집대소화계산복잡도,분별위O(1/ε)화O(mn/ε).연후,급출일충적겁집책략,매차질대계산거리당전구심최원적N개점.장해책략결합도제출적산법중,득도일개기우적겁집책략적산법.최후,실험결과표명기우적겁집책략적산법능구쾌속、유효지구해m》n적대규모수거집적근사최소폐포구.
