遍历所有点回到原点数学建模

2022-10-21 00:01:33 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《遍历所有点回到原点数学建模》，欢迎阅读！
数学建模,遍历,原点,有点,回到

遍历所有点回到原点数学建模

数模问题梗概：

先给出一张地铁路线图，主人公小p希望能从某两个给定的地铁站之一出发，采取某种路径遍历该路线图上所有的地铁中转站，最终回到给定的两个起始站之一(同前所述)。现要求你在两种条件下分别给出对应的最优路径：

小p在一天内遍历完所有的中转站，并使得所用时间最少。小p将该遍历任务分配成五天完成，使得总用时最少。问题分析：

该问题中，首先可以应用图论的知识，将该路线图抽象成一张无向图，两地铁站间往来所用时间视为距离，保留中转站作为节点。构建出这样一张图以后，进行分析可以发现，给定两起始点事实上等价于一个起始点，因为我们总可以利用这两个起始点间的最短路径来优化方案。

因此，问题简化成从一个起始点出发，遍历所有点，再次回到起始点。那么很容易就联想到两个相关的数学模型：哈密顿回路和旅行商问题。简单分析后，可以发现与本题相关的显然是后者。

旅行商问题：

旅行推销员问题(Travelling salesman problem,TSP)是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

本题与上面的描述其实还存在着差异，也就是，在我们遍历所有地铁中转站时，其实是必然要重复经过中转站的。当然，这个问题解决起来也不困难，只需要我们先用Floyd算法对原图进行预处理即可。(为什么这样预处理就能解决问题呢？请自行思考)

接下来也即正式开始解决问题。

当图中顶点数时，该问题可以考虑用状态压缩DP来解决，时间复杂度为，在较短时间内就得到最优解。

本文来源：https://www.dywdw.cn/cc0a8c4da717866fb84ae45c3b3567ec102ddc31.html