下载文档原格式
TSP问题算法实验报告指导教师：****名：***学号：**********提交日期：2015年11月目录总述 (2)动态规划法 (3)算法问题分析 (3)算法设计 (3)实现代码 (3)输入输出截图 (6)OJ提交截图 (6)算法优化分析 (6)回溯法 (6)算法问题分析 (6)算法设计 (7)实现代码 (7)输入输出截图 (9)OJ提交截图 (9)算法优化分析 (10)分支限界法 (10)算法问题分析 (10)算法设计 (10)实现代码 (10)输入输出截图 (15)OJ提交截图 (15)算法优化分析 (15)总结 (16)总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。
动态规划法算法问题分析假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。
首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。
设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。
算法设计输入：图的代价矩阵mp[n][n]输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列（动态规划的边界问题）for(i=1;i<n;i++)dp[i][0]=mp[i][0]2.依次处理每个子集数组x[2^n-1]for(i=1;i<n;i++)if（子集x[j]中不包含i）对x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。
第1篇一、实验目的1. 理解动态规划的基本思想和方法。
2. 掌握动态规划在解决实际问题中的应用。
3. 提高编程能力和算法设计能力。
二、实验内容本次实验主要涉及以下四个问题：1. 斐波那契数列2. 最长公共子序列3. 最长递增子序列4. 零钱找零问题三、实验原理动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划的基本思想是将一个复杂问题分解成若干个相互重叠的子问题，然后按照子问题的顺序逐个求解，最后将这些子问题的解合并成原问题的解。
四、实验步骤及代码实现1. 斐波那契数列斐波那契数列是指这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, ...，其中每个数都是前两个数的和。
```cppinclude <iostream>using namespace std;int Fibonacci(int n) {if (n <= 1) {return 1;}int fib[n+1];fib[0] = 1;fib[1] = 1;for (int i = 2; i <= n; i++) {fib[i] = fib[i-1] + fib[i-2];}return fib[n];}int main() {int n;cout << "请输入斐波那契数列的项数：" << endl;cin >> n;cout << "斐波那契数列的第 " << n << " 项为：" << Fibonacci(n) << endl;return 0;}```2. 最长公共子序列给定两个序列A和B，找出它们的公共子序列中长度最长的序列。
```cppinclude <iostream>using namespace std;int LCSLength(string X, string Y) {int m = X.length();int n = Y.length();int L[m+1][n+1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)L[i][j] = 0;else if (X[i-1] == Y[j-1])L[i][j] = L[i-1][j-1] + 1;elseL[i][j] = max(L[i-1][j], L[i][j-1]);}}return L[m][n];}int main() {string X = "AGGTAB";string Y = "GXTXAYB";cout << "最长公共子序列长度为：" << LCSLength(X, Y) << endl; return 0;}```3. 最长递增子序列给定一个序列，找出它的最长递增子序列。
动态规划实验报告动态规划实验报告一、引言动态规划是一种常用的算法设计方法，广泛应用于计算机科学和运筹学等领域。
本实验旨在通过实际案例，探究动态规划算法的原理和应用。
二、实验背景动态规划算法是一种通过将问题分解为子问题，并存储子问题的解来解决复杂问题的方法。
它通常适用于具有重叠子问题和最优子结构性质的问题。
三、实验目的1. 理解动态规划算法的基本原理；2. 掌握动态规划算法的实现方法；3. 分析动态规划算法在实际问题中的应用。
四、实验过程本实验选择了经典的背包问题作为案例进行分析。
背包问题是一个组合优化问题，给定一个背包的容量和一系列物品的重量和价值，如何选择物品放入背包，使得背包中物品的总价值最大化。
1. 确定状态在动态规划算法中，状态是问题的关键。
对于背包问题，我们可以将状态定义为背包的容量和可选择的物品。
2. 确定状态转移方程状态转移方程是动态规划算法的核心。
对于背包问题，我们可以定义一个二维数组dp[i][j]，表示在背包容量为j的情况下，前i个物品的最大总价值。
则状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
3. 初始化边界条件在动态规划算法中，边界条件是必不可少的。
对于背包问题，边界条件可以定义为当背包容量为0时，无论物品如何选择，总价值都为0。
4. 递推求解根据状态转移方程和边界条件，我们可以通过递推的方式求解问题。
具体步骤如下：- 初始化dp数组；- 逐行逐列计算dp数组的值，直到得到最终结果。
五、实验结果与分析通过实验，我们得到了背包问题的最优解。
同时，我们还可以通过分析dp数组的取值，了解到每个状态下的最优选择。
这为我们提供了在实际问题中应用动态规划算法的思路。
六、实验总结本实验通过对动态规划算法的实际案例进行分析，深入理解了动态规划算法的原理和应用。
实验报告（2013/2014学年第一学期）课程名称算法分析与设计实验名称密码算法实验时间2014 年 5 月23 日指导单位计算机学院软件工程系指导教师张怡婷学生姓名班级学号B******** 学院(系) 软件工程专业软件工程实验报告三、实验原理及内容（包括操作过程、结果分析等）实验步骤1、RSA 算法是由麻省理工学院的Ron Rivest,Adi Shamir 和Len Adleman 于1977 年研制并于1978 年首次发表的一种算法，是第一个能同时用于加密和数字签名的算法，且易于理解和操作，因此作为一种通用公开密钥加密方式而受到推崇。
RSA 是一种分组密码，其中明文和密文都是小于某个n 的从0 到n-1 的整数，则分组的二进制值长度必须小于或等于log2n。
若以M 表示明文分组，而C 表示密文分组，则加密和解密的过程如下：C=Me mod nM=Cd mod n=(Me)d mod n=Med mod n发送方和接受方都必须知道n 的值。
发送方知道 e 的值，而只有接受方知道d 的值。
因此这是一种公开密钥为{e,n}，且私有密钥为{d,n}的公开密钥加密算法。
此时算法要能够满足公开密钥加密的要求，则必须满足以下条件：（1）有可能找到e、d、n 的值，使得对所有M<n 有Med=M mod n。
（2）对于所有M<n 的值，要计算Me和Cd 相对来说是简单的。
（3）在给定e 和n 时，判断出 d 是不可行的。
2、重点考虑第一个条件：由Euler 定理的一个推论：给定两个素数p和q以及两个整数n 和m，使得n=pq 而且0<m<n，并且对于任意整数k，下列关系成立：mkΦ(n)+1=mk(p-1)(q-1)+1≡m mod n其中Φ(n)是欧拉函数，也就是不超过n 且与n 互素的整数个数。
对于素数p 和q，有Φ(pq)=(p-1)(q-1)。
因此得到需要的关系：ed=kΦ(n)+1，等价于: ed≡1 mod Φ(n)d≡e-1 mod Φ(n)也就是说：d 和 e 是以Φ(n)为模的乘法逆元。
动态规划法动态规划法（Dynamic Programming）是一种常用的算法思想，主要用于解决具有重叠子问题性质和最优子结构性质的问题。
动态规划法通过把问题分解为更小的子问题，并将子问题的解存储起来，以避免重复计算，从而提高了算法的效率。
动态规划法有两个核心概念：状态和状态转移方程。
在动态规划过程中，我们需要定义状态，即问题的子问题解，以及状态之间的关系，即状态转移方程。
动态规划法的一般步骤如下：1. 定义问题的子问题：将问题划分为更小的子问题，并明确子问题的解是什么。
2. 定义状态：将问题的子问题解抽象为状态，即用一个变量或者数组表示子问题的解。
3. 定义状态转移方程：根据子问题的关系，定义状态之间的转移方程，即如何根据已知的子问题解计算出更大的问题的解。
4. 缓存子问题解：为了避免重复计算，我们需要将已经计算过的子问题解存储起来，以便后续使用。
5. 递推计算：通过状态转移方程和缓存的子问题解，逐步计算出更大的问题的解，直到计算出最终的问题解。
动态规划法的关键在于找到正确的状态转移方程和合理的存储子问题解的方式。
有些问题的状态转移方程比较容易找到，比如斐波那契数列，每个数都是前两个数的和；而有些问题的状态转移方程可能比较复杂，需要通过观察问题的特点和具体分析来确定。
动态规划法的时间复杂度通常为O(n)，其中n 表示问题规模。
由于利用了子问题的解，避免了重复计算，因此动态规划法相对于暴力求解法能够大大提高算法的效率。
但是，动态规划法的空间复杂度通常较高，需要存储大量的子问题解，因此在实际应用中需要权衡时间和空间的消耗。
总的来说，动态规划法是一种非常灵活且强大的算法思想，能够解决许多复杂的问题，特别适用于具有重叠子问题性质和最优子结构性质的问题。
通过正确定义状态和状态转移方程，并结合缓存子问题解和递推计算，我们可以高效地求解这类问题，提高算法的效率。
第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。
通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。
二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法：顺序查找、二分查找。
3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。
4. 动态规划算法：0-1背包问题。
三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。
2. 查找算法：查找算法用于在数据集中查找特定的元素。
常见的查找算法包括顺序查找和二分查找。
3. 图算法：图算法用于处理图结构的数据。
常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。
4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。
常见的动态规划算法包括0-1背包问题。
四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。
（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。
（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。
（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。
（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。
（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。
2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。
现代控制理论学习报告动态规划法1、概述：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
本文简要介绍了动态规划的基本概念，并通过一个实例说明其在现实生活中的应用。
2、基本思想：动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解。
每一个解都对应于一个值，我们希望找到具有最优值的解。
其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。
若存在若干个取最优值的解的话，它只取其中的一个。
但是首先要保证该问题的无后效性,即无论当前取哪个解,对后面的子问题都没有影响.在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
实验二动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z 是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
三．(1)实验源代码://最长公共子序问题://问题描述: 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，//是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
//例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
//给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z 是序列X和Y的公共子序列。
//给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
#include<bits/stdc++.h>using namespace std;#define max 1000//注意：这里使用的char数组，可以按字符输出，若改为string类型，//执行printf("%c",A[m-1])就会报错;char A[100],B[100]; //输入的两个串a和b//这里定义全局变量可以不赋值0，因为全局变量自动赋值0;int c[max][max]; //记录最长公共子序的长度；int b[max][max]; //记录状态号;void LCS(int m,int n){if(m==0||n==0){return;else if(b[m][n]==1){LCS(m-1,n-1);printf("%c",A[m-1]);}else if(b[m][n]==2){m=m-1;LCS(m,n);}else if(b[m][n]==3){n=n-1;LCS(m,n);}}void LCS_length(int m,int n){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}{printf("请输入两个待测的字符串:\n");scanf("%s",&A);scanf("%s",&B);int m=strlen(A); //m为A串长度；int n=strlen(B); //n为B串长度;LCS_length(m,n);printf("其最长公共子序的长度为:%d\n",c[m][n]);printf("其最长公共子序为:");LCS(m,n);return 0;}(2)运行结果为:(3)算法思路:最长公共子序列的结构有如下表示：设序列X=<x1, x2, …, x m>和Y=<y1, y2, …, y n>的一个最长公共子序列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且z k≠x m ，则Z是X m-1和Y的最长公共子序列；3.若x m≠y n且z k≠y n，则Z是X和Y n-1的最长公共子序列。
