算法分析若干实例问题解析

1、最小长度电路板排列问题问题描述 小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是: 将n块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对 应于不同的电路板插入方案。设B=1，2，n 是n块电路板的集合。集合L= N1， N2， Nm是n块电路板的m个连接块。其中每个连接块Ni是B的一个子集，且Ni中的电路板用同一根导线连 接在一起。连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最 大长度达到最小。例：如图，设n=8, m=5，给定n块电路板及其m个连接块

2、：B=1, 2, 3, 4, 5, 6, 7, 8，N1=4, 5, 6，N2=2, 3，N3=1, 3，N4=3, 6，N5=7, 8;这8块电路板两个可能的排列如图所示：在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。例如在左图示的电路板排列中，连接块N4的第1 块电路板在插槽3 中， 它的最后1块电路板在插槽6中，因此N4的长度为3。同理N2的长度为2。图中连接块最大长度为3。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。输入数据：第一行有2 个正整数n和m。接下来的n 行中，每行有m个数。第k行的第

3、j个数为0 表示电路板k不在连接块j 中，1 表示电路板 k在连接块j中。输出数据为计算出的电路板排列最小长度与相应的排列方式。Sample Input8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1Sample Output45 4 3 1 6 2 8 7可用策略 电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。首先考虑分治的方法，因为不同连接块连接了不同的电路板，原问题很难分解成互不相关的子问题，所以不考虑分治法。其次考虑贪婪法，逐步满足每个连接块的局部最优解，很容易

4、想出并不能得到全局最优解。使用动态规划方法也没有办法解答这个问题。可用算法有回溯法和分支限界法。采用回溯法予以解答。算法设计 考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。Bij的值为1当且仅当电路板i在连接块Nj中。设lowi 表示第i块连接块中最左边的电路板的下标，highi表示第i快连接块中最右边的电路板的下标。回溯法搜索排列树的算法一般可以描述如下：void backtrack(int t) if (t n) output(x); else for (int i = t; i n; i+) swap(xt, xi); if (constraint

5、(t) & bound(t) backtrack(t + 1); swap(xt, xi); 在这个问题中，output(x)，即所有已经排列好，更新最优排列。当in时，电路板排列尚未完成。X1：i的是当前扩展结点所相应的部分排列，highi- lowi 表示相应的部分最大长度，在当前部分排列之后加入一块未排定的电路板，扩展当前部分排列产生当前扩展结点的一个儿子结点。对于这个儿子结点，计算新的最大长度。仅当lenB=B;23. this-n=n;24. this-m=m;25. this-t=1;26. minl=0x7fffffff;27. nowl=0;28. x=newintn+1;29

6、. bestx=newintn+1;30. for(inti=1;iBacktrack(t);37. 38. intminBoard:caNowl(intt)39. for(inti=1;i=m;+i)40. lowi=n+1;41. highi=0;42. 43. for(i=1;i=t;+i)44. 45. for(intj=1;ji)lowj=i;50. if(highji)highj=i;51. 52. 53. 54. 55. intmaxt=0;56. for(intj=1;jmaxt&lowjn)/若能够达到说明满足条件nowlminl68. 69. /更新最优解70. for(i

7、ntj=1;j=n;+j)71. 72. bestxj=xj;73. 74. minl=nowl;75. 76. else77. for(inti=t;i=n;+i)78. 79. /产生下一个排列80. swap(xt,xi);81. /记录原始nowl当前最大长度用于恢复82. intreNowl=nowl;83. /计算当前组合的最大长度84. nowl=caNowl(t);85. if(nowlnm;97. int*B=newint(m+1)*(n+1);98. for(inti=1;i=n;+i)99. 100. for(intj=1;jBi*(m+1)+j;103. 104. 10

8、5. minBoardminB(n,m,B);106. 107. outCase#Case:minB.getMinl()endl;108. for(i=1;i=n;+i)109. 110. outminB.getBestx()i;111. 112. outendl;113. 114. return0;115. 输入：8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1输出45 4 3 1 6 2 8 7算法分析 该问题用回溯法求解，搜索一棵树列树。最坏情况下有n!个节点，对于剪枝函数caNowl复

9、杂度为O(mn)。n为电路板数量,m为连接块数量。所以此问题的总复杂度为O(mn*n!) 。中位数一、 中位数1. 问题描述 给定一个由n个互不相同的数组成的集合S，及一个正整数，试设计一个O(n)时间算法找出S中最接近S的中位数的k个数。2. 设计思路1) 可用策略 对数组排序，然后取范围内的k个数。2) 选用策略1. 找中位数x；2. 计算S中各个数与该中位数x的差值：,组成新的非负数集合；3. 查找中k个小的数对应于集合S中的元素。3. 算法设计/描述1. 找中位数x；2. 计算S中各个数与该中位数x的差值：,组成新的非负数集合；3. 查找中第k小的数，记为；4. 查找中所有小于等于的数

10、；5. 根据第4步查找的结果找出在集合S中对应的数即为S中最接近S的中位数的k个数。 关于第三步,求数组中第k小的数,线性时间复杂度的具体算法描述如下:基于快排序思想，步骤如下：1. 随机选择一个支点2. 将比支点大的数，放到数组左边；将比支点小的数放到数组右边；将支点放到中间(属于左部分)3. 设左部分的长度为L, 当K L时，递归地在有部分中找第(K - L)大的数 当K = L时，返回左右两部分的分割点（即原来的支点），就是要求的第K 大的数4. 实例/执行结果输入：输出：5. 分析T(n)/S(n)1) 策略1 T(n)取决于所采用的排序算法，根据已知的效率比较高的排序算法如归并排序或

11、者堆排序，2) 策略2 第一步，；第二步，一遍扫描即可，；第三步，采用STL中的nth_element算法，该算法的平均；第四步，一遍扫描找出符合要求的数即可，因此。根据算法效率度量的加法规则，整个算法的。二、 带权中位数邮局选址问题1. 问题描述 对分别具有正的权重且的n个不同元素，带权中位数是满足如下条件的元素： 邮局选址问题（post-office location problem） 定义如下：已知n个点及与它们相联系的权重，要求希望确定一点p（p不一定是n个输入之一），使和式达到最小，其中，表示a与b之间的距离。试论证带权中位数是一维邮局问题的最优解。此时。2. 证明思路 设是带权中位

12、数，对于任意一点，设。要证明 f(p) 是最小值，则只需要证明对于任意地x，f(x)-f(p)0。3. 证明过程i. 当时1. 当：2. 当：3. 当 且 同理，当时，。 问题得以证明，故带权中位数为一维邮局选址位置的最优解。参考文档算法导论第九章：中位数和顺序统计学寻找数组中第k小元素：查找数组中第k个最小元素对快排的改动STL 源码分析-nth_element() 使用与源码分析STL源码解析 - nth_element：带权中位数：算法导论_中位数与带权中位数：单机和多机最优服务次序一单机最优服务次序1.问题描述 设有个顾客同时等待一项服务。顾客需要的服务时间为，。应如何安排个顾客的服务

13、次序才能使平均等待时间达到最小 ? 平均等待时间是个顾客等待服务时间的总和除以。2.问题分析 采用贪心算法，第一个被服务的顾客所需的等待时间为0，由于只有一个服务机，因此第二个顾客的等待时间取决于第一个顾客，令表示第个顾客的等待服务时间，表示当前队列长度为时候的总服务时间，即，。根据上公式有，因此若要第二个顾客的等待时间小，则第一个顾客的服务时间是最短的，那么我们首先将，按照升序进行排序，该顺序即为服务次序，由于在这个例子中贪心算法的局部最优即使它的全局最优，因此它的最优服务次序即的升序序列。其时间复杂度主要取决于排序算法的时间复杂度，我采用的是冒泡排序，时间复杂度为。3.问题求解1. N个顾

14、客，每个顾客服务时间为t i.2. 将所有顾客的服务时间存在数组data中3. 将data内所有数据从小到大进行排序4. 用数组sequence存储排序队列5. 采用贪心算法依次选取data中的元素放入sequence中6. 最终sequence的内容即为最优服务次序代码如下：读取文件类：ReadFileimport java.io.BufferedReader;import java.io.File;import java.io.FileReader;import org.omg.CORBA.DATA_CONVERSION;public class ReadFile private Stri

15、ng fileString;private int num;private int data;private int serviceNum;public ReadFile(String filepath)this.fileString=filepath;try File file=new File(fileString);FileReader fReader=new FileReader(file);BufferedReader bReader=new BufferedReader(fReader);serviceNum=Integer.valueOf(bReader.readLine();n

16、um=Integer.valueOf(bReader.readLine();String DataString=bReader.readLine();data=new intnum;String dataString2=new Stringnum;dataString2=DataString.split( );for(int i=0;inum;i+)datai=Integer.valueOf(dataString2i);fReader.close(); catch (Exception e) / TODO: handle exceptionSystem.out.println(e.toStri

17、ng();public int getNum()return this.num;public int getData()return this.data;public int getServiceNum()return this.serviceNum;public void showData()System.out.println(读入数据为：);System.out.println(服务机数量为：+this.serviceNum);System.out.println(任务数量为：+this.num);System.out.println(任务时间数据分别为：);for(int i=0;in

18、um;i+)System.out.print(datai+ );单机服务类：public class SingleService private int data;private int num;private int sequence;private double t;public SingleService(ReadFile rf)this.num=rf.getNum();data=new intnum;data=rf.getData();sequence=new intnum;sort();setSequence();countTime();public void sort()for(i

19、nt i=0;inum;i+)for(int j=0;jnum;j+)if(datai=dataj)int k=0;k=datai;datai=dataj;dataj=k;public void setSequence()for(int i=0;inum;i+)sequencei=datai;public int getSequence()return this.sequence;public void countTime()int totalTime=0;int time=new intnum;time0=0;totalTime +=time0;for(int i=1;inum;i+)for

20、(int j=0;ji;j+)timei+=sequencej;totalTime +=timei;t=Double.valueOf(totalTime)/Double.valueOf(num);public void show()System.out.println();System.out.print(单机最优次序为：);for(int i=0;i);System.out.println(sequencenum-1);System.out.println(平均等待时间为：+t);主函数代码：输入格式为：1.服务机数量2.顾客数量3.每一个顾客的服务时间结果为：二多机最优服务次序1.问题描述

21、设有个顾客同时等待服务，服务机数量为。顾客需要的服务时间为，。应如何安排个顾客的服务次序才能使平均等待时间达到最小 ? 平均等待时间是个顾客等待服务时间的总和除以。2.问题分析依旧采取贪心算法，首先还是将，按照升序进行排序，由于本例子中服务机数量为，因此前个顾客的等待时间均为0，第个顾客则选择当前服务时间最短的那一个服务机进行等待，依次排序，从而贪心得到最优的服务次序，因此在本例中贪心算法的局部最优也就是它的全局最优，因此得到的最优序列即为全局最优序列。其时间复杂度为：。3.问题求解1.N个顾客，每个顾客服务时间为t i.2. 将所有顾客的服务时间存在数组data中3.将data内所有数据从小

22、到大进行排序4.用数组ArrayList sequence存储m个服务排序队列5.采用贪心算法依次选取data中的元素放入当前最短的sequence中6.最终ArrayList sequence的内容即为最优服务次序读取文件的类和单机服务相同多机服务类：import java.util.ArrayList; public class MutiService private int num;private int serviceNum;private int data;private ArrayList sequence;private int timePerSequence;private d

23、ouble t;public MutiService(ReadFile rFile)this.num=rFile.getNum();serviceNum=rFile.getServiceNum();data=new intnum;data=rFile.getData();sequence=new ArrayListserviceNum;timePerSequence=new intserviceNum;for(int i=0;iserviceNum;i+)sequencei=new ArrayList();timePerSequencei=0;sort();setSequence();setA

24、verageTime();public void sort()for(int i=0;inum;i+)for(int j=0;jnum;j+)if(datai=dataj)int k=0;k=datai;datai=dataj;dataj=k;public void setSequence()for(int i=0;inum;i+)int index=getMinSequenceIndex();sequenceindex.add(datai);timePerSequenceindex+=datai;/System.out.println(第+i+个数：+最小序列为：+index +time:+

25、timePerSequenceindex);public int getMinSequenceIndex()int k=-1;int min=10000;for(int i=0;iserviceNum;i+)if(timePerSequencei=min)min=timePerSequencei;k=i;return k;public void setAverageTime()int totalTime=0;for(int i=0;iserviceNum;i+)int tmpTime=0;int time=new intsequencei.size();time0=0;tmpTime+=tim

26、e0;for(int j=1;jsequencei.size();j+)for(int k=0;kj;k+)timej +=sequencei.get(k);tmpTime +=timej;totalTime +=tmpTime;t=Double.valueOf(totalTime)/Double.valueOf(num);public void show()System.out.println();System.out.println(多机最优次序为：);for(int i=0;iserviceNum;i+)System.out.print(服务机+i+次序为:);for(int j=0;j

27、);System.out.print(sequencei.get(sequencei.size()-1);System.out.println();System.out.println(平均等待时间为：+t);主函数代码：MutiService service2=new MutiService(rFile);service2.show();输入格式为：1.服务机数量2.顾客数量3.每一个顾客的服务时间结果为：网格行走问题题目描述 给定一个m x n的矩形网格，设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干个网格点处设置了障碍，表示该网格点不可到达。试设

28、计一个算法，求出汽车从起点S出发到终点T的一条行驶路程最短的路线。 下图描述了一张4 x 4的道路网格，网格点(2, 2)处设置了一个障碍，汽车无法到达该点。图1 网格行走问题样例输入4 42 2 202 2 3 32 2 33 3 5 44 2 210 10 5 510 10 1012 2样例输出18(1, 1)-(2, 1)-(3, 1)-(3, 2)-(3, 3)-(3, 4)-(4, 4)解题思路 以每个网格点为结点，可达网格点的网格边为边建图，则可以建立无向有环图。所以就将题目转换成了无向有环图上的两点间最短路问题。而两点间最短路问题的复杂度不会低于单源最短路问题，所以就将题目转换为

29、无向有环图上的单源最短路问题。 无向有环图上的最短路问题的经典算法有：Dijkstra、Bellman-Ford、Floyd-Warshall。其中，Dijkstra和Bellman-Ford可以求解单元最短路，Bellman-Ford可以求解带负边的最短路。Floyd-Warshall可以求解任意两点最短路。 对于无负边的情况，Dijkstra算法的效率最高，若使用优先队列来优化，时间复杂度可以降为O(|E|log|V|)。故选择Dijkstra算法来求解。 具体来说，Dijkstra算法基于贪心思想，在求解过程中利用记忆化搜索（动规）来辅助求解。考虑网格点(i, j)的情况，假设从起点到(

30、i, j)的最短路是d(i, j)，那么可以由四个方向来到d(i, j)，对应着4条入边。所以有递推关系d(i, j) = mind(k, l)|e(k,l), (i,j)E。 令S为已知最短路的结点的集合，则初始情况下S=S。在Dijkstra算法执行时，考虑所有从S连出的边e(u,v)，取出d(v)最小的v。对于v，使用前述递推式和结点v更新其余结点。也就是在这一步时，认为d(v)就是s到v的最短路。贪心证明：因为边权为正，所以当d(v)最小时不可能通过别的点到达v使得d(v)更小。 当算法结束时，即可以求得所有点的最短路。最短路径统计 新开一个数组pa存储每个结点的前驱结点，在递推式du

31、+e.cost dv为真时更新pav = u。 也可以在算出每一个结点的最短路后，利用du + e.cost = dv来找到结点v的前驱结点u。这里采用第一种方法。伪代码Q.add(new HeapNode(0, s); /初始化，将起点加入优先队列while(!Q.isEmpty)u = Q.poll().u;if(doneu) continue;doneu = true;for(u的所有出边e(u, v)if(du+e.cost dv)dv = du + e.cost;pav = u;Q.add(new HeapNode(dv, v);算法实现import java.io.File;imp

32、ort java.io.FileNotFoundException;import java.io.IOException;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.Queue;import java.util.Scanner;class Main class Edge int from, to, cost;public Edge(int from, int to, int cost)this.fr

33、om = from; this.to = to; this.cost = cost;class HeapNode implements Comparableint d, u;public HeapNode(int d, int u)this.d = d; this.u = u;Overridepublic int compareTo(HeapNode o) return d-o.d;static int INF = Integer.MAX_VALUE;static int maxn = 10000;int n,m;int d = new intmaxn, pa = new intmaxn;bo

34、olean done = new booleanmaxn, obstacle = new booleanmaxn;List edges;ListList G;void dijkstra()Arrays.fill(d,0,n*m,INF);Arrays.fill(done,0,n*m,false);Arrays.fill(pa, 0, n*m, -1);d0 = 0;Queue Q = new PriorityQueue();Q.add(new HeapNode(0, 0);while(!Q.isEmpty()HeapNode x = Q.poll();int u = x.u;if(doneu)

35、 continue;doneu = true;for(int i=0; iG.get(u).size(); i+)Edge e = edges.get(G.get(u).get(i);if(obstaclee.to) continue;if(de.from + e.cost );System.out.printf(%d, %d), u/m + 1, u%m + 1);void solve()dijkstra();System.out.println(d(n-1)*m + (m-1);first = true;print_path(n-1)*m + (m-1);void begin() thro

36、ws IOException n = in.nextInt(); m = in.nextInt();int cost;G = new ArrayListList();for(int i=0; in*m; i+)G.add(new ArrayList();edges = new ArrayList();for(int i=0; im-1; i+)cost = in.nextInt();addEdge(i, i+1, cost);for(int i=0; in-1; i+)for(int j=0; jm; j+)cost = in.nextInt();addEdge(i*m+j, (i+1)*m+

37、j, cost);for(int j=0; j 0)u = in.nextInt(); v = in.nextInt();obstacle(u-1)*m+(v-1) = true;solve();public void close() throws IOException in.close();Scanner in;public Main() throws FileNotFoundException in = new Scanner(new File(in.txt);public static void main(String args) throws IOException Main SSS

38、P = new Main();SSSP.begin();SSSP.close();荷兰国旗问题1.原问题描述将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗，是因为可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。 要求算法的时间复杂度为O(n)。2.设计思路可以将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在0,1的区域里，由于三色小球之间数量的比不同（此处假设

39、1:2:2），可能前部为0,0.2)，中部为0.2,0.6)，后部为0.6,1。3.算法设计 首位置IB=1，尾位置IE=LENGTH。LOOP 5 累计量I=1，LENGTH若I=IE 退出LOOP 5若NN(I)=0，IB=IB+1，I=I+1若IBI，NN(I)和NN(IB)互换；若NN(I)=1，I=I+1;若NN(I)=2，I=I+1，IE=IE-1若NN(IE)=1，NN(I)和NN(IE)互换；若NN(IE)=0，IB=IB+1若IB=I，NN(I)和NN(IE)互换；若IBI，NT=NN(IB)，NN(IB)=NN(IE)，NN(IE)=NN(I)，NN(I)=NT；若NN(I

40、E)=2，则进行IE=IE-1直到NN(IE) 2，若NN(IE)=1，NN(I)和NN(IE)互换；若NN(IE)=0，IB=IB+1若IB=I，NN(I)和NN(IE)互换；若IBI，NT=NN(IB)，NN(IB)=NN(IE)，NN(IE)=NN(I)，NN(I)=NT；结束LOOP 54.实例/执行结果输入数据NN（10,2）：编号：1,2,3,4,5,6,7,8,9,10内容：1,2,0,2,1,2,0,0,2,1计算结果 编号：3 8 7 10 5 1 6 4 9 2内容：0 0 0 1 1 1 2 2 2 25.讨论1)没有开辟格外的数组存放元素，空间复杂度为n； 2)每个元素均扫描了一次；每个元素至多进行了一次交换值，时间复杂度为n。 3)对于只有1色或2色能否正常运行？ 能！ 4)对于四种及以上颜色呢？ 不行，需要三个标度。最小机器重量设计1. 问题描述设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，ci