设施选址问题是一类被广泛研究和应用的优化问题,在互联网、分布式计算、数据挖掘和运筹规划等领域有广泛应用,所以对设施选址问题各种形式的研究有着重要的实际意义。设施选址问题的一般形式是从一个对象集合中选择若干对象作为设施来服务其它对象,优化的目标是服务费用最小,比如从一个局域网中选择若干主机作为代理服务器使得其它主机通过代理服务器访问外部网络的时间尽量短。围绕设施选择问题的一些形式,本文开展了以下研究工作:提出并研究了无向树全覆盖问题及其应用。该问题是已有的无向树上1覆盖问题的一个限定形式,也是已有的无向树1中心问题的一个推广形式。设计了一个时间复杂度为O ( n log n )的简洁算法来解决该问题。这一算法可以用来解决树形网络的代理服务器和网页缓存服务器的选择问题。改进了直线上p覆盖问题的已有算法。该问题是设施选址问题中较早被研究的形式之一。改进算法利用高效的数据结构和优化技术将已有动态规划算法的时间复杂度改进为O ( np log n ),空间复杂度改进为O ( n log n ),而原算法的时间复杂度和空间复杂度均为O ( n 2)。提出并研究了无向树上K节点子树核心问题及其应用。该问题是已有的无向树p中心问题的一个限定形式,可以应用于树形网络上的分布式数据库数据副本最优安置问题。设计了两个不同的动态规划算法来解决这一问题,一个具有编程实现简单实用性强的特点,另一个具有时间复杂度低时间效率高的特点,两个算法可分别适用于不同的应用环境。研究了无向树1中心问题的动态形式。该问题需要在树节点权值动态改变的情况下多次求解无向树的1中心。提出了利用简单的动态树数据结构在对数时间内维护动态无向树的1中心的算法,从而解决了已有算法不能处理树节点权值变小的情况这一问题。研究了无向树上的p中心问题。在已有无向树上无容量限制的设施选址问题算法的基础上提出了一个时间复杂度较低的实用算法。这一算法并不能求解所有的输入实例,即一些特殊的输入实例会导致该算法失败,但是验证实验表明该算法能够求解绝大部分输入实例。