技术标签： tsp问题动态规划python
Traveling Salesman Problem
Description： Time Limit: 4sec Memory Limit:256MB
有编号1到N的N个城市，问从1号城市出发，遍历完所有的城市并最后停留在N号城市的最短路径长度。
Input：
第一行整数 T ：T组数据 (T<=20)
每个case 读入一个N( 2 <= N <= 20)，接着输入N行，第i行有两个整数 xi , yi 表示第 i 个城市坐标轴上的坐标 。
Output：
每个case输出一个浮点数表示最短路径。四舍五入保留两位小数。
Sample Input：
1 4 0 0 1 0 1 1 0 1
Sample Output：
3.41
经典难题！数据开到这么小就知道没有那么简单的复杂度了，一般的算法，即爆搜，复杂度为 o( n! ) ，我们这里采用的动态规划算法，
算法复杂度已经从阶乘级降到了o( ( n^2 )*( 2^n ) ) (看起来也是相当恐怖的，不过像这种经典难题这种复杂度对我来说已经不错了)。
开始说说思路，一开始马上想到的必然是搜索，搜索必然超时，于是某大神直接告诉我——记忆化搜索，记忆化搜索能做的动规就能做，写递归太麻烦了于是动规！
题目中起点终点确定，我们可以考虑用一个二维dp数组来保存一个状态——dp[i]{V}表示从结点0到结点 i 途经V中所有节点的最短路径长(这里的V是一个集合)
于是状态转移方程可以为：dp[i]{V}=min( dp[i]{V} , dist[i][j]+dp[j]{V-{j}} ) (j 属于 V)
大思路定好了，我们来考虑细节部分，主要有以下部分：
1)建图等等：结构体point，距离函数dist；
2)集合V的表示：二进制数，即010表示三个数的集合第二个有，其余无；
3)dp过程的范围：1 ~ n-1 (最大可能为 1 ~ 18 )；
于是我们可以敲代码啦！
#include
const double INF=10e7;
using namespace std;
int T,n,cnt;
double a[25][25],dp[25][1100000];
struct point{//结点结构体
int x,y;
}pt[25];
double d(point a,point b){//结点间距离
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
scanf("%d",&T);
while(T--)
{
cnt=1;
scanf("%d",&n);
for(int i=2;i
for(int i=0;i
scanf("%d %d",&pt[i].x,&pt[i].y);
for(int i=0;i
for(int j=0;j
a[i][j]=d(pt[i],pt[j]);
for(int i=0;i
for(int j=0;j
dp[i][j]=INF;
for(int i=0;i
dp[i][0]=a[i][0];
for(int i=1;i
for(int j=1;j
{
for(int k=1;k
{
if((1<
dp[j][i]=min(dp[j][i],a[j][k]+dp[k][i-(1<
}
}
double ans=INF;
for(int i=1;i
ans=min(ans,dp[i][cnt-1]+a[i][n-1]);
printf("%.2lf\n",ans);
}
return 0;
}
之前动态规划也是做了不少的基础例题，这道题算是动态规划的第一次成功应用，还是蛮开心的，软创得加油啊！
文章浏览阅读117次。神经网络初探——读《深度学习的数学》总结 学习是一个系统通过某种过程或者方式提升自身的某个或某些性能的过程，它本身包含的是一种自动化和可控化的含义。那么如何能让不具备智能的机器去学习呢？在模拟大脑神经元的工作原理后，看来我们已经找到了通往机器学习的一种方法，它叫做神经网络。神经网络是一种看似不可理解的复杂学习方法，这里包含着许多数学的知识。在阅读《深度学习的数学》一书之后，我想，我对神经网..._神经网络初探
文章浏览阅读3.5k次，点赞5次，收藏13次。音频分离Spleeter的安装1.环境依赖及建立（需要已安装anaconda）1.0 项目源地址（github地址）1.1 创建虚拟环境1.2 激活虚拟环境1.3 conda 安装spleeter1.4 下载一个示例音乐1.5 将该音乐分离为两部分1.5.1 报错：No module named numba.decorators1.5.2 解决方案：1.6 下载分类模型1.6.1报错ValueError:Can't load save_path when it is None.1.6.2 解决方案：1.6._2stems.tar.gz
文章浏览阅读64次。朋友曾经给我推荐了一个有关代码优化的pdf文档《让你的软件飞起来》，看完之后，感受颇深。为了推广其，同时也为了自己加深印象，故将其总结为word文档。下面就是其的详细内容总结，希望能于己于人都有所帮助。速度取决于算法同样的事情，方法不一样，效果也不一样。比如，汽车引擎，可以让你的速度超越马车，却无法超越音速；涡轮引擎，可以轻松超越音障，却无法飞出地球；如果有火箭发动机，就可以到达火..._bao.yuv
文章浏览阅读2.5k次，点赞3次，收藏33次。文章目录前言一、载具设置二、电机接线三、PWM输出设置四、航点设置前言一个人可以走的更快，一群人才能走的更远，交流学习加qq:2096723956更多保姆级PX4+ROS学习视频：https://b23.tv/ZeUDKqy分享知识，传递正能量，如有疏漏或不当之处，恳请指出．PX4固件版本：1.10.0硬件:淘宝竞速船或者打窝船实验录屏https://www.bilibili.com/video/BV1wA411c7p3?spm_id_from=333.999.0.0一、载具设置单电机_在px4固体中如何设置差速船
文章浏览阅读370次。每天都有大量的快递单号需要查询，如果一个个手动查询，不仅费时费力，还容易出错。为了解决这个问题，我们教您如何批量查询快递单号，并将快递物流信息进行备份并共享，实现高效管理。弹出一个对话框，文件名和保存类型不变，直接点“保存”，会提示备份成功，那么这个数据库就备份在电脑上了，也可以用第三方工具发送到其他电脑上。第四步，查询速度很快，我们就可以在主页面看到该批单号的运件信息了，比如：发出时间，状态，最后更新的物流时间，等等。第二步，在弹出来的文件框里，将需要查询的德邦快递单号都一一导入，并点击保存。_批量快递查询
文章浏览阅读7.7k次，点赞6次，收藏61次。敏捷开发（scrum）是一种软件开发的流程，强调快速反应、快速迭代、价值驱动。Scrum的英文意思是橄榄球运动的一个专业术语，表示“争球”的动作；运用该流程，你就能看到你团队高效的工作。一、四大价值观（特点）敏捷开发的特点就是下面4句话：「个体与交互」胜过「过程与工具」「可以工作的软件」胜过「面面俱到的文挡」「客户协作」胜过「合同谈判」「响应变化」胜过「遵循计划」说明：（1）敏捷开发（scrum）适用于竞争激烈，快速变化的市场。 敏捷的客户协作观念，快速迭代能帮助团队以最小成本，最快速_敏捷开发
文章浏览阅读2k次。本篇推文共计2000个字，阅读时间约3分钟。华为云—华为公司倾力打造的云战略品牌，2011年成立，致力于为全球客户提供领先的公有云服务，包含弹性云服务器、云数据库、云安全等云计算服务，软..._modelarts yolo weights 文件 bbs 华为云
文章浏览阅读2.2k次，点赞3次，收藏13次。802.11 Wi-Fi_wifi dfs
文章浏览阅读249次。pcie接口sata接口pcie总线pcie总线pcie控制器sata控制器nvme设备sata设备nvme协议ahci协议m-key接口b-key接口_rk3568 sata
文章浏览阅读1.3k次。循环队列可以很好的解决假溢出问题,不同于普通队列,在循环队列中,需将rear与front初始值都设置为0,rear指针指向队列中最后一个元素的下一个位置,也正因如此,数组是否存满的判定条件也应做出改变,在普通队列中,front==maxSize-1,即可认为数组已满,但是在循环队列中,由于在存放完数组最后一个有效位置后可以继续像数组中的0号位置进行存储,所以判断满的条件也会发生改变,—(rear+1)%maxSize = front.可以举个例子方便理解,假设一maxSize=5的数组,那么其有0 1_但是要利用循环队列的时候,处理假溢出,要使q.front=0的时候,为什么q.rear要加
文章浏览阅读4.8k次。linux CentOS 7下载步骤_centos7下载
文章浏览阅读464次。布局管理器提供相关的类对界面组件进行布局管理能够自动排布窗口中的界面组件窗口变化后自动更新界面组件的大小QLayoutQLayout 是Qt 中布局管理器的抽象基类通过继承QLayout实现了功能各异且互补的布局管理器Qt中可以根据需要自定义布局管理器布局管理器不是界面部件，而是界面部件的定位策略QBoxLayout 布局管理器以水平或者垂直的方式管理界面组件水平：QHBoxLayout 水平布局管理器垂直：QVBoxLayout 垂直布局管理器sizePolicy:QSize_qt layout可以嵌套layout吗