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

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

2、。例：如图，设n=8, m=5，给定n块电路板及其m个连接块：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个连接块中最

3、大长度达到最小。输入数据：第一行有2 个正整数n和m。接下来的n 行中，每行有m个数。第k行的第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)  

5、; output(x); else  for (int i = t; i < n; i+)    swap(xt, xi);   if (constraint(t) && bound(t)    backtrack(t + 1);   swap(xt, xi);  在这个问题中，output(x)，即所有已经排列好，更新最优排列。当i<n时，电路板排列尚未完成。X1：i的是当前扩展结点所相应的部分排列，highi- lowi 表示相应的部分最大长度，在当前部

6、分排列之后加入一块未排定的电路板，扩展当前部分排列产生当前扩展结点的一个儿子结点。对于这个儿子结点，计算新的最大长度。仅当len<bestd时候，算法搜索相应的子树，否则该子树被剪去。按上述回溯搜索策略设计的算法如下： 实例/执行结果1. using namespace std;  2. class minBoard  3. public:  4.     minBoard(int n, int m, int 

7、*B);  5.     int* getBestx()return bestx;  6.     int getMinl()return minl;  7. private:      8.     int minl;/最优最大长度  9.     

8、;int nowl;/当前最大长度  10.     int *low;/lowi表示第i块连接块中最左边的电路板的下标  11.     int *high;/highi表示第i快连接块中最右边的电路板的下标  12.     int *x;/当前解向量  13.     int *bestx;/当前最优解

9、向量  14.     int *B;/Bij = 1表示第i个电路板在第j个连接块中  15.     int n;/电路板数量  16.     int m;/连接块数量  17.     int t;/递归深度  18.     vo

10、id Backtrack(int t);/回溯递归函数  19.     int caNowl(int t);/计算当前排列的最大长度  20. ;  21. minBoard:minBoard(int n, int m, int *B)  22.     this->B = B;  23.  

11、;   this->n = n;  24.     this->m = m;  25.     this->t = 1;  26.     minl = 0x7fffffff;  27.     nowl = 0

12、;  28.     x = new intn + 1;  29.     bestx = new intn + 1;  30.     for (int i = 1; i <= n; +i)  31.  

13、;     32.         xi = i;  33.       34.     low = new intm + 1;  35.     high = new intm 

14、+ 1;  36.     this->Backtrack(t);  37.   38. int minBoard:caNowl(int t)  39.     for (int i = 1; i <= m; +i)  40.       

15、;  lowi = n + 1;  41.         highi = 0;  42.       43.     for (i = 1; i <= t; +i)  44.   &

16、#160;   45.         for (int j = 1; j <= m; +j)  46.           47.             if&

17、#160;(B(m + 1) * xi + j)  48.               49.                 if (lowj > i)lowj =

18、0;i;  50.                 if (highj < i)highj = i;  51.               52.     

19、0;     53.           54.       55.     int maxt = 0;  56.     for (int j = 1; j <= m; +

20、j)  57.       58.         if (highj - lowj > maxt &&lowj <= n)  59.           60.     

21、        maxt = highj - lowj;  61.           62.       63.     return maxt;  64.       

22、;        65.   66. void minBoard:Backtrack(int t)  67.     if (t > n)/若能够达到说明满足条件nowl < minl  68.       69.      &

23、#160;  /更新最优解  70.         for (int j = 1; j <= n; +j)  71.           72.           

24、60; bestxj = xj;  73.           74.         minl = nowl;  75.       76.     else  77.    &

25、#160;    for (int i = t; i <= n; +i)  78.           79.         /产生下一个排列  80.         &

26、#160;   swap(xt,xi);  81.         /记录原始nowl当前最大长度用于恢复  82.             int reNowl = nowl;  83.        

27、60;/计算当前组合的最大长度  84.             nowl = caNowl(t);  85.             if(nowl < minl)  86.       &#

28、160;         Backtrack(t+1);  87.               88.         /回溯恢复状态  89.         

29、0;   swap(xi,xt);  90.             nowl = reNowl;  91.           92.       93.   94. int main() 

30、; 95.         int n,m;  96.         in>>n>>m;  97.         int *B = new int(m + 1)*(n + 1); &

31、#160;98.         for (int i = 1; i <= n; +i)  99.           100.             for (int j

32、 = 1; j <= m; +j)  101.               102.                 in>>Bi*(m+1) + j;  103

33、.               104.           105.         minBoard minB(n,m,B);  106.          

34、; 107.         out<<"Case #"<<Case<<": "<<minB.getMinl()<<endl;  108.         for (i = 1; i <= n; +i) 

35、 109.           110.             out<<minB.getBestx()i<<" "  111.           112.    

36、;     out<<endl;  113.       114.     return 0;  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!个

37、节点，对于剪枝函数caNowl复杂度为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小的数，记

38、为；4. 查找中所有小于等于的数；5. 根据第4步查找的结果找出在集合S中对应的数即为S中最接近S的中位数的k个数。 关于第三步,求数组中第k小的数,线性时间复杂度的具体算法描述如下:基于快排序思想，步骤如下：1. 随机选择一个支点2. 将比支点大的数，放到数组左边；将比支点小的数放到数组右边；将支点放到中间(属于左部分)3. 设左部分的长度为L,          当K < L时，递归地在左部分找第K大的数       

39、0;  当K > L时，递归地在有部分中找第(K - L)大的数          当K = L时，返回左右两部分的分割点（即原来的支点），就是要求的第K 大的数4. 实例/执行结果输入：输出：5. 分析T(n)/S(n)1) 策略1 T(n)取决于所采用的排序算法，根据已知的效率比较高的排序算法如归并排序或者堆排序，2) 策略2 第一步，；第二步，一遍扫描即可，；第三步，采用STL中的nth_element算法，该算法的平均；第四步，一遍扫描找出符合要求的数即可，因此。根据算法效率度量的

40、加法规则，整个算法的。二、 带权中位数邮局选址问题1. 问题描述 对分别具有正的权重且的n个不同元素，带权中位数是满足如下条件的元素： 邮局选址问题（post-office location problem） 定义如下：已知n个点及与它们相联系的权重，要求希望确定一点p（p不一定是n个输入之一），使和式达到 最小，其中，表示a与b之间的距离。试论证带权中位数是一维邮局问题的最优解。此时。2. 证明思路 设是带权中位数，对于任意一点，设。要证明 f(p) 是最小值，则只需要证明对于任意地x，f(x)-f(p)0。3. 证明过程i. 当时1. 当：2. 当：3. 当 且 同理，当时，。

41、问题得以证明，故带权中位数为一维邮局选址位置的最优解。参考文档算法导论第九章：中位数和顺序统计学 寻找数组中第k小元素：查找数组中第k个最小元素对快排的改动STL 源码分析-nth_element() 使用与源码分析STL源码解析 - nth_element：带权中位数： 算法导论_中位数与带权中位数：单机和多机最优服务次序一单机最优服务次序1.问题描述 设有个顾客同时等待一项服务。顾客需要的服务时间为，。应如何安排个顾客的服务次序才能使平均等待时间达到最小 ? 平均等待时间是个顾客等待服务时间的总和除以。2.问题分析 采用贪心算法，第一个被服务的顾客所需的等待时间为0，由

42、于只有一个服务机，因此第二个顾客的等待时间取决于第一个顾客，令表示第个顾客的等待服务时间，表示当前队列长度为时候的总服务时间，即，。根据上公式有，因此若要第二个顾客的等待时间小，则第一个顾客的服务时间是最短的，那么我们首先将，按照升序进行排序，该顺序即为服务次序，由于在这个例子中贪心算法的局部最优即使它的全局最优，因此它的最优服务次序即的升序序列。其时间复杂度主要取决于排序算法的时间复杂度，我采用的是冒泡排序，时间复杂度为。3.问题求解1. N个顾客，每个顾客服务时间为t i.2. 将所有顾客的服务时间存在数组data中3. 将data内所有数据从小到大进行排序4. 用数组sequence存储

43、排序队列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 String fileString;private int num;private int data;private int serviceNum;publ

44、ic 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();num=Integer.valueOf(bReader.readLine();String DataString=bReader.readLine()

45、;data=new intnum;String dataString2=new Stringnum;dataString2=DataString.split(" ");for(int i=0;i<num;i+)datai=Integer.valueOf(dataString2i);fReader.close(); catch (Exception e) / TODO: handle exceptionSystem.out.println(e.toString();public int getNum()return this.num;public int getData

46、()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;i<num;i+)

47、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(

48、)for(int i=0;i<num;i+)for(int j=0;j<num;j+)if(datai<=dataj)int k=0;k=datai;datai=dataj;dataj=k;public void setSequence()for(int i=0;i<num;i+)sequencei=datai;public int getSequence()return this.sequence;public void countTime()int totalTime=0;int time=new intnum;time0=0;totalTime +=time0;f

49、or(int i=1;i<num;i+)for(int j=0;j<i;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<num-1;i+)System.out.print(sequencei+"->");System.out.println(seq

50、uencenum-1);System.out.println("平均等待时间为："+t);主函数代码：输入格式为：1.服务机数量2.顾客数量3.每一个顾客的服务时间结果为：二多机最优服务次序1.问题描述设有个顾客同时等待服务，服务机数量为。顾客需要的服务时间为，。应如何安排个顾客的服务次序才能使平均等待时间达到最小 ? 平均等待时间是个顾客等待服务时间的总和除以。2.问题分析依旧采取贪心算法，首先还是将，按照升序进行排序，由于本例子中服务机数量为，因此前个顾客的等待时间均为0，第个顾客则选择当前服务时间最短的那一个服务机进行等待，依次排序，从而贪心得到最优的服务次序，因此在

51、本例中贪心算法的局部最优也就是它的全局最优，因此得到的最优序列即为全局最优序列。其时间复杂度为：。3.问题求解1.N个顾客，每个顾客服务时间为t i.2. 将所有顾客的服务时间存在数组data中3.将data内所有数据从小到大进行排序4.用数组ArrayList<Integer> sequence存储m个服务排序队列5.采用贪心算法依次选取data中的元素放入当前最短的sequence中6.最终ArrayList<Integer> sequence的内容即为最优服务次序读取文件的类和单机服务相同多机服务类：import java.util.ArrayList; publ

52、ic class MutiService private int num;private int serviceNum;private int data;private ArrayList<Integer> sequence;private int timePerSequence;private double t;public MutiService(ReadFile rFile)this.num=rFile.getNum();serviceNum=rFile.getServiceNum();data=new intnum;data=rFile.getData();sequence

53、=new ArrayListserviceNum;timePerSequence=new intserviceNum;for(int i=0;i<serviceNum;i+)sequencei=new ArrayList<Integer>();timePerSequencei=0;sort();setSequence();setAverageTime();public void sort()for(int i=0;i<num;i+)for(int j=0;j<num;j+)if(datai<=dataj)int k=0;k=datai;datai=dataj

54、;dataj=k;public void setSequence()for(int i=0;i<num;i+)int index=getMinSequenceIndex();sequenceindex.add(datai);timePerSequenceindex+=datai;/System.out.println("第"+i+"个数："+"最小序列为："+index +"time:"+timePerSequenceindex);public int getMinSequenceIndex()int k=-

55、1;int min=10000;for(int i=0;i<serviceNum;i+)if(timePerSequencei<=min)min=timePerSequencei;k=i;return k;public void setAverageTime()int totalTime=0;for(int i=0;i<serviceNum;i+)int tmpTime=0;int time=new intsequencei.size();time0=0;tmpTime+=time0;for(int j=1;j<sequencei.size();j+)for(int k

56、=0;k<j;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;i<serviceNum;i+)System.out.print("服务机"+i+"次序为:");for(int j=0;j&

57、lt;sequencei.size()-1;j+)System.out.print(sequencei.get(j)+"->");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.每一个顾客的服务时间结果为：网格行走问题

58、题目描述 给定一个m x n的矩形网格，设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干个网格点处设置了障碍，表示该网格点不可到达。试设计一个算法，求出汽车从起点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

59、)->(4, 4)解题思路 以每个网格点为结点，可达网格点的网格边为边建图，则可以建立无向有环图。所以就将题目转换成了无向有环图上的两点间最短路问题。而两点间最短路问题的复杂度不会低于单源最短路问题，所以就将题目转换为无向有环图上的单源最短路问题。 无向有环图上的最短路问题的经典算法有：Dijkstra、Bellman-Ford、Floyd-Warshall。其中，Dijkstra和Bellman-Ford可以求解单元最短路，Bellman-Ford可以求解带负边的最短路。Floyd-Warshall可以求解任意两点最短路。 对于无负边的情况，Dijkstra算法的效率最高，若使用优先队

