状态压缩动态规划:最短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

相关文章

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.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod