《算法竞赛进阶指南》 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

相关文章

CentOS7更改默认SSH端口与配置指南

《CentOS7更改默认SSH端口与配置指南》SSH是Linux服务器远程管理的核心工具,其默认监听端口为22,由于端口22众所周知,这也使得服务器容易受到自动化扫描和暴力破解攻击,本文将系统性地介绍... 目录引言为什么要更改 SSH 默认端口?步骤详解:如何更改 Centos 7 的 SSH 默认端口1

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码(一)pom.

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

PyInstaller打包selenium-wire过程中常见问题和解决指南

《PyInstaller打包selenium-wire过程中常见问题和解决指南》常用的打包工具PyInstaller能将Python项目打包成单个可执行文件,但也会因为兼容性问题和路径管理而出现各种运... 目录前言1. 背景2. 可能遇到的问题概述3. PyInstaller 打包步骤及参数配置4. 依赖

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n