wordpress用户自建,百度关键词seo年度费用,118论坛,100个详情页设计图邮局选址问题(分治算法)前言提示#xff1a;在算法的学习过程中我们会遇到各种各样的算法思想#xff0c;其中最常见的就有分治算法思想#xff0c;而本文的问题邮局选址问题就是基于分治思想而去实现的一个日常问题提示#xff1a;以下是本文内容#xff0c;我将对该问题…邮局选址问题(分治算法)前言提示在算法的学习过程中我们会遇到各种各样的算法思想其中最常见的就有分治算法思想而本文的问题邮局选址问题就是基于分治思想而去实现的一个日常问题提示以下是本文内容我将对该问题进行详细的描述一、分治算法是什么总体而言分治算法是将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题并各个击破分而治之。将求出的较小规模的问题解合并成一个较大规模的问题解并自底向上地求出原问题的解。二、分治算法的基本思想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 stubint N0;int x[]new int[500]; //存放测试样本中x轴的数据值int y[]new int[500]; int xweight[]new int[500];//存放测试样本中的权值int yweight[]new int[500]; for(int a1;a7;a) { try { System.out.println(测试样本a); FileReader filereadernew FileReader(input0a.txt); //采用拼接方式读取样本 BufferedReader bufnew BufferedReader(filereader); int j0; String readline; String[] arraynew String[200]; readlinebuf.readLine(); NInteger.parseInt(readline);//读取测试样本中的第一行居民点的个数 System.out.println(居民点个数为N); while((readlinebuf.readLine())!null) { arrayreadline.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(lowhigh) { return; } int firstlow; int lasthigh; int keya[first]; int Weightweight[first]; while(firstkey) { --last; } a[first]a[last]; weight[first]weight[last]; while(first sumxweight / 2){x1i;break;//求取x轴上的带权中位数 } } System.out.println(邮局的x坐标为x[x1]); QuickSort(y,yweight,0,N-1); int sumyWeight0; for(int b0;b sumyweight / 2){y1k;break;//求取y轴上的带权中位数 } } System.out.println(邮局的y坐标为y[y1]); System.out.println(邮局的坐标位置为x[x1],y[y1]); for(int q0;q}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112运行说明邮局选址问题通过对居民点的坐标位置已经居民数量权值来进行分析在输入数据中先输入该测试样例共有几个居民点再依次输入各个居民点的坐标位置以及居民的数量运行程序之后会返回输出结果邮局所在的坐标位置以及邮局到所有居民点的最短路径之和。运行结果总结算法设计思路该程序主要采用了分治的思想包含有快速排序的方法将所输入数据值中的x坐标按从小到大依次进行排序使得该x坐标相对应的权值也进行相应的排序。然后通过权值的总和一半来选择所对应的x坐标求出带权中位数并通过同样的方式求出数据y坐标最后通过得到的邮局坐标对每一居民点坐标进行求距离操作所累加的结果就是邮局到所有居民点的最短距离之和。文章来源: blog.csdn.net作者九墨、版权归原作者所有如需转载请联系作者。原文链接blog.csdn.net/Xiao_ni_tongxue/article/details/109255860