算法设计与分析期末复习部分题目.ppt

1、问题毽子、动态规划是解决多层次决策最优化问题的一种茄子方法。图中显示的电路网络，两点之间连接中的数字表示两点之间的距离，必须获取从A到E的路径以使总距离最小化。多段图形的最短路问题，图G=(V，E)是具有权重的连接图形。顶点集V除以K个不相交的子集Vi(2kn，1ik)，E的所有边(u，V)都必须有uVi。多段图的最短路径问题是找出从源到端点的最小成本路径。多段图形将顶点分割为k个不徐璐相交的子集片段，因此多段图形分割为k个分段，每个k个分段包含顶点的一个子集。在不丢失一般性的情况下，按线段顺序对多段图形中的顶点编号，同一段中的顶点顺序并不重要。如果图形中的顶点数为n，则源点S的编号为0，结束

2、T的编号为n-1，对于图形中的所有边(U，V)，顶点U的编号小于顶点V的编号。下面考虑了多段图的最短路径问题的西餐创建。使用Costn数组作为存储子故障诊断的表。costi表示顶点I到端点n-1的最短路径、阵列pathn存储状态、pathi表示顶点I到端点n-1的路径中顶点I的下一个顶点。例如：costi=mincij costj (ijn-1和顶点j是顶点I的相邻点)(1)使pathi=cij costj最小的j (2)，算法主要由三部分组成。第一部分是初始化部分，时间性能如下第二部分是从每个顶点到端点按顺序计算的最短路径，由两个嵌套循环组成，外部循环执行n-1次，内部循环计算所有传出边，所

3、有循环中每个传出边只计算一次。假设图形中的面数为m，则牙齿部分的时间性能为o (m)。第三部分是输出最短路径通过的顶点，时间性能为O(n)。因此，算法6.2的时间复杂性为O(n m)。所有点对的最短路问题，问题设置G=(V，E)是每个边(I，j)上具有非负长度li，j的方向图。如果从顶点I到顶点j没有边，则li，j=。问题：找到每个顶点到所有其他顶点的距离。其中，顶点x到顶点y的距离是从x到y的最短路径长度。为简便起见，V=1，2，n，设置I和J由V的徐璐其他两个顶点从I定义为J，这是不通过k 1，k 2，n的所有顶点的最短路径长度。如果所有点对的最短路问题，最优解结构分析K是从I到J的最短路

4、径上的节点，则从I到K，K到J的两部分子路径也必须最短。也就是说，所有点对的最短路径问题满足了最佳子结构特性。所有点对的最短路问题，建立递归关系，所有点对的最短路问题，算法(Floyd算法)，输入：nn维矩阵l1.n，1.输入n以直接图形g=(1，2，n，)，所有点对的最短路问题，d=l for k=1 to n for I=1 to n for j=1 to n di，j=mindi，j，DDend for end for end for end for end for，所有点对的最短路问题，例如，所有点对的最短路问题，0/1背包问题，问题设置u=u1，U2，un是可以放在C容量的背包中的n

5、个项目的集合(1=j=n j)问题是，要用总体积不超过C的U的部分物品装满背包，然后最大化总价值。要求：背包不能包含两个或更多同类物品。0/1背包问题，问题是通过格式化带N项的U来查找N元组，在约束条件下最大。0/1背包问题，最佳子结构特性设置(y1，y2，yn)是0/1背包问题(y1，yn-1)的最佳解决方案。，0/1背包问题，证明：设置(z1，zn-1)是上述子问题的最佳解决方案，(y1，yn-1)不是最佳解决方案，因此，设置0/1背包问题，0/1背包问题，递归关系ViI的范围为0到n，j的范围为0到c。0/1背包需要Vn，C。V0、j=0、Vi、0=0。如果I和j都大于0，则Vi，j是以

6、下两个量的最大值：Vi-1，J:以最佳方法装入体积为J的背包，作为u1、u2、ui-1的物品，获得的价值最大值Vi-1、j-wi VI:以最佳方法从U1、U2、ui-1中获得的物品。0/1背包问题，通过以上分析，可以得到以下递归式：0/1背包问题，算法for I=0 to n VI，0=0 end for j=0 to c v0，j=0 end for I=1 to n J=maxvi，J，VI-1，J通过改进算法，空间复杂性假设您有一个O(C)、0/1背包问题，例如容量为9的背包，需要装入体积为2、3、4和5的4茄子项目。其价值分别是3，4，5，7。void knapsack (int n，

7、float c，float v，float w，float x)/v，w包含n个条目的/C，每个条目按Vi/WiVi 1/wi 1排序for(I=1)；ICU)break；Xi=1；Cu=Cu-wi；if(I=n)Xi=Cu/wi；算法背包问题贪心的算法，算法knapsack的主要计算时间是将各种物品按单位重量的价值从大到小排序。因此，算法计算时间上限为O(nlogn)。当然，要证明算法的正确性，还必须证明背包问题贪婪选择的性质。最大子段和问题，问题说明：由n个整数(负整数)组成的序列a1、a2、an获取该序列子段总和的最大值。当所有整数都为负数时，定义最大子线段和0。因此，所需的最佳值为(a

8、1、a2、a3、a4、a5、a6)=(-2、11、-4、13、-5、-2)，例如int MaxSum，2 .如解决分割方法、解决问题的结构所示，适合用分割策略解决。将给定序列a1:n除以两个长度相同的a1:n/1和an/2 1:n，分别计算两个牙齿段的最大子段的总和，从而使a 13360n的最大子段和an/2 1:n的最大子段，以及相同a1:n的最大子段和以下格式。a，b两种情况都可以递归求。对于情形C，我们很容易看出我们正在优化an/2和an/2 1牙齿的子序列。因此，a 13360n/2和an/2 1:n可以分别计算以下S1和S2:S1 S2是复本c取得最佳值。进行如下所示的分割算法设计。intmaxsubsum (inta，intleft，int right)intsum=0；If (left=right)sum=aleft0？Aleft:0Elseintcenter=(左右)/2；Intleftsum=maxsubsum (a，left，center)；Intrightsum=maxsubsum (a，中心1，右)；int