实验4 动态规划算法设计
《算法分析与设计》实验报告
实验四动态规划算法设计
姓名xxxxxxx 学号xxxxxxxx 班级xxxxxxxx
时间：xxxxxx 地点：xxxx
同组人：无
指导教师：xxxxxx
实验目的
1.掌握动态规划法算法设计的一般原理和方法。
2.理解动态规划向前处理和向后处理的思想，掌握递推公式的求解方法。
3.掌握多段图、每对结点之间最短路径的计算算法。
4.能用动态规划法设计算法求解一般问题。
实验内容
1.设计求解多段图问题的动态规划程序，上机调试通过。
2.设计求解每对结点之间最短路径问题的动态规划程序，上机调试通过。
3.准备几个多段图和几个道路交通图的数据。
4.输入求解多段图问题的动态规划程序，并用准备的数据调试通过。
5.输入每对结点之间最短路径问题的动态规划程序，并用准备的数据调试通
过。
实验环境
硬件：Intel(R) Pentium(R) CPU RAM:4G
软件：Myeclipse2013
编程语言：Java 实验前准备
1、程序设计：见附1
实验步骤
1、准备实验数据。
准备几个多段图和几个道路交通图的数据。
多段图的实验数据和道路交通图的数据均可利用程序生成(ReadEdgeData.java的randMultGraph和radomDirectedGraph)；
其中多段图的生成原则是n个结点分为k段，且每段大约为4到5个结点，第一个和最后一个结点要和相邻段所有结点相连，中间段的结点与相邻段的结点至少要有一个结点相邻，每条边的成本随机生成。
道路交通图至少则是生成有图的方式，n个结点有（n*n）*4/5使边数不至于多，也不至于少。
将生成的边以数对的形式存于文本文件中，如下图，其中第一行分别为结点数和边数。剩下的若干行表示每条表的两个结点和成本。在需要的时间通过读取文本文件来获取数据。
2、多段图问题的动态规划程序
根据算法设计的多段图向前处理法的sparks语言，写出相应的java程序，并调试验证通过。其中边是以邻接表的形式表现出来更方便显示点之间的邻接关系。
int[] COST=new int[n+1];//用来记录从j到最后一个结点的最小权值
int[] D=new int[n];//D[j]用来表示j到最后一个结点最短路径上的后续一个结点
for(int j=n-1;j>=1;j--){
int minCost=Graph.MAXCOST;
int r=1;
LinkedList
for(Edge edge: costList){//找到j之后的一个点r，使
edge.cost+COST[r]取最小值，并将最小值赋给minCost
int v=edge.v;//edge.cost代表j到v的权值
if(v>j&&edge.cost+COST[v] { r=v; minCost=edge.cost+COST[v]; } } COST[j]=minCost;//将从j到最后一个结点的最短路径的权值赋给COST[j] D[j]=r; } P[1]=1;//第一个结点 P[k]=n;//最后一个结点 for(int j=2;j P[j]=D[P[j-1]]; } } 将课本上的实验数据进行计算得到结果如下，其结果与书的最短路径一致。 3、最短路径问题的动态规划程序 根据最短路径问题的动态规划程序算法的sparks语言写出对应的java程序，并调试验证通过，对比相同数据下的用求单源点最短路径算法求解每对结点之间 最短路径得出的结果相同 /** * 计算每对结点之间的最短路径长度 * @param COST n个结点的邻接矩阵 * @param A A[i][j]是从i到j的最短路径的成本 * @param n 结点个数 */ public static void ALL_PATHS(int[][] COST,int[][] A,int n){ for(int i =0; i <= n; i++){//将COST[i][j]复制到A[i][j]中for(int j =0; j <= n; j++){ A[i][j]= COST[i][j]; } } for(int k =1; k <= n; k++){// 对最高下标为k的结点的路径 for(int i =1; i <= n; i++){// 对于所有可能的结点对 for(int j =1; j <= n; j++){//比较A[i][j] 和 (A[i][k] + A[k][j])和大小，以确定是否经过k if(A[i][k]!=Graph.MAXCOST &&A[k][j]!=Graph.MAXCOST &&(A[i][j]>(A[i][k]+ A[k][j]))) A[i][j]= A[i][k]+ A[k][j]; } } } } 输出结点如下图，且结果与实验三得到的单源最短路径一致 4、（附加3）最短路径问题的动态规划的最短路径 根据短路径问题的动态规划程序，添加一个AllParent数组用来记录每个结点 的最短路径的父结点，最后通过入栈和出栈的方式输出每个结点的路径 实验结果及其分析 1、多段图的向前处理法 实验中取100000次运行的数据 该问题根据课上的理论分析知为时间复杂度为O(n+e)，其中e 为边数，似于线性，与图有所区别，这可以是由于数据量太少和计算和复杂造成的噪声干扰，但总体来看其趋势仍接近线性； 2、最短路径问题的动态规划程序 最短路径问题的动态规划程序实现结果 通过课堂的理论分析知，结点之间的最短路径问题的时间复杂度为O(n3),而实验结果通过添加趋势线可能符合理论分析结果；它与贪心方法的时间复杂度一样，但成本上比贪心方法弱些且计算简单，容易理解。 附加3是对上题添加路径，只是在计算过程中记录每个结点的上个结点，以树的形式保存下来，再通过先入栈再出栈的方式将每对结点的路径输出出来。 4、总结 动态规划是将一个问题的活动分为若干个阶段，而且每个阶段在任一阶段后的行为都仅信赖于i阶段的过程状态它指出无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最伟决策序列，这便是最优性原理。 动态规划和贪心算法一样都是求最短路径问题，通过最优性原理求解出最优 策略，可以快速准确的救出多段图问题和每对结点的最短路径问题， 附：源代码 1、多段图的向前处理法Fgraph.java import java.io.File; import java.util.LinkedList; public class Fgraph { /** * 多段图的向前处理算法 * * @param args */ public static void main(String[] args){ int Z =10;// 数据个数 int tp =0;// 文件的初始编号 long[][] D =new long[Z][2];// 记录数据量和运行时间的数组 String surDir ="E:\\我的文档\\大三下\\算法分析与设计\\实验\\实验4 动态规划算法设计\\data"; for(int t =0; t <10; t++){ String fileName ="MultGraph"+ t +".txt"; File sur =new File(surDir, fileName); Graph G =null; // 从文件中读取图的有关信息 if((G = ReadEdgeData.readEdges(sur,true))==null){ System.out.println("读取错误，请检查！"); return; } G.initCostList(); int k =5+ t;// 段数 int n = G.n;// 结点数 int[] P =new int[k +1]; // 循环计算MM次计算其运行时间 long time =0, T1, T2; int MM =100000; T1 = System.currentTimeMillis(); for(int j =0; j < MM; j++){ FGRAPH(G, k, n, P); } T2 = System.currentTimeMillis(); time = T2 - T1; D[t][0]= n;// 将结点和对应的计算时间加入数组便于输出 D[t][1]= time; /*for (int i = 1; i < P.length; i++) { System.out.print(P[i] + "\t"); } System.out.println();*/ } //输出结点和对应的运行时间 for(int k =0; k < Z; k++){ System.out.print(D[k][0]+"\t"); } System.out.println(); for(int k =0; k < Z; k++){ System.out.print(D[k][1]+"\t"); } System.out.println(); } /** * * 输入是按段的顺序给结点编号的，G表示图，并且用邻接表的访求来表示边集，最后得到的是最小成本路径P * * @param G * 图 * @param k * k段图 * @param n * n个结点 * @param P * 最小成本路径 * */ public static void FGRAPH(Graph G,int k,int n,int[] P){ int[] COST =new int[n +1];// 用来记录从j到最后一个结点的最小权值 int[] D =new int[n];// D[j]用来表示j到最后一个结点最短路径上的后续一个结点 for(int j = n -1; j >=1; j--){ int minCost = Graph.MAXCOST; int r =1; LinkedList for(Edge edge : costList){// 找到j之后的一个点r，使 edge.cost+COST[r]取最小值，并将最小值赋给minCost int v = edge.v;// edge.cost代表j到v的权值 if(v > j && edge.cost + COST[v]< minCost){ r = v; 2、最短路径问题AllPaths.java import java.io.File; public class AllPaths { /** * 每对结点之前的最短路径长度 * * @param args */ public static void main(String[] args){ int Z =10;// 数据个数 int tp =21;// 文件的初始编号 long[][] D =new long[Z][2];// 记录数据量和运行时间的数组 String surDir ="E:\\我的文档\\大三下\\算法分析与设计\\实验\\实验4 动态规划算法设计\\data"; for(int t =0; t <10; t++){ String fileName ="Edges"+(tp+t)+".txt"; File sur =new File(surDir, fileName); Graph G =null; // 从文件中读取图的有关信息 if((G = ReadEdgeData.readEdges(sur,true))==null){ System.out.println("读取错误，请检查！"); return; } int n = G.getN(); int[][] COST = G.getCost(); /*for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (COST[i][j] == Graph.MAXCOST) { System.out.print("∞\t"); } else { System.out.print(COST[i][j] + "\t"); } } System.out.println(); }*/ int[][] A =new int[n +1][n +1]; int[][] AllParent=new int[n+1][n+1]; /******* 形如计算*****************************************************/ /*ALL_PATHS(COST, A, n);*/ // 循环计算MM次计算其运行时间 long time =0, T1, T2; int MM =10000; T1 = System.currentTimeMillis(); for(int j =0; j < MM; j++){ ALL_PATHS(COST, A, n,AllParent); } T2 = System.currentTimeMillis(); time = T2 - T1; D[t][0]= n;// 将结点和对应的计算时间加入数组便于输出 D[t][1]= time; /******* 计算结束*************************************************/ //System.out.println("/****************计算后所有对结点的最短路径****************************************************/"); /*for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (A[i][j] == Graph.MAXCOST) { System.out.print("∞\t"); } else { System.out.print(A[i][j] + "\t"); } } System.out.println(); } displayPath(AllParent,A,n);*/ } //输出结点和对应的运行时间 for(int k =0; k < Z; k++){ System.out.print(D[k][0]+"\t"); } System.out.println(); for(int k =0; k < Z; k++){ System.out.print(D[k][1]+"\t"); } System.out.println(); } /** * 计算每对结点之间的最短路径长度 * @param COST n个结点的邻接矩阵 * @param A A[i][j]是从i到j的最短路径的成本 * @param n 结点个数 */ public static void ALL_PATHS(int[][] COST,int[][] A,int n){ for(int i =0; i <= n; i++){//将COST[i][j]复制到A[i][j]中for(int j =0; j <= n; j++){ A[i][j]= COST[i][j]; } } for(int k =1; k <= n; k++){// 对最高下标为k的结点的路径 for(int i =1; i <= n; i++){// 对于所有可能的结点对 for(int j =1; j <= n; j++){//比较A[i][j] 和 (A[i][k] + A[k][j])和大小，以确定是否经过k if(A[i][k]!=Graph.MAXCOST &&A[k][j]!=Graph.MAXCOST &&(A[i][j]>(A[i][k]+ A[k][j]))) A[i][j]= A[i][k]+ A[k][j]; } } } } /** * 计算每对结点之间的最短路径长度,并将最短路径记录下来 * @param COST * @param A * @param n * @param AllParent */ public static void ALL_PATHS(int[][] COST,int[][] A,int n, int[][] AllParent){ for(int i =0; i <= n; i++){//将COST[i][j]复制到A[i][j]中，将将所有结点的父结点设为自身 for(int j =0; j <= n; j++){ A[i][j]= COST[i][j]; AllParent[i][j]= i; } } for(int k =1; k <= n; k++){// 对最高下标为k的结点的路径 for(int i =1; i <= n; i++){// 对于所有可能的结点对 for(int j =1; j <= n; j++){ if(A[i][k]!=Graph.MAXCOST &&A[k][j]!=Graph.MAXCOST &&(A[i][j]>(A[i][k]+ A[k][j]))){ A[i][j]= A[i][k]+ A[k][j]; AllParent[i][j]= k; } } } } } /** * 用来输出单源点路径 * @param v * @param parent * @param DIST * @param n */ public static void displayPath(int v,int[] parent,int[] DIST,int n){ int[] stack =new int[n]; for(int i =1; i <= n; i++){ if(i != v){ stack[0]= i; int p = parent[i]; int top =1; while((stack[top]= p)!= v){// 依次入栈 p = parent[p]; top++; } while(top >-1){// 依次出栈并输出 System.out.print(stack[top]); if(top >0){ System.out.print("==>"); } top--; } if(DIST[i]< Graph.MAXCOST){ System.out.println(":"+ DIST[i]); }else{ System.out.println(":Infinity"); } } } } /** * 用来输出所有点的最短路径 * @param AllParent * @param ALLDIST * @param n */ public static void displayPath(int[][] AllParent,int[][] ALLDIST, int n){ for(int i=1;i<=n;i++){ System.out.println("/**"+i+"到其它点的单源最路径*****************************/"); displayPath(i,AllParent[i],ALLDIST[i],n); } } } 3、图和边类Graph.java package test.exp4; import java.util.LinkedList; public class Graph { int n;//点的个数 int m;//边的个数 Edge[] edge;//m=edge.length+1，边从1开始到m止 int[][] cost; LinkedList public LinkedList return costList; } public void setCostList(LinkedList this.costList = costList; } boolean isDirected=false; public static int MAXCOST = Integer.MAX_VALUE;//表示无穷大 static int MINCOST = Integer.MIN_VALUE;//表示无穷大 public Graph(){}; public Graph(int n,int m,Edge[] edge,boolean isDirected){ this.m=m; this.n=n; this.edge=edge; this.isDirected=isDirected; this.initCost(); } public Graph(int n,int m,Edge[] edge){ this.m=m; this.n=n; this.edge=edge; isDirected=false; this.initCost(); } /** * 初始化邻接矩阵 * 将COST[0][j]和COST[i][0]设为列编号和行编号 * COST[i][i]将为0 * 不连通则将COST[i][j]设为无穷大 */ public void initCost(){ int[][] COST =new int[n +1][n +1]; for(int j=0;j<=n;j++){ COST[0][j]=j; } for(int i =1; i <= n; i++){//将所有边设为无穷大 COST[i][0]=i; for(int j =1; j <= n; j++){ if(i==j){ COST[i][j]=0; }else{ COST[i][j]= MAXCOST; } } } for(int k =1; k < edge.length; k++){//为邻接矩阵赋初值 COST[edge[k].u][edge[k].v]= edge[k].cost; if(!this.isDirected){//当为无向图时，只赋一边 COST[edge[k].v][edge[k].u]= edge[k].cost; } } this.cost=COST; } public void initCostList(){ costList=new LinkedList[n+1]; for(int i=0;i costList[i]=new LinkedList } for(int i=1;i int u=edge[i].u; int v=edge[i].v; int cost=edge[i].cost; Edge ed1=new Edge(u,v,cost); Edge ed2=new Edge(v,u,cost); costList[u].add(ed1); costList[v].add(ed2); } } public int getN(){ return n; } public void setN(int n){ this.n = n; } public int getM(){ return m; } public void setM(int m){ this.m = m; } public Edge[] getEdge(){ return edge; } public void setEdge(Edge[] edge){ this.edge = edge; } public int[][] getCost(){ return cost; } public void setCost(int[][] cost){ this.cost = cost; } public boolean isDirected(){ return isDirected; } public void setDirected(boolean isDirected){ this.isDirected = isDirected; } } /** * 边类 * @author XT * */ class Edge { int u; int v; int cost; public Edge(){}; public Edge(int u,int v,int cost){ this.u=u; this.v=v; this.cost=cost; } } 4、图的生成与读取ReadEdgeData.java package test.exp4; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.LinkedList; class ReadEdgeData{ /** * isDirected为true时表示读取有向边 * @param sur * @param isDirected * @return Graph */ public static Graph readEdges(File sur,boolean isDirected){ File date=sur; if(!date.exists()||!date.isFile()){ System.out.println("文件不存在或有误，请检查！"); return null; 华东师范大学计算机科学技术系上机实践报告 一、 内容与设计思想 1．对于以下5 个矩阵： M 1: 2?3, M 2: 3?6, M 3: 6?4, M 4: 4?2, M 5: 2?7 , (a) 找出这5个矩阵相乘需要的最小数量乘法的次数。 (b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。 输入： 第一行为正整数N,表示有N 组测试数据； 每组测试数据的第一行为n,表示有n 个矩阵,2<=n<=50； 接下去的n 行,每行有两个整数x 和y,表示第ni 个矩阵是x*y 的。 输出： 对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。 我们保证输出的结果在2^64之内。 基本思想： 对于n 个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： 2．定义0/1/2背包问题为：}x p max{n 1i i i ∑=。限制条件为：c x w n 1i i i ≤∑=，且 n i 1},2,1,0{x i ≤≤∈。设f(i , y)表示剩余容量为y ，剩余物品为：i ，i+1，…，n 时的最优解的值。 1．）给出f(i , y)的递推表达式； 2．）请设计求解f(i , y)的算法，并实现你的算法； 3．）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。 输入： 第一行为一个正整数N ，表示有几组测试数据。 每组测试数据的第一行为两个整数n 和M ，0 算法分析 设计与实验 王 源 二0一四年十月 实验一：分治算法及其应用 实验要求： 掌握分治算法的原理. 掌握递归算法及递归程序的设计. 能用程序设计语言设计求解典型问题的算法 实验题： 1、棋盘覆盖问题：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 2、最近对问题：设p 1=(x 1,y 1), p 2=(x 2,y 2), …, p n =(x 1,y 1)，是平面上n 个点构成的集合S ，最近对问题就是找出集合S 中距离最近的点对。 3、（选作）最大子段和问题：给定由n 个整数（可能有负整数）组成的序列(a 1, a 2, …, a n )， 最大子段和问题要求该序列形如 的最大值（1≤i ≤j ≤n ），当序列中所有整数均为负 整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 。 ∑=j i k k a ∑==4 220 k k a 实验要求： 基本动态规划法的原理方法； 能用程序设计语言实现求解背包问题的算法 实验题： 1、最长公共子序列问题：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij ≤m）。给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。 2、（选作）多段图的最短路径问题：设图G=(V, E)是一个带权有向图，如果把顶点集合V 划分成k个互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题求从源点到终点的最小代价路径。 3、 实验三：动态规划法 【实验目的】 应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]， A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （i=j ） m[i][j]= min{m[i][k]＋m[k+1][j]+n i-1n k n j （i 实验二动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 三、算法设计 void main() { 申明一个5*5的二维数组； for(int i=0;i<5;i++) { for(int j=0;j<=i;j++) { 输入数组元素p[i][j]; } } for(int k=0;k<5;k++) { for(int w=0;w<=k;w++) { 输出数组元素p[k][w]; } } for(int a=4;a>0;a--) { for(int s=0;s<=a;s++) { if(p[a][s]大于p[a][s+1]) p[a-1][s]等于p[a-1][s]加p[a][s]; else p[a-1][s] 等于p[a-1][s] 加p[a][s+1]; } } 输出p[0][0] } 四.程序调试及运行结果分析 五.实验总结 虽然这个实验比较简单，但是通过这次实验使我更加了解的动态规划法的好处和、，在解决问题时要尝试使用动态规划，这样就有可能得到一种即简单复杂性有不高的算法。 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 实验一简单算法设计 一.实验目的和要求 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力； 二．实验内容 (一)相等元素问题 1.问题描述先排序函数，再查找函数。 #define size 100 Typedef strat { Int Array[size] Int listlength }List List a; Main() { 1、输入 2、排序 3、查找 4、输出 } 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 测试数据 输入： 9 71 25 64 38 52 5 31 19 45 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No 3. 设计与实现的提示 算法最坏情况和平均情况的时间复杂性是衡量算法优劣的重要指标，算法设计要求尽可能设计比较高效的算法。 (二) 整数集合分解（选做） 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 测试数据 输入： 68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12 28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2 输出： 2 3 4 6 12 13 16 17 20 21 25 29 34 37 39 43 51 57 68 76 78 95 2 2 3 7 9 1 4 24 26 28 29 32 37 37 42 47 48 51 51 52 59 61 62 65 73 78 95 3. 设计与实现的提示 本题可以有多种方法。算法时间复杂性是选取算法的重要依据。输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。 一、实验目的 (2) 二、实验内容 (2) 三、实验步骤 (3) 四.程序调试及运行结果分析 (5) 附录：程序清单（程序过长，可附主要部分） (7) 实验四动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 题目二：最长单调递增子序列问题(课本184页例28) 设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 若存在i1 题目三 0-1背包问题 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，，物品的个数n。接下来的n 行表示n个物品的重量和价值。输出为最大的总价值。 输入样例： 20 3 11 9 9 10 7 5 输出样例 19 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 算法设计与分析实验指导书 实验一 C/C++环境及递归算法( 4学时) 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、经过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想, 分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。 三、实验题 1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一 串整数或字符, 输出结果能够用递归方法实现整数或字符的全排列。 2、设a,b,c是3个塔座。开始时, 在塔座a上有一叠共n个圆盘, 这些圆 盘自下而上, 由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上, 并仍按同样顺序叠置。 四、实验步骤 1．理解算法思想和问题要求; 2．编程实现题目要求; 3．上机输入和调试自己所编的程序; 4．验证分析实验结果; 5．整理出实验报告。 实验提示 1、 #include b=temp; } void perm(int list[],int k,int m) { if(k==m) { for(int i=0;i<=m;i++) cout< 学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日 实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 实验报告一 课程C++ 实验名称简单算法设计第 1 页专业_数学与应用数学_ __ 班级__ 双师一班学号105012011056 姓名陈萌 实验日期：2013 年 3 月9 日报告退发(订正、重做) 一、实验目的 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。 二、实验内容 (一)相等元素问题 1.问题描述 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题 输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。 3. 测试数据 输入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No (二) 整数集合分解 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n为偶数，且n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测 算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 实验二：回溯法VS分支定界法 一、问题分析 回溯法可以处理货郎担问题，分支定界法也可以处理货郎担问题，回溯法和分支定界法哪个算法处理货郎担问题效率更高呢？ 实现回溯法、分支定界法，以及不同的界值函数（课上讲过的或者自己新设计的），通过随机产生10个不同规模的算例（城市数量分别为10，20，40，80，100，120，160，180，200，500，或者其它规模），比较回溯法和分支定界法在相同界值函数下的执行效率。另外，分别比较回溯法和分支定界法在不同界值函数下的执行效率。 二、算法基本思想 1、回溯法 从初始状态出发，搜索其所能到达的所有“状态”， 当一条路走到尽头，再后退一步或若干步，从另外一种状态出发，继续搜索，直到所有的路径都搜索过。这种不断前进、不断回溯寻找解的方法叫回溯法。回溯法通常将问题解空间组织成“树”结构，采用系统的方法搜索解空间树，从而得到问题解。 搜索策略： 深度优先为主，也可以采用广度优先、函数优先、广度深度结合等。 避免无效搜索策略： 约束函数：在扩展结点处剪去不满足约束条件的子树 界限函数：在扩展结点处剪去得不到最优解的子树 2、分支限界法 分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。 分支界限法与回溯法思想对比： 求解目标：回溯法的可以用于求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标通常是找出满足约束条件的一个解或最优解。 搜索方式的不同：回溯法主要以深度优先的方式搜索解空间树，而分支限界法则 主要以广度优先或以最小耗费优先的方式搜索解空间树。 在分支限界法中，每个活结点只有一次机会成为扩展结点。一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 三、算法设计 1、回溯法 TSP问题的目的是得到一条路径，即一个解向量（X1,X2...Xn），为排列树问题。 对所有城市进行编号后，按大小顺序存储于数组path中，构造一个交换函数swap（）；对数组path进行遍历，判断当前城市与目标城市是否连通，若连通，通过swap函数对当前节点和目标城市进行交换，即树的节点拓展。若不连通则恢复，并进入下一次的循环，循环到叶子节点时，判断叶是否与初始节点相连，并计算代价cost是否小于当前最小代价bestc，若小于，则更新bestc，再返回上一节点，知道遍历完树中的所有节点。 2、分支限界法 因为问题是经典的TSP问题，所以确定问题的解空间树为排列树。 问题解的表示：可以将问题的解表示成一个n元式 [x1,x2,…,xn]。 使用优先级队列实现最小耗费优先求解。 界函数的确定：首先利用贪心的方法获得一个较优的上界。对于当前路径下的扩展的过程中，每一步需要存储的当前的结点的下界。其中的第二部分需要计算的是当前路径的起始结点以及终止结点各自与仍未访问过的结点中的结点只存存在的最小代价。 结点的扩展过程如下：根据优先级从队列中选取优先级最高的元素，当结点不是叶子结点的父节点时，扩展该结点的所有子节点，在扩展的过程中需要根据计算所得的下界与当前求解得到的最优解进行对比，如果下界大于当前的最优解则对相应的子节点时进行剪枝处理，否则扩展该子节点，将其加入到队列中。当当前所访问的结点为叶子结点的父节点时，判断当前费用+当前结点到叶子结点的费 算法设计与分析实验指导书 东北大学软件学院 2012年 目录 算法设计与分析 (1) 实验指导书 (1) 前言 (3) 实验要求 (4) 实验1 分治法的应用（2学时） (5) 1.实验目的 (5) 2.实验类型 (5) 3.预习要求 (5) 4.实验基本要求 (5) 5.实验基本步骤 (7) 实验2动态规划（2学时） (11) 1.实验目的 (11) 2.实验类型 (11) 3.预习要求 (11) 4.实验基本要求 (11) 5.实验基本步骤 (12) 实验3 回溯法（4学时） (16) 1.实验目的 (16) 2.实验类型 (16) 3.预习要求 (16) 4.实验基本要求 (16) 5.实验基本步骤 (17) 前言 《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。 要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。 通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。 希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。动态规划实验报告
算法设计与分析实验指导2014版
算法设计实验3
动态规划算法的应用实验报告
《算法设计与分析》实验指导
算法设计与分析实验报告
实验一 简单算法设计
动态规划算法实验
算法设计与实验报告讲解
算法设计与分析实验指导书样本
《算法设计与分析》实验一
算法设计实验报告一(简单算法设计)
算法设计与分析课程设计-实验指导书
南京邮电大学算法设计实验报告——动态规划法
算法与设计实验报告
算法设计与分析实验报告 统计数字问题
算法设计与分析实验报告
西北工业大学算法设计实验2
算法设计与分析实验指导书详解