郵局選址問題（分治演算法）

前言

提示：在演算法的學習程序中我們會遇到各種各樣的演算法思想，其中最常見的就有分治演算法思想，而本文的問題郵局選址問題就是基于分治思想而去實作的一個日常問題

提示：以下是本文內容，我將對該問題進行詳細的描述

一、分治演算法是什么？

總體而言，分治演算法是將一個難以直接解決的規模較大的問題分解為若干個規模較小的子問題，并各個擊破，分而治之，

將求出的較小規模的問題解合并成一個較大規模的問題解，并自底向上地求出原問題的解，

二、分治演算法的基本思想

1.分治策略的基本思想

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坐標，最后通過得到的郵局坐標對每一居民點坐標進行求距離操作，所累加的結果就是郵局到所有居民點的最短距離之和，