我们先来看题目描述服务中心的最佳位置一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标并希望能够以此为依据为新的服务中心选址使服务中心 到所有客户的欧几里得距离的总和最小。示例 1这道题是运筹学里面中心选址问题的简化版本。注意读题可以发现题目中输入的“客户”坐标是整数但要求输出的服务中心坐标可以是小数并且说与真实值误差在 10e-5 之内的答案将被视作正确答案。为什么要特别添加这个说明呢因为这是一道竞赛题要求参赛者在一个半小时内给出答案所以该说明是为了降低问题的难度。因为解的类型是小数所以解空间的边界是连续的可以进一步猜测该问题是凸优化问题我们可以尝试使用爬山算法来寻找最优解。爬山算法的思想非常简单首先在地图上面找一个位置作为初始解有了初始解以后按照一定的方向迭代搜索更优的解。 在选取初始解时可以考虑所有客户坐标的几何中心也可以随机选择一个点作为初始位置。在迭代时算法只搜索当前解附近的位置如果发现附近有一个更好的解那么就将当前位置更新过去。算法的伪代码如下# 爬山算法伪代码 cur_sol init() while not stop: for new_sol in neighbor(cur_sol): if obj(new_sol) best_obj: cur_sol new_sol break return best_obj这里面的 neighbor() 函数用来产生当前解附近的解因为解空间是连续的所以当前解附近必定有离最优解更近的解我们只需要找到个这个解并继续做迭代即可。那么迭代的停止条件是什么呢假如地图中只存在一个最优解那么迭代的结果必然是让当前解无限的接近最优解所以只需要设置一个阈值并判断当前迭代步长是否小于该阈值即可这里可以选择一个比题目中要求的误差更小的值作为阈值。