贪心算法求解k-median问题  

Greedy Algorithms for K-median Problems

作　　者：肖进杰[1] 范辉[1] 郭玉刚[1] 程大鹏[1] 

机构地区：[1]山东工商学院信息与电子工程学院,山东烟台264005

出　　处：《计算机工程与应用》2006年第3期57-58,68,共3页Computer Engineering and Applications

摘　　要：文章讨论了用贪心算法解k-m edian问题以及其试验结果。首先提出了一个解k-m edian问题的简单贪心算法,然后对求解质量和求解的近似性能比进行了探讨。主要讨论了公制空间和非公制空间初始解的产生,用贪心算法解k-m edian问题以及全局最优解的计算。试验结果表明:贪心算法解公制空间的k-m edian问题效果要好于解非公制空间的k-m edian问题;用贪心算法解公制空间和非公制空间k-m edian问题都能得到较好的结果。This paper discusses greedy algorithms for k-median problems and the results of testing.This paper first presents a simple greedy algorithm for k-median problems,then discusses the quality of solutions and approximation ration through computer verification.This paper mainly discusses generation methods of the initial solution in metric space and no-metric space,greedy algorithms for k-median problems and the computation of global optimization.The testing data shows：the result of greedy algorithms for metric k-median problems is better than that of no-metric k-median problems and we can get a better result using greedy algorithms for metric and no-metric k-median problems.

关 键 词：k-median 贪心算法 公制空间 非公制空间 初始解 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]