学习使用分治算法来解决邮局选址问题（Java实现）

邮局选址问题（分治算法）

大致目录

• 邮局选址问题（分治算法）
• 前言
• 一、分治算法是什么？
• 二、分治算法的基本思想
• 三、邮局选址问题
• 总结算法设计思路

---

前言

提示：在算法的学习过程中我们会遇到各种各样的算法思想，其中最常见的就有分治算法思想，而本文的问题邮局选址问题就是基于分治思想而去实现的一个日常问题

---

提示：以下是本文内容，我将对该问题进行详细的描述

一、分治算法是什么？

总体而言，分治算法是将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。

将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的解。

二、分治算法的基本思想

1.分治策略的基本思想

1.将原始问题划分或者归结为规模较小的子问题 2.递归或迭代求解每个子问题 3.将子问题的解综合得到原问题的解

2.注意：

1.子问题与原始问题性质完全一样
2.子问题之间可彼此独立地求解
3.递归停止时子问题可直接求解

三、邮局选址问题

问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求：为建邮局选址，使得n个居民点到邮局之距离的总和最小。
提示：
带权中位数

代码实现 :

package Site_selection;
import java.io.BufferedReader;
import java.io.FileReader;

public class Site_selection {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N=0;
		int x[]=new int[500];    //存放测试样本中x轴的数据值
		int y[]=new int[500]; 
		int xweight[]=new int[500];//存放测试样本中的权值
		int yweight[]=new int[500];
        for(int a=1;a<7;a++) {
        try {
    	  System.out.println("测试样本"+a);
    	  FileReader filereader=new FileReader("input0"+a+".txt"); //采用拼接方式读取样本
    	  BufferedReader buf=new BufferedReader(filereader);
    	  int j=0;
    	  String readline="";
    	  String[] array=new String[200];
    	  readline=buf.readLine();
    	  N=Integer.parseInt(readline);//读取测试样本中的第一行居民点的个数
    	  System.out.println("居民点个数为："+N);
    	  while((readline=buf.readLine())!=null) {
    		  array=readline.split(",");  	//按照,分隔字符串来放入相应的数组之中
    	      x[j]=Integer.parseInt(array[0]);
    		  y[j]=Integer.parseInt(array[1]);
    		  xweight[j]=Integer.parseInt(array[2]);
    		  yweight[j]=Integer.parseInt(array[2]);
    		  j++;  		 
    	  } 
      }
      catch(Exception e) {
    	 e.printStackTrace();
      }
      MinSumDistance(x,y,xweight,yweight,N);
     }
	}
	/*
	 * 1.快速排序
	 *   通过该排序方式中的分治思想，来对测试样本中所有的数据值进行相对应的排序
	 * 
	*/
    public static void QuickSort(int a[],int weight[],int low,int high){
    	if(low>high) {
    		return;
    	}
    	int first=low;
    	int last=high;
    	int key=a[first];
    	int Weight=weight[first];
    	while(first<last)
    	{
    		while(first<last&&a[last]>key) {
    			--last;
    		}
    		a[first]=a[last];
    		weight[first]=weight[last];
    		while(first<last&&a[first]<key) {
    			++first;
    		}
    		a[last]=a[first];
    		weight[last]=weight[first];
    	}
    	a[last]=key;
    	weight[last]=Weight;
    	QuickSort(a,weight,low,first-1);
        QuickSort(a,weight,first+1,high);    	 	
    }
    /*
     * 2.邮局到居民点的最短路径之和
     *   通过对x轴与y轴的带权中位数的求解来得到相应的邮局坐标，再通过坐标位置与各个居民点的坐标位置相运算累加之和即为最短距离
     * 
     * 
     */
    public static void MinSumDistance(int x[],int y[],int xweight[],int yweight[],int N) {
    	int x1=0;
    	int y1=0;
    	int distance = 0;
    	QuickSort(x,xweight,0,N-1);
    	int sumxweight=0;
    	int sumyweight=0;
    	for(int b=0;b<xweight.length;b++) {
    		sumxweight+=xweight[b];
    	}
    	System.out.println("x坐标上的总权值为："+sumxweight);
    	for(int i = 0; i < xweight.length; i++){
			sumxweight += xweight[i];
			if(sumxweight >= sumxweight / 2){x1=i;break;//求取x轴上的带权中位数
				 }
			}
    	System.out.println("邮局的x坐标为："+x[x1]);
    	QuickSort(y,yweight,0,N-1);
    	int sumyWeight=0;
    	for(int b=0;b<yweight.length;b++) {
    		sumyWeight+=yweight[b];
    	}
    	System.out.println("y坐标上的总权值为："+sumyWeight);
    	for(int k = 0; k < yweight.length; k++){
			sumyweight += yweight[k];
			if(sumyweight >= sumyweight / 2){y1=k;break;//求取y轴上的带权中位数
				 }
			}
    	System.out.println("邮局的y坐标为："+y[y1]);
    	System.out.println("邮局的坐标位置为"+x[x1]+","+y[y1]);
    	for(int q=0;q<N;q++) {
    		distance+=Math.abs((x[q]-x[x1]))+Math.abs((y[q]-y[y1]));
    	}
    	System.out.println("所有居民点到邮局的最短距离为："+distance);
    	System.out.println("------------------");
    }
}

运行说明：
邮局选址问题通过对居民点的坐标位置已经居民数量权值来进行分析，在输入数据中，先输入该测试样例共有几个居民点，再依次输入各个居民点的坐标位置以及居民的数量，运行程序之后会返回输出结果邮局所在的坐标位置，以及邮局到所有居民点的最短路径之和。

运行结果：

总结算法设计思路

该程序主要采用了分治的思想，包含有快速排序的方法，将所输入数据值中的x坐标按从小到大依次进行排序，使得该x坐标相对应的权值也进行相应的排序。然后通过权值的总和一半来选择所对应的x坐标，求出带权中位数，并通过同样的方式求出数据y坐标，最后通过得到的邮局坐标对每一居民点坐标进行求距离操作，所累加的结果就是邮局到所有居民点的最短距离之和。

本文地址：https://blog.csdn.net/Xiao_ni_tongxue/article/details/109255860