《算法设计与分析》实验报告

目  录

实验九-1：TSP问题

一、实验目的与要求

二、实验环境

三、实验步骤与分析

四、实验小结

实验九-2 最大子段和

一、实验目的与要求

二、实验环境

三、实验步骤与分析

四、实验小结

实验九-1：TSP问题 

一、实验目的与要求 

二、实验环境

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!)的排列问题转化为组合问题，从而降低了算法的时间复杂度，但仍需要指数时间。

实验九-2 最大子段和

一、实验目的与要求

给定由n个整数(可能有负整数)组成的序列(a1, a2, .. an),求该序列形如子段和的最大值

分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法,并设测试数据，比较不同算法的时间性能。

二、实验环境

DEVC++

三、实验步骤与分析

源代码：

#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)//区间的形式采用左闭右开
{//首先处理递归基，也就是数组中只包含一个元素的情况，这时根据最大子段和的定义，如果该元素是正数则结果为其自身，否则结果为0if (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;
}