p-cluster:基于聚类的平面p-中心定位算法  

p-cluster:a novel p-center location algorithm based on clustering

作　　者：刘显宾[1] 唐常杰[1] 陈瑜[1] 张悦[1] 李川[1] 代术成[1] 

机构地区：[1]四川大学计算机学院,成都610064

出　　处：《四川大学学报（自然科学版）》2009年第1期80-84,共5页Journal of Sichuan University(Natural Science Edition)

基　　金：国家自然科学基金(60473071);四川大学青年基金(0636);四川大学计算机学院基金

摘　　要：客户-设备的p中心定位问题旨在使每个客户访问与其最近的开放设备的最大距离最小,是典型的NP难题。采用聚类分析来解决离散p-中心问题,主要工作包括:(1)分析了按需求点分布类型来分类p-中心问题;(2)提出了基于聚类的p-中心定位算法p-cluster;(3)提出了用混沌搜索机制来求解带权值的一中心问题的算法CSOC(Chaos Search One Center)。在合成数据和真实数据上的实验表明,使用p-cluster算法可以有效地解决p-中心问题,从对比实验可以看出p-cluster算法明显优于分支限界法。The p-center problem of locating clients-facilities is to optimize the maximal distance between each client and the nearest openning facility as small as possible. It is proved to be an NP hard problem. To address the problem of discrete p-center with weight , this paper proposes a cluster analyze scheme named p-cluster,. The contributions include： （1） analyzing classify p-center problems by distributing types of requirement points. （2） proposing p-cluster algorithm based on Clustering. （3） proposing CSOC （Chaos Search One Center）, a algorithm of chaotic searching mechanism to solve one-center problem with weight, our experiments on synthesis data and real data show that the p-cluster on p-center location problem offers a better performance improvement.

关 键 词：p-中心 混沌搜索 聚类 定位机制 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]