实验九 TSP问题

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

       

所在院系

计算机与信息工程学院

学生学号

学生姓名

年级专业

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

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

  1. 数组长度为1000时:
  2. 数组长度为5000时:

  1. 数组长度为20000000(两千万)时:

四、实验小结

综上所属,时间性能比较:动态规划算法>分治算法>蛮力算法

原因分析:动态规划算法的时间复杂度为O(n),分治算法的时间复杂度为O(nlogn),而蛮力算法的时间复杂度为O(2n),因此随着问题规模的增加,最终的运行时间总会呈现:动态规划时间最短,分治算法的时间次之,蛮力算法的时间最长。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3347.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

html+css制作

<!DOCTYPE html> <html><head><meta charset"utf-8"><title>校园官网</title><style type"text/css">*{padding: 0;margin: 0;}#logo{width:30%;float: left;}.nav{width: 100%;height: 100px;background-color…

mybatis如何解析常用的标签

通过这三行就解析好了一个mybatis配置文件&#xff0c;我们看看如何工作的&#xff1f; String resource "mybatis-config.xml"; Reader reader Resources.getResourceAsReader(resource); SqlSessionFactory sqlSessionFactory new SqlSessionFactoryBuilder().b…

【进阶C语言】qsort库函数(详解)

qsort库函数1. qsort到底是什么&#xff1f;2. qsort库函数的功能3. qosrt函数详解4. 冒泡排序的实现5. qsort库函数如何实现冒泡排序6. qsort库函数排序结构体数据7. 使用冒泡排序的思想来实现类似于qsort1. qsort到底是什么&#xff1f; qsort是C语言库函数里面的一种&#x…

【Flutter·学习实践·配置】认识配置文件pubspec.yaml

目录 简介 pubspec.yaml 添加Pub仓库 其他依赖方式 依赖本地包 依赖Git 简介 简单说就是包管理工具&#xff0c;类似于Android 提供了 Gradle 来管理依赖&#xff0c;iOS 用 Cocoapods 或 Carthage 来管理依赖&#xff0c;Node 中通过 npm 等。 让我们能很好的管理第三…

固定优先级仲裁器设计

前言仲裁器Arbiter是数字设计中非常常见的模块&#xff0c;应用也非常广泛。定义就是当有两个或两个以上的模块需要占用同一个资源的时候&#xff0c;我们需要由仲裁器arbiter来决定哪一个模块来占有这个资源。一般来说&#xff0c;提出占有资源的模块要产生一个请求(request)&…

电脑硬盘文件数据误删除/格式化为什么可以恢复? 怎么恢复?谈谈文件删除与恢复背后的原理

Hello 大家好&#xff0c; 我是元存储~ 主页&#xff1a;元存储的博客_CSDN博客 1. 硬盘数据丢失场景 我们在每天办公还是记录数据的时候&#xff0c;文件存储大多数都是通过硬盘进行存储的&#xff0c;因此&#xff0c;使用多了&#xff0c;各种问题就会出现&#xff0c;比如…

【C++初阶】五、内存管理

文章目录1. C/C内存分布2. C语言中动态内存管理3. C中动态内存管理方式new/delete操作内置类型new和delete操作自定义类型4.C和C在内存申请失败时处理方式的区别5. operator new与operator delete函数6. new和delete的实现原理内置类型自定义类型7. 定位new表达式(placement-ne…

【 Spark编程基础 】实验1

文章目录第1部分&#xff1a;虚拟机的准备工作1.1 下载安装虚拟机1.2 修改主机名1.3 主机ip映射安装SSH服务端SFTP连接&#xff0c;传输安装包安装Java环境第2部分 Hadoop安装2.1 安装Hadoop第3部分 配置集群环境第4部分 Spark安装第1部分&#xff1a;虚拟机的准备工作 1.1 下…

【设计模式-工厂方法】想象力和创造力:你考虑过自动化实现工厂吗?

无限思维-想象力和创造力&#xff1a;自动化实现工厂方法前言一、《大话设计模式》对应的Java版本工厂方法类图先行&#xff1a;代码实现&#xff1a;思考升华&#xff1a;二、想象力&#xff1a;创新型思维解决思路战略上&#xff1a;以无限思维的角度去想问题&#xff1a;部署…

SpringBoot整合数据可视化大屏使用

1 前言 DataV数据可视化是使用可视化应用的方式来分析并展示庞杂数据的产品。DataV旨让更多的人看到数据可视化的魅力,帮助非专业的工程师通过图形化的界面轻松搭建专业水准的可视化应用,满足您会议展览、业务监控、风险预警、地理信息分析等多种业务的展示需求, 访问地址:h…

文件上传的多种利用方式

文件上传的多种利用方式 文件上传漏洞除了可以通过绕过检测进行webshell的上传之外&#xff0c;还有多种其它的漏洞可以进行测试。 XSS漏洞 文件名造成的XSS 当上传任何文件时&#xff0c;文件名肯定是会反显示在网页上&#xff0c;可以使用 XSS Payload做文件名尝试将其上传到…

upload—labs(9-12)

pass9直接查看的源码&#xff0c;得知是黑名单过滤&#xff0c;而且过滤也都很全通过查看wp&#xff0c;得知我们可以使用. .(点空格点)进行绕过利用bp抓包进行更改trim删除文件名末尾的点&#xff0c;得到shell.php.空格&#xff0c;然后进行首尾去空得到shell.php.,黑名单过滤…

Java并发高频面试题

分享50道Java并发高频面试题。 线程池 线程池&#xff1a;一个管理线程的池子。 为什么平时都是使用线程池创建线程&#xff0c;直接new一个线程不好吗&#xff1f; 嗯&#xff0c;手动创建线程有两个缺点 不受控风险频繁创建开销大 为什么不受控&#xff1f; 系统资源有…

【机器学习基础 3】 sklearn库

目录 一、sklearn库简介 二、sklearn库安装 三、关于机器学习 四、sklearn库在机器学习中的应用 1、数据预处理 2、特征提取 3、模型选择与评估 五、常用的sklearn函数 1、数据集划分 2、特征选择 3、特征缩放 4、模型训练 5、模型预测 一、sklearn库简介 Scikit-l…

基于卷积神经网络进行股价预测(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f468;‍&#x1f4bb;4 Matlab代码 &#x1f4a5;1 概述 CNN是一种人工神经网络&#xff0c;CNN的结构可以分为3层&#xff1a; 卷积层(Convolutional Layer) - 主要作用是提取特征。 …

C语言基础——流程控制语句

文章目录一、流程控制语句 -- 控制程序的运行过程 9条&#xff08;一&#xff09;、条件选择流程控制语句&#xff1a;if语句if……else……语句if……else if……语句switch语句&#xff08;二&#xff09;、循环流程控制语句&#xff1a;for语句while语句do while……语句co…

Linux学习之端口、网络协议及查看端口占用情况

端口&#xff1a;设备与外界通讯交流的出口 网络协议&#xff1a;   网络协议是指计算机通信网络中两台计算机之间进行通信所必须共同遵守的规定或规则。 HTTP协议&#xff1a;   HTTP协议&#xff08;超文本传输协议&#xff09;是一种网络通信协议&#xff0c;它允许将超…

Mac和Linux安装Mongodb教程

Mac教程 在mongodb的官网中有mac环境的安装配置说明 在mac上安装mongodb有两种方式&#xff1a; &#xff08;1&#xff09;使用Homebrew来安装&#xff0c;如果电脑中有Homebrew&#xff0c;安装起来就比较简单&#xff0c;如果没有可以安装一个&#xff0c;以后安装其他的…

【C++学习】多态

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《C学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 多态&#x1f355;多态&#x1f35f;构成多态的条件&#x1f35f;C11 final override&#x1f35f;重…

thinkphp+vue水果购物商城网站

需要解决的主要问题&#xff1a; 1、网页编程环境和工具。 2、后台数据库的管理。 3、网站的基本功能建设。 4、对比实际应用中的购物网站的功能和运作流程&#xff0c;完善程序功能。 水果购物商城系统的主要使用者分为管理员&#xff1b;个人中心、用户管理、水果分类管理…