《算法设计与分析》实验报告
| 所在院系 | 计算机与信息工程学院 |
| 学生学号 | |
| 学生姓名 | |
| 年级专业 | 2020级计算机科学与技术 |
| 授课教师 | 彭绪富 |
| 学 期 | 2022-2023学年第一学期 |
| 提交时间 | 2022年10月26日 |
目 录
实验九-1：TSP问题
一、实验目的与要求
二、实验环境
三、实验步骤与分析
四、实验小结
实验九-2 最大子段和
一、实验目的与要求
二、实验环境
三、实验步骤与分析
四、实验小结
实验九-1：TSP问题
一、实验目的与要求
TSP问题是指旅行家要旅行n个城市，要求各个城市经历且经历一次，然后回到出发城市，并要求所走的路程最短。
二、实验环境
Devc++
三、实验步骤与分析
假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。
- 当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的 城市3->城市0(0为起点城市)。此时d(i, V’)=Cis(就是 城市i 到 城市s 的距离)
②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个，并求出最优解。d(i, V’)=min{Cik + d(k, V’-{k})}注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。
综上所述，TSP问题的动态规划方程就出来了：
图3-1
现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)
图3-2
①我们要求的最终结果是d(0,{1,2,3}),它表示，从城市0开始，经过{1,2,3}之中的城市并且只有一次，求出最短路径.
②d(0,{1,2,3})是不能一下子求出来的，那么他的值是怎么得出的呢？看上图的第二层，第二层表明了d(0,{1,2,3})所需依赖的值。那么得出：
d(0,{1,2,3})=min {
C01+d(1,{2,3})
C02+d{2,{1,3}}
C03+d{3,{1,2}}
}
③d(1,{2,3})，d(2,{1,3})，d(3,{1,2})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3})
d(1,{2,3})=min{
C12+d(2,{3})
C13+d(3,{2})
}
d(2,{1,3})，d(3,{1,2})同样需要这么求。
④按照上面的思路，只有最后一层的，当当V’为空集时，Cis的值才可以求，它的值是直接从图3-3里求出的。
图3-3
将d(i, V’)转换成二维表，d[i][j]如图3-4
图3-4
伪代码及代码测试：
四、实验小结
算法需要对顶点集合{1， 2, .，.n-1)的每一个子集都进行操作,因此时复杂度为0(2^n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂度是(n!)的排列问题转化为组合问题，从而降低了算法的时间复杂度，但仍需要指数时间。
给定由n个整数(可能有负整数)组成的序列(a1, a2, .. an),求该序列形如
子段和的最大值
分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法,并设测试数据，比较不同算法的时间性能。
源代码：
#include<iostream>
#include<ctime>
using namespace std;
const int length = 1000;
//用于求三个数中最大值的辅助函数，由于内容少，定义为内联函数以提高效率
inline int max(const int& x1, const int& x2, const int& x3)
{
if (x1 >= x2 && x1 >= x3)
{
return x1;
}
else if (x2 >= x1 && x2 >= x3)
{
return x2;
}
else return x3;
}
//蛮力法求解，即求出数组的所有子段并分别计算子段和，从子段和中选择最大值
int BruteForce(const int* a, const int& n)
{
int max = 0;
for (int length = 1; length <= n; length++)//对于每一种可能长度都需要求出子段和
{
for (int i = 0; i <= n - length; i++)//对于子段长度相同的不同子段也需要分别求出子段和
{
int sum = 0;
for (int j = i; j < i + length; j++)
{
sum += a[j];
}
if (sum > max)//每求出一个子段和就与当前最大子段和进行比较，如果新求出的子段和更大则更新当前最大子段和
{
max = sum;
}
}
}
return max;//返回求出的所有子段和中的最大值
}
//分治法求解，对于任意一个数组，其子段和无非可以分为三种情况：最大和对应子段在数组的左半段、最大和对应的子段在数组的右半段、最大和对应的子段跨越了数组的中点
int DivideConquer(const int* a, const int& left, const int& right)//区间的形式采用左闭右开
{
//首先处理递归基，也就是数组中只包含一个元素的情况，这时根据最大子段和的定义，如果该元素是正数则结果为其自身，否则结果为0
if (right - left <= 1)
{
if (a[left] > 0)
{
return a[left];
}
else return 0;
}
int middle = (left + right) >> 1;//首先找到数组的中点，方便后续处理
int leftMax = 0, rightMax = 0;
int leftSum = 0, rightSum = 0;
//分别以数组的中点为基准，分别找出其向左和向右方向的最大子段长度
for (int i = middle - 1; i >= left; i--)
{
leftSum += a[i];
if (leftSum >= leftMax)
leftMax = leftSum;
}
for (int i = middle; i < right; i++)
{
rightSum += a[i];
if (rightSum >= rightMax)
rightMax = rightSum;
}
//从三种情况中选择最大的一种，三种情况分别是最大和子段在数组左半段，最大和子段在数组右半段，最大和数组跨越了数组中点（此处使用了辅助函数max用于求出三个数中的最大值）
return max(DivideConquer(a, left, middle), DivideConquer(a, middle, right), leftMax + rightMax);
}
//动态规划法求解，使用一个数组temp，temp[i]可以理解为到第i号元素为止最大子段和的长度
int DynamicProgram(int* a,const int& n)
{
int* temp = new int[n];
temp[0] = a[0] > 0 ? a[0] : 0;
for (int i = 1; i < n; i++)
{
temp[i] = temp[i - 1] > 0 ? (temp[i - 1] + a[i]) : a[i];
}
int max = 0;
for (int i = 0; i < n; i++)
{
if (temp[i] > max)
max = temp[i];
}
return max;
}
int main(void)
{
//首先创建一个指定长度的整数数组
int* array = new int[length];
int result;
clock_t start, end;
double TimeGap;
srand(1);//固定随机数种子，方便后续多次调试
for (int i = 0; i < length; i++)
{
array[i] = rand() % 21 - 10;//采用随机数的方法给数组元素赋值（正数与负数出现的概率均等）
}
//首先采用蛮力法求解该问题并计算运行时间
start = clock();
result = BruteForce(array, length);
end = clock();
TimeGap = double((end - start) / CLK_TCK);
cout << "蛮力算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;
//接着采用分治法求解该问题并计算运行时间
start = clock();
result = DivideConquer(array, 0, length);
end = clock();
TimeGap = double((end - start) / CLK_TCK);
cout << "分治算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;
//最后采用动态规划求解该问题并计算运行时间
start = clock();
result = DynamicProgram(array, length);
end = clock();
TimeGap = double((end - start) / CLK_TCK);
cout << "动态规划算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;
delete[]array;
return 0;
}- 数组长度为1000时：
- 数组长度为5000时：
- 数组长度为20000000（两千万）时：
原因分析：动态规划算法的时间复杂度为O(n)，分治算法的时间复杂度为O(nlogn)，而蛮力算法的时间复杂度为O(2n)，因此随着问题规模的增加，最终的运行时间总会呈现：动态规划时间最短，分治算法的时间次之，蛮力算法的时间最长。
