贪心算法求解k-median问题

Greedy Algorithms for K-median Problems

文章讨论了用贪心算法解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.