问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求：为建邮局选址，使得n个居民点到邮局之距离的总和最小。
提示：带权中位数（分治算法）
题目分析：
（1）n个居民点散乱在街区中，是一个二维面，因此使用坐标来刻画每一个居民点；
这里的权值代表的是地点的重要程度或者是价值，比如医院、商场这样人流量大且重要的地点权值要高一些；
（2）不带权的中位数：就是一组有序数的中间值，如果为奇数为中间一个数，如果为偶数为中间两个数的平均值；
（3）带权中位数：就是给定的N个数都有一个权值，或者说相当于个数，然后求解
如何计算带权中位数：现将这些数按值排序，sum = (第i个数的权重 * 第i个数本身的值)
如果sum(k-1)= (第i个数的权重 * 第i个数本身的值) < sum/2
且 sum(k-1)= (第i个数的权重 * 第i个数本身的值) >= sum/2 ,则第k个元素为这组数的带权中位数
理解计算：之前已经说过权值其实可以看做是个数，也就是说如果X1=5，它的权值为3，X2=1，它的权值为5，先排序应该是X2,X1，然后再按公式计算。其实也就是把权值体现在个数上求中位数：1,1,1,1,1,5,5,5求这组数的中位数，上面的求前k-1个带权之和不就是展开后的求中位数么
（4）证明带权中位数是一维邮局位置问题的最佳解决方案
由此可以推出二维，只需转化成两个一维分别求取带权中位数即可，那么求出来的位置就是邮局所在的位置。
求解过程：
（1）从文件读取数据（数据包括x,y坐标以及两个坐标对应的权值）
（2）对x轴坐标排序，求取x方向的带权中位数；对y轴坐标排序，求取y方向的带权中位数（求取方法见上）
（3）两个带权中位数所组成的坐标就是邮局选址的位置
代码如下：
（1）居民点的实体类（本来想考虑实际意义进行封装，但是在后面的排序中发现考虑操作可能有些重复，也可以定义两个一维数组操作更方便）
public class Position {//位置实体类
private double x;//位置的横坐标
private double y;//位置的纵坐标
private double xWeight;//横坐标的权值
private double yWeight;//纵坐标的权值
//构造方法
public Position(){
}
//构造方法
public Position(double x, double xWeight, double y, double yWeight) {
this.x = x;
this.y = y;
this.xWeight = xWeight;
this.yWeight = yWeight;
}
//get/set方法
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public double getxWeight() {
return xWeight;
}
public void setxWeight(double xWeight) {
this.xWeight = xWeight;
}
public double getyWeight() {
return yWeight;
}
public void setyWeight(double yWeight) {
this.yWeight = yWeight;
}
@Override
public String toString() {
return "Position{" +
"x=" + x +
", y=" + y +
", xWeight=" + xWeight +
", yWeight=" + yWeight +
'}';
}
}
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test {
public static void main(String[] args) throws IOException {
System.out.println("请输入要测试的数据序号：");
Scanner input = new Scanner(System.in);
int num = input.nextInt();
//从文件读取数据并对其进行封装
List<Position> list = readData(".\\input_assign01_0"+num+".dat");
System.out.println(list.toString());
//调用方法求取邮局坐标
Position pos = postOffice(list);
System.out.println("x:"+pos.getX()+"\ny:"+pos.getY());
}
/**
* 读取数据
* @param path:文件路径
* @return 封装好的居民点坐标数组
*/
public static List<Position> readData(String path) throws IOException {
List<Position> list = new ArrayList<>();
//打开输入流
InputStream is = new FileInputStream(path);
BufferedReader reader = new BufferedReader(new InputStreamReader(is));
String buffer = null;
while ((buffer = reader.readLine())!=null){//按行读取
String[] str = buffer.split("，");
Position pos = new Position(Double.parseDouble(str[0]),Double.parseDouble(str[1]),Double.parseDouble(str[2]),Double.parseDouble(str[3]));
list.add(pos);
}
//关闭流
is.close();
reader.close();
return list;
}
/**
* 对居民点坐标集合按照x或y排序
* @param list 未排序的居民点坐标集合
* @param low 要排序的集合第一个位置
* @param height 要排序的集合的最后一个位置
* @param choose 判断是要根据x排序，还是根据y排序
* @return 排好序的居民点坐标集合
*/
public static List qSort(List<Position> list, int low, int height, String choose){
if(low>=height){//判断位置的合法性
return list;
}
Position temp = list.get(low);//先选择一个位置
Position change = null;
int i = low;//i指针从低到高筛选
int j = height;//j指针从高到低筛选
//当对x轴的权值进行排序时
if(choose.equals("x")){
while(i!=j){
while(list.get(j).getX()>=temp.getX() && i<j){j--;}//j指向的数值大于选择数值，j指针前移
while (list.get(i).getX()<=temp.getX() && i<j){i++;}//i指向的数值小于选择数值，i指针后移
if(i<j) {//当遇到j指向的数据小于i指向的数据时，两个数据交换位置，把小的放前面，大的放后面
change = list.get(i);
list.set(i, list.get(j));
list.set(j, change);
}
}
}
//当对y轴的权值进行排序时，与x轴同理
if(choose.equals("y")){
while(i!=j){
while(list.get(j).getY()>=temp.getY() && i<j){j--;}
while (list.get(i).getY()<=temp.getY() && i<j){i++;}
if(i<j){
change = list.get(i);
list.set(i,list.get(j));
list.set(j,change);
}
}
}
//当把小的数据放到前面，大的数据放到后面之后，i和j所指向的同一个位置就是所选择数据应该所在的位置
change = list.get(i);
list.set(i,temp);
list.set(low,change);
//找到第一个选择数据应该放的位置之后，从此处再把数据分为前后两端，分别对这两段数据按照同样的方法递归排序
qSort(list,low, i - 1,choose);
qSort(list,i + 1, height,choose);
return list;
}
/**
* 通过对x轴，y轴坐标排序，分别计算出出带权中位数，其对应的x,y即为邮局的坐标
* @param list：传入的居民点的位置信息
* @return
*/
public static Position postOffice(List<Position> list){
Position postOffice = new Position();
double xsum = 0;//用来记录x轴的权重之和
double ysum = 0;//用来记录y轴的权重之和
double sum = 0;
List<Position> xlist = qSort(list,0,list.size()-1,"x");//对x坐标进行由小到大排序
// System.out.println("x:"+xlist.toString());
//分别计算x轴和y轴的权重之和
for(int i=0;i<list.size();i++){
xsum+=list.get(i).getxWeight();
ysum+=list.get(i).getyWeight();
}
//求x轴的带权中位数作为邮局的横坐标
for(int j=0;j<xlist.size();j++){
sum+=xlist.get(j).getxWeight();
if(sum > xsum/2){//累加的权值之和刚好大于权值总和的一半时，所对应的x值为带权中位数
postOffice.setX(xlist.get(j).getX());
break;
}
}
//对y坐标进行由小到大排序
List<Position> ylist = qSort(list,0,list.size()-1,"y");
// System.out.println("y:"+ylist.toString());
sum = 0;
//求y轴的带权中位数作为邮局的纵坐标
for(int k=0;k<ylist.size();k++){
sum+=ylist.get(k).getyWeight();
if(sum > ysum/2){
postOffice.setY(ylist.get(k).getY());
break;
}
}
return postOffice;
}
}
输入数据存储格式：
分别代表x坐标，x的权值，y坐标，y权值。每一行代表一个居民点
版权声明：本文为qq_42525835原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。