60、列来优化，时间复杂度可以降为O(|E|log|V|)。故选择Dijkstra算法来求解。 具体来说，Dijkstra算法基于贪心思想，在求解过程中利用记忆化搜索（动规）来辅助求解。考虑网格点(i, j)的情况，假设从起点到(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更新其余结点。也就是在这一步时，

61、认为d(v)就是s到v的最短路。贪心证明：因为边权为正，所以当d(v)最小时不可能通过别的点到达v使得d(v)更小。 当算法结束时，即可以求得所有点的最短路。最短路径统计 新开一个数组pa存储每个结点的前驱结点，在递推式du+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 =

62、 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;import 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.u

63、til.Queue;import java.util.Scanner;class Main class Edge int from, to, cost;public Edge(int from, int to, int cost)this.from = from; this.to = to; this.cost = cost;class HeapNode implements Comparable<HeapNode>int d, u;public HeapNode(int d, int u)this.d = d; this.u = u;Overridepublic int comp

64、areTo(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;boolean done = new booleanmaxn, obstacle = new booleanmaxn;List<Edge> edges;List<List<Integer>> G;void dijkstra()Arrays.fill(d,0,n*m,INF);Arrays.f

65、ill(done,0,n*m,false);Arrays.fill(pa, 0, n*m, -1);d0 = 0;Queue<HeapNode> Q = new PriorityQueue<HeapNode>();Q.add(new HeapNode(0, 0);while(!Q.isEmpty()HeapNode x = Q.poll();int u = x.u;if(doneu) continue;doneu = true;for(int i=0; i<G.get(u).size(); i+)Edge e = edges.get(G.get(u).get(i)

66、;if(obstaclee.to) continue;if(de.from + e.cost < de.to)pae.to = e.from;de.to = de.from + e.cost;Q.add(new HeapNode(de.to, e.to);void addEdge(int u, int v, int cost)G.get(u).add(edges.size();edges.add(new Edge(u,v,cost);G.get(v).add(edges.size();edges.add(new Edge(v,u,cost);boolean first = true;vo

67、id print_path(int u)if(pau != -1) print_path(pau);if(first) first = false;else System.out.print("->");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() throws IOExcepti

68、on n = in.nextInt(); m = in.nextInt();int cost;G = new ArrayList<List<Integer>>();for(int i=0; i<n*m; i+)G.add(new ArrayList<Integer>();edges = new ArrayList<Edge>();for(int i=0; i<m-1; i+)cost = in.nextInt();addEdge(i, i+1, cost);for(int i=0; i<n-1; i+)for(int j=0;

69、j<m; j+)cost = in.nextInt();addEdge(i*m+j, (i+1)*m+j, cost);for(int j=0; j<m-1; j+)cost =in.nextInt();addEdge(i+1)*m+j, (i+1)*m+j+1,cost);int k = in.nextInt(), u, v;Arrays.fill(obstacle, 0, n*m, false);while(k- > 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 SSSP = new Main();SSSP.begin();SSSP.close();荷兰国旗问题1.原问题描述将乱序的红白蓝三色小球排列成有序的红白蓝三色的