状态压缩动态规划:最短Hamilton路径

2023-12-12 12:44

本文主要是介绍状态压缩动态规划:最短Hamilton路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

[状态压缩动态规划] 最短Hamilton路径

题目描述

给定一张 n n n 个点的带权无向图,点从 0 0 0~ n − 1 n-1 n1 标号,求起点 0 0 0 到终点 n − 1 n-1 n1 的最短 H a m i l t o n Hamilton Hamilton路径。 H a m i l t o n Hamilton Hamilton路径的定义是从 0 0 0 n − 1 n-1 n1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n n n

接下来 n n n行每行 n n n个整数,其中第 i i i行第 j j j个整数表示点 i i i j j j的距离(记为 a [ i , j ] a[i,j] a[i,j])。

对于任意的 x x x, y y y, z z z,数据保证 a [ x , x ] = 0 a[x,x]=0 a[x,x]=0 a [ x , y ] = a [ y , x ] a[x,y]=a[y,x] a[x,y]=a[y,x] 并且 a [ x , y ] + a [ y , z ] > = a [ x , z ] a[x,y]+a[y,z]>=a[x,z] a[x,y]+a[y,z]>=a[x,z]

输出格式

输出一个整数,表示最短 H a m i l t o n Hamilton Hamilton路径的长度。

样例 #1

样例输入 #1

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5

样例输出 #1

18

提示

【数据范围】

1 ≤ n ≤ 20 1≤n≤20 1n20

0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0a[i,j]107

算法思想

根据题目描述, H a m i l t o n Hamilton Hamilton路径的定义是从 0 0 0 n − 1 n-1 n1 不重不漏地经过每个点恰好一次,求最短 H a m i l t o n Hamilton Hamilton路径的长度。

从数据范围来看, 1 ≤ n ≤ 20 1≤n≤20 1n20,点非常少,可以考虑使用状态压缩的方式表示每个点是否经过。例如,有 5 5 5个点,经过了点 0 、 2 、 3 0、2、3 023,其状态的二进制形式为 ( 01101 ) 2 (01101)_2 (01101)2

状态表示

f [ s t a t e ] [ i ] f[state][i] f[state][i]表示从起点走到 i i i点时,并且经过点的状态为 s t a t e state state的情况下,最短 H a m i l t o n Hamilton Hamilton路径的长度。

最终结果为 f [ 2 n − 1 ] [ n − 1 ] f[2^n-1][n-1] f[2n1][n1]

状态计算

计算 f [ s t a t e ] [ i ] f[state][i] f[state][i]可以根据最后一步走到 i i i点的情况分成若干类。

不妨设上一点为 j j j,那么 f [ s t a t e ] [ i ] f[state][i] f[state][i]应该为不包含 i i i的状态走到 j j j点的最短路径长度,再加上 a [ j ] [ i ] a[j][i] a[j][i],即
f [ s t a t e ] [ i ] = m i n { f [ s t a t e − ( 1 < < i ) ] [ j ] + a [ j ] [ i ] } f[state][i]=min\{f[state-(1<<i)][j]+a[j][i]\} f[state][i]=min{f[state(1<<i)][j]+a[j][i]}

注意:计算 f [ s t a t e ] [ i ] f[state][i] f[state][i]前提是状态 s t a t e state state已经包含了 i i i点和 j j j点。

初始状态

  • 题目中求最短路径长度,状态应初始化为无穷大。
  • 0 0 0点出发,因此 f [ 1 ] [ 0 ] = 0 f[1][0]=0 f[1][0]=0

时间复杂度

  • 状态数为 2 n × n 2^n\times n 2n×n
  • 状态计算过程中要枚举所有能到达 i i i的点 j j j,时间复杂度为 O ( n ) O(n) O(n)

总的时间复杂度为 O ( n 2 × 2 n ) = 400 × 1048576 = 419 , 430 , 400 O(n^2\times2^n)=400\times 1048576=419,430,400 O(n2×2n)=400×1048576=419,430,400

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << 20, INF = 0x3f3f3f3f;
int a[N][N], f[M][N];
int main()
{int n;cin >> n;for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)cin >> a[i][j];//初始状态memset(f, 0x3f, sizeof f);       f[1][0] = 0;//状态计算for(int state = 0; state < 1 << n; state ++){for(int i = 0; i < n; i ++){//状态中包含i点if(state >> i & 1){//枚举i的上一点jfor(int j = 0; j < n; j ++){//状态中包含jif((state >> j & 1) && i != j)f[state][i] = min(f[state][i], f[state - (1 << i)][j] + a[j][i]);}}}}cout << f[(1 << n) - 1][n - 1] << endl;return 0;
}

这篇关于状态压缩动态规划:最短Hamilton路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/484688

相关文章

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.