k-median问题的局部搜索近似算法

摘要

在生产活动和城市规划中,经常会遇到设备定位的问题.即开设某些设备,每个设备为距离它最近的客户提供服务,使得整个成本最小.对成本的度量,最直接的方法就是计算客户到为它提供服务的设备之间的距离之和,这称为服务成本.此外开设设备所需的成本称为设备成本,k-median问题即是其中的一种.在k-median问题中,最多允许开设k个设备,全部服务成本为每个客户到与之最近的设备之间的距离之和,目的是使这个成本最小.局部搜索技术是算法设计中一个重要的技术。它首先找出问题的一个随机解，然后对当前的解施与给定的变换，使改进的解成为新的当前解。重复执行类似变换，直到再无变换能改善当前解为止。本文就通过局部搜索技术得出卜me山an问题的一个近似解。