k-center问题的算法研究综述

摘要

k-center问题是设施选址的基础问题，同样是NP难问题，在分配、紧急服务等领域也有着实际的应用。随着问题规模的扩大，原有的算法已不再适用，需要进一步优化或者改进。为了找到求解该问题的高效算法，对现有算法进行研究。对各类求解k-center问题的算法进行梳理，将求解算法划分为精确算法、启发式算法、元启发式算法、近似算法等，从算法原理、改进思路、性能和精度等方面进行对比综述。精确算法在求解小规模k-center问题时可在多项式时间内得到最优解，但是算法效率低，不适用于大规模问题；启发式算法可以在多项式时间内给出相对最优解，但是没有理论保证，无法衡量与最优解的关系；元启发式算法可对目前存在的智能优化算法进行改进，给出相对最优解，但是解的质量无法保证；利用近似算法得到的解具有近似比保证，有较大的理论研究价值，但是实用价值较弱。目前求解k-center问题的元启发式算法已取得一定的研究成果，但是在求解时间、求解规模、算法效率等方面仍待突破，这将是未来k-center问题的研究重点。

关键词

k-center问题 / 精确算法 / 近似算法 / 蜂群优化 / 遗传算法