《算法竞赛进阶指南》 91. 最短Hamilton路径

2023-10-29 08:18

本文主要是介绍《算法竞赛进阶指南》 91. 最短Hamilton路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《算法竞赛进阶指南》 91. 最短Hamilton路径

  • 1.问题分析
  • 2.具体代码
  • 3.总结

题目链接(经典问题,无原题链接)

  • 是否看了题解找思路

1.问题分析

0.原题:
给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

1.暴力做法(dfs爆搜)
用dfs搜索卡在了n=15上,但是好像有人dfs可以AC,应该是我剪枝没剪好。
2.状态压缩dp的复习
分析题目可知,每种情况可用二进制的状态表示。
动态规划的分析:(1).dp[state][j]表示状态为state,最终落在j点上的最小值。例如:经过0(必须经过0点),1,4三点,最终停在2点上的状态表示为dp[10011][2]——错误!该状态不合法;dp[10111][2]——正确!
(2).集合的划分:暴力枚举所有点,不断更新。

2.具体代码

//暴力dfs
#include <iostream>using namespace std;
const int N = 21;
int data[N][N];
int n,sum,ans,path[N];
bool vis[N];
void dfs(int u,int d)
{if(d==n&&path[d-1]==n-1){ans=min(ans,sum);}else if(path[d-1]!=n-1){vis[u]=true;for(int i=0;i!=n;i++){if(!vis[i]){sum+=data[u][i];path[d]=i;dfs(i,d+1);sum-=data[u][i];}}vis[u]=false;}
}
int main()
{cin>>n;ans=0x3f3f3f3f;for(int i=0;i!=n;i++)for(int j=0;j!=n;j++)cin>>data[i][j];dfs(0,1);cout<<ans;return 0;
}
//状态压缩dp
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 20,M= 1<<20;
int w[N][N],n;
int dp[M][N];
int main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];memset(dp,0x3f,sizeof dp);dp[1<<0][0]=0;for(int i=1;i<(1<<n);i++)//枚举所有状态for(int j=0;j<n;j++)//遍历所有点{if((i>>j & 1))//判断当前状态是否经过了j点for(int k=0;k<n;k++)//如果当前状态经过了j点,则以j为基础,遍历所有点{if((i^(1<<j)) >> k & 1)//难点! 单独总结dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);}}cout<<dp[(1<<n)-1][n-1]<<endl;return 0;
}

3.总结

(i^(1<<j)) >> k & 1
判断i^(1<<j)状态含k点,
确保dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);操作合法
当前i状态是从i^(1<<j)转移来的

这篇关于《算法竞赛进阶指南》 91. 最短Hamilton路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

JavaScript错误处理避坑指南

《JavaScript错误处理避坑指南》JavaScript错误处理是编程过程中不可避免的部分,它涉及到识别、捕获和响应代码运行时可能出现的问题,本文将详细给大家介绍一下JavaScript错误处理的... 目录一、错误类型:三大“杀手”与应对策略1. 语法错误(SyntaxError)2. 运行时错误(R

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

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

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