| 贪心算法求解k-median问题 |
| |
| 引用本文： | 肖进杰,范辉,郭玉刚,程大鹏. 贪心算法求解k-median问题[J]. 计算机工程与应用, 2006, 42(3): 57-58,68 |
| |
| 作者姓名： | 肖进杰 范辉 郭玉刚 程大鹏 |
| |
| 作者单位： | 山东工商学院信息与电子工程学院,山东,烟台,264005 |
| |
| 摘 要： | 文章讨论了用贪心算法解k-m edian问题以及其试验结果。首先提出了一个解k-m edian问题的简单贪心算法,然后对求解质量和求解的近似性能比进行了探讨。主要讨论了公制空间和非公制空间初始解的产生,用贪心算法解k-m edian问题以及全局最优解的计算。试验结果表明:贪心算法解公制空间的k-m edian问题效果要好于解非公制空间的k-m edian问题;用贪心算法解公制空间和非公制空间k-m edian问题都能得到较好的结果。
|
| 关 键 词： | k-median 贪心算法 公制空间 |
| 文章编号： | 1002-8331-（2006）03-0057-02 |
| 收稿时间： | 2005-04-01 |
| 修稿时间： | 2005-04-01 |
Greedy Algorithms for K-median Problems |
| |
| Xiao Jinjie,Fan Hui,Guo Yugang,Cheng Dapeng. Greedy Algorithms for K-median Problems[J]. Computer Engineering and Applications, 2006, 42(3): 57-58,68 |
| |
| Authors: | Xiao Jinjie Fan Hui Guo Yugang Cheng Dapeng |
| |
| Affiliation: | School of Information and Electronic Engineering,Shandong Institute of Business and Technology, Yantai, Shandong 264005 |
| |
| Abstract: | 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. |
| |
| Keywords: | k-median |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
