《西电软件学院算法实验报告模板2份分析》由会员分享，可在线阅读，更多相关《西电软件学院算法实验报告模板2份分析（34页珍藏版）》请在金锄头文库上搜索。
1、第二次试验问题：Matrix-chain product分析：本题是矩阵链乘问题，需要求出最优括号化方案。即在矩阵的乘法链上 添加括号来改变运算顺序以使矩阵链乘法的代价降低。可以分析该链乘的一个子段总结一些结论。假设 mi,j表示A*-*Aj的链 成需要进行的乘法次数（假设j-i足够大），我们可以将Ai* Aj分为两段进行 计算：（Ai*Ak） *（ Ak+i*Aj）可以得出mi,j的递推公式可以得出，当i=j的时候，mi,j=O。当ij的时候。k的取值范围是i到 j-1，对于k的每一个取值都可以得到一个 mi,j的值，取出最小值即时 mi,j 的最优化方案。递推公式如下：可以根据上式得到一个
2、递归算法。本题即是求m1, n的值。用二维数组m存储mi,j的值，用二维数组s来储存应当分割的位置。 以本题中第一个矩阵a） 3, 5, 2, 1,10功例，可以得出如下矩阵：通过m数组可以得出最少的乘法次数，通过 s数组可以输出最优方案。遇到的问题：在输出s数组的结果的时候仍然需要递归调用，需要合适的控制递归的 条件。总结：在矩阵链乘问题中可以看出， 动态规划结合递归的思想可以快捷的解决 很多问题。本题中，重点是归纳出 mi,j的递推公式。问题：Longest Common Subsequence分析：本题即是最长公共子序列问题。假设有序列 Am和序列Bn,显然，对 于每一个i,j，都对应着
3、一个公共子序列的长度。假设长度为 c，就可以得到 一个二维数组cm,n。对于ci,j，当Ai=Bj的时候，问题就转变为求 A1.i-1 和B1.j-1的公共子序列长度的问题，所以ci，j的长度就是ci-1，j-1 + 1; 同理，当Ai != Bj的时候，ci,j应该在ci-1,j与ci,j-1中取最大值。另外，当 i或者j等于0的时候，显然c的值为0。由上面所述，可以得到递推公式如 下：为了解决这个问题，还如要定义另一个数组用于存放 c数组中每一个元素的来源。这个来源其实就反映了公共子串。可以通过箭头表示来源，相连 的箭头序列中指向左上方的箭头最多的一串对应的就是最长公共子序列。比如对于题目
4、中给出的第一个例子X: xzyzzyx Y: zxyyzxz 可以用一个矩阵表示计算的过程：遇到的问题：在算法中，=是属于 会给结果带来不同。在输出子序 列的时候，最长公共子序列可能不止一个，但是最终未能解决还是只能输出 一个。总结：最长公共子序列问题可以利用动态规划很好的解决。 动态规划的思想就 是根据规律获得推导公式，然后解决问题。问题：Longest Common Substring分析：Ai != Bj最长公共子序列问题就是和最长公共子串问题差不多，的时候，对应的ci, j置为0。推导公式如下：最终c数组的最大值max对应的就是最长公共子串，只需要将从本位置 向前述max-1个的子串即
5、是所求子串。总结：本题就是第二题的一种特殊的情况，即 c数组中的值不能从左和上两个 方向获取，其他基本相同。在代码上，只需要修改小部分代码就可以实现该 问题。四、问题：Max Sum分析：求和最大的子串。这个问题和第三题很像，不过这次不用二维数组而是 使用两个标记来标志所求子串的起始位置（maxb）结束位置（maxe）。思路 是，对于第i个元素，如果当前元素与目前选中的序列的 sum小于0，那么 这么序列不会被选择，更新 sumb 与 sume 的值；如果 sum 仍然大于 0，则 sum 可以选中。比较 sum 与 max的值，女口果 summax,贝U更新 maxb与 maxe的值。递推公
6、式如下：遇到的问题：在全是负数时出现问题， 后来讲 max 的初始值设置为第一个元素的值后 就能正常了。总结：动态规划能解决很多问题，找到递推公式非常重要。五、问题：Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.分析：观察本题图的特点，发现可以将图分解为 7 个部分，以此可以计算到每 一个节点的最短的路径。即可求出最终的最短路径。总结：结合本题中的特殊情况，可以采用适当的方法来处理。第三次实验问题:Knapsack Problem. There ar
7、e 5 items that have a value and weight list below, the kn apsack can contain at most 100 Lbs. Solve the problem both as fracti onal kn apsack and 0/1 kn apsack.5alne(SUS)2030654060weiglit(Lbs)1020304050weight2L52J11.2分析：本题是背包问题的两个解法。对于部分背包来说比较简单，就是将单位 价值大的物品优先放置到背包中，这样就能在背包中获取最大的价值。但是 对于0/1背包问题来说，就相
8、对复杂了。可以通过贪心算法解决。经过分析， 我们转化这个问题为将n件物品放置到容量为w的容器中。这里，每件物品 只可能有一个状态：放入/不放入，我们用0/1来对应。用vi,w来表示前i 件物品选出重量不超过 w的物品，并且构成的最大的价值。那么，可以分析 得出vi,w的递推式。如果i=0或者w=0，显然vI,w = 0;如果第i件物品的重 量wiw贝U i不可能放入容器中；如果 i能够放入容器（即 wi vi-1,w时才可能会放入。关系式如下这样，我们可以认为，每一次都恰到好处的选择了放或者不放一个物品 直到最后一个物品，我们得到的一定就是最好的结果总结:背包问题是一个典型的贪心算法的例子。
9、在解决问题的时候可以将当前 步骤做到最好，然后通过推导，有可能得到一个关系式，这样就能使问题得 到解决。在本题中，我们可以通过第i件物品是否应该放在容量的 w的背包 中进行分析，最终得到了一个递推式。问题：A simple scheduling problem. We are given jobs j1, j2 jn, all with known running times t1, t2 tn respectively. We have a si ngle processor. What is the best way to schedule these jobs in order to m
10、inimize the average completion time. Assume that it is a nonpreemptive scheduling: once a job is started, it must run to completion. The following is an instance。分析：这是一个线程调度问题，通过操作系统课程的学习，我们了解到应当采 用短作业优先的调度方式。 可以采用快速排序对进程顺序进行排序即可得到 调度时间。总结：在进程调度问题中，如果想获取最短的平均周转时间（单线程）应当使 用短作业优先的算法。问题：单源点最短路径分析：本题中，因
11、为路径中存在负边，所以应当使用 bellman-ford 算法。为了 方便的使用该算法，需要首先创建合适的边的数据结构。这样，在遍历边的 时候比较快捷。首先需要初始化每一个节点的 d 值，源点的 d 值为 0，其他点的 d 值的 初始值为max （个足够大的数）。表示在初始时，源点到各点都不可达。 然后，对每条边进行松弛操作，进行 |V|-1 次松弛之后，可以得到结果。随 后，检测结果， 如果依然存在可松弛的节点的话， 说明存在权重为负的环路。 表明结果不存在。总结：该算法并没有在一开始就计算是否存在权值为负的环路。 而是通过结果 来分析，如果没有负环路，一定能在松弛循环结束后便不能继续被松弛
12、。由 此，可以判断是否存在最短路径。所以，该算法不仅可以判断一个图是否存 在最短路径，还能得到最短路径。四、 问题：All-pairs shortest paths分析：所有节点对的最短路径问题，应当使用 Johnson 算法。 Johnson 算法需 要用 dijkstra 和 bellman-ford 算法作为子程序。如果图G=(V,E中所有的边权重都为非负值，可以通过在每一个节点 使用 dijkstra 算法求出所有节点虹之间的最短路径；如果该图包含权值为负 的边，但是没有权重为负的环路，那么只要计算一组新的非负权重值，然后 使用同样的方法即可。总结：Johnson算法相当于是对dijk
13、stra算法和bellman-ford算法的应用，结合 这两个算法，通过使用重新赋值权重来生成非负权重，最终得到所有节点对 之间的最短路径。第四次实验题目0/1 KnapsackProblem. There are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem using back-track ing algorithm and try to draw the tree gen erated.value(SUS)203065
14、4060wighr(Lbs)1020304050value weight21.52.111.2分析：使用回溯法解决0/1背包问题。可以用一个数组来记录“选中”物品的 情况。首先，选择第一件物品，如果超重的话不选择该物品；如果没有超重， 继续添加下一个物品，这样选择下去，最终一定可以选择完全部的物品。计 算目前选择物品的totalValue值。继续回溯，如果的到新的totalValue值，如 果大于前一个值，那么更新该值，并且更新保存选择的数组中。总结：从8皇后问题可以发现回溯法的一般方法。经过代入到这个问题中，发 现确实可行。回溯法需要一个合理的递归函数，这个函数的终止条件也需要 认真的分析。
15、比如这一题和8皇后问题都可以使用元素的个数作为一个结束 条件，另外还需要注意导致“回溯”的位置。题目：Solve the 8-Quee n problem using back-track ing algorithm分析：8皇后问题是回溯法的一个典型的例题。假设目前已经在奇葩的前i(i8) 行放置了 i和皇后并且位置合法。然后我们放置第j (j=i+1)个皇后，先将j放置在第一列，如果合法就放置第j+1个皇后；如果放置在当前列不合法， 就将j皇后放置在第二列以此类推，如果全部不行，将会返回调用该函 数的上一层函数。如果i的值等于8,说明已经完全摆放成功，就可以输出 结果，输出后返回上一层调用，继续查找其他的符合题意的皇后摆放。总结：使用回溯法，能后很好的解决 8皇后问题。在使用回溯法是，应当注意如何使用递归调用，尤其是递归调用的结束条件算法导论上机实验报告册班级：1313012学号：13130120180姓名
