【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

2024-01-22 12:04
文章标签 动态 规划 访问 路径 搜索 所有 压缩 状态 节点 优先 广度 847

本文主要是介绍【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总
广度优先搜索 状态压缩

LeetCode847 访问所有节点的最短路径

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 1：
输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]
示例 2：
输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]
参数范围：
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] 不包含 i
如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
输入的图总是连通图

广度优先搜索

需要记录那些节点已经访问，用状态压缩 (1 << i )表示第i个节点已访问。
还要记录此路径的最后节点。
这两个状态相同，后面的路径则相同。 由于是广度优先搜索，所以路径短的先处理，每个状态只会处理一次。
vDis 记录各状态的最短路径数。
que 记录状态。
时间复杂度：O(n2nn) 枚举起点O(n) 枚举状态数O(2^n) 每个状态处理。

核心代码

class Solution {
public:int shortestPathLength(vector<vector<int>>& graph) {m_c = graph.size();m_iMaskCount = 1 << m_c;for (int i = 0; i < m_c; i++){BFS(graph, i);}return m_iRet;}void BFS(vector<vector<int>>& neiBo,int start){vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay));queue<pair<int, int>> que;auto Add = [&](int node, int iPreMask,int iNew){const int iMask = iPreMask | (1 << node);if (vDis[node][iMask] <= iNew ){return ;}vDis[node][iMask] = iNew;que.emplace(node, iMask);};Add( start,0, 0);while (que.size()){auto [preNode, preMask] = que.front();const int iNew = vDis[preNode][preMask]+1;que.pop();for (const auto& next : neiBo[preNode]){Add(next, preMask, iNew);}}for (const auto& v : vDis){m_iRet = min(m_iRet, v.back());}}const int m_iNotMay = 100'000;int m_c, m_iMaskCount;int m_iRet = m_iNotMay;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{	vector<vector<int>> graph;{Solution sln;graph = { {1,2,3},{0},{0},{0} };auto res = sln.shortestPathLength(graph);Assert(res, 4);}{Solution sln;graph = { {1},{0,2,4},{1,3,4},{2},{1,2} };auto res = sln.shortestPathLength(graph);Assert(res, 4);}}

动态规划

节点的距离用多源路径的最短距离。

动态规划的状态表示

mask&(1 << next)表示经过了next节点。
vDis[node][mask] 有以下两种含义：
一， 以node结尾，经过mask指定节点的最短路径经过的节点数。
二，以node结尾，且只经过node节点一次,经过mask指定节点的最短路径经过的节点数。
含义二，如果存在，则是含义二，否则是含义一。 必须枚举所有符合含义二的可能。

动态规划的转移方程

vDis[next][maks|next]= MinSelf n e x t = 0 m c − 1 \Large_{next=0}^{m_c-1} next=0mc​−1​vDis[i][mask]+距离(i,next)
vDis[i][mask] 必须合法，且mask不包括next节点

动态规划的填表顺序

mask从1到大，确保动态规划的无后效性。某路径的编码是mask，经过新节点next后，新编码为iNewMask。则iNewMask-mask = 1 << next
1 << next 恒大于0。

动态规划的初始值

全部为不存在的数

动态规划的返回值

Min j = 0 m c − 1 \Large_{j=0}^{m_c-1} j=0mc​−1​vDis[j].back() -1

证明

将最短路径的重复节点删除，保留任意一个。删除后为: i 1 \Large_1 1​ i 2 \Large_2 2​ …i n \Large_n n​ 。任意i k \Large_k k​到i k + 1 \Large_{k+1} k+1​的路径一定是最短，否则替换成最短。直接枚举，12! 超时。 用动态规划，共2nn种状态，空间复杂度O(2nn)，每种状态转移时间复杂度O(n)，故总时间复杂度O(2nnn)。

代码

//多源码路径
template<class T, T INF = 1000 * 1000 * 1000>
class CFloyd
{
public:CFloyd(const  vector<vector<T>>& mat){m_vMat = mat;const int n = mat.size();for (int i = 0; i < n; i++){//通过i中转for (int i1 = 0; i1 < n; i1++){for (int i2 = 0; i2 < n; i2++){//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离}}}};vector<vector<T>> m_vMat;
};class Solution {
public:int shortestPathLength(vector<vector<int>>& graph) {m_c = graph.size();m_iMaskCount = 1 << m_c;vector<vector<int>> mat(m_c, vector<int>(m_c, 1000 * 1000 * 1000));for (int i = 0; i < m_c; i++){for (const auto& j : graph[i]){mat[i][j] = 1;}}CFloyd floyd(mat);vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay));for (int i = 0; i < m_c; i++){	vDis[i][1 << i] = 1;}for (int mask = 1; mask < m_iMaskCount; mask++){for (int i = 0; i < m_c; i++){if (vDis[i][mask] >= m_iNotMay){continue;}for (int next = 0 ;next < m_c ;next++ ){if ((1 << next) & mask){continue;//已经访问}const int iNewMask = (1 << next) | mask;vDis[next][iNewMask] = min(vDis[next][iNewMask], vDis[i][mask] + floyd.m_vMat[i][next]);}}}int iRet = m_iNotMay;for (const auto& v : vDis){iRet = min(iRet, v.back());}return iRet-1;}const int m_iNotMay = 100'000;int m_c, m_iMaskCount;};

2023年1月

class Solution {
public:
int shortestPathLength(vector<vector>& graph) {
auto Add = [this](int iMask, int iPos, int iOpeNum)
{
if (INT_MAX != m_vMaskPosMinOpe[iMask][iPos])
{
return;
}
m_vQue.emplace_back(iMask, iPos);
m_vMaskPosMinOpe[iMask][iPos] = iOpeNum;
};
m_c = graph.size();
for (int i = 0; i < sizeof(m_vMaskPosMinOpe) / sizeof(m_vMaskPosMinOpe[0]); i++)
{
for (int j = 0; j < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); j++)
{
m_vMaskPosMinOpe[i][j] = INT_MAX;
}
}
for (int i = 0; i < m_c; i++)
{
Add(1 << i, i, 0);
}
for (int i = 0; i < m_vQue.size(); i++)
{
const int iMask = m_vQue[i].first;
const int iPos = m_vQue[i].second;
for (auto& next : graph[iPos])
{
int iNewMask = iMask | (1 << next);
Add(iNewMask, next, m_vMaskPosMinOpe[iMask][iPos] + 1);
}
}
int iMin = INT_MAX;
for (int i = 0; i < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); i++)
{
iMin = min(iMin, m_vMaskPosMinOpe[(1 << m_c) - 1][i]);
}
return iMin;
}
vector<std::pair<int,int>> m_vQue;
int m_vMaskPosMinOpe[1 << 12 ][12];
int m_c;
};

2023年8月

class Solution {
public:
int shortestPathLength(vector<vector>& graph) {
auto Add = [this](int iMask, int iPos, int iOpeNum)
{
if (INT_MAX != m_vMaskPosMinOpe[iMask][iPos])
{
return;
}
m_vQue.emplace_back(iMask, iPos);
m_vMaskPosMinOpe[iMask][iPos] = iOpeNum;
};
m_c = graph.size();
for (int i = 0; i < sizeof(m_vMaskPosMinOpe) / sizeof(m_vMaskPosMinOpe[0]); i++)
{
for (int j = 0; j < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); j++)
{
m_vMaskPosMinOpe[i][j] = INT_MAX;
}
}
for (int i = 0; i < m_c; i++)
{
Add(1 << i, i, 0);
}
for (int i = 0; i < m_vQue.size(); i++)
{
const int iMask = m_vQue[i].first;
const int iPos = m_vQue[i].second;
for (auto& next : graph[iPos])
{
int iNewMask = iMask | (1 << next);
Add(iNewMask, next, m_vMaskPosMinOpe[iMask][iPos] + 1);
}
}
int iMin = INT_MAX;
for (int i = 0; i < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); i++)
{
iMin = min(iMin, m_vMaskPosMinOpe[(1 << m_c) - 1][i]);
}
return iMin;
}
vector<std::pair<int,int>> m_vQue;
int m_vMaskPosMinOpe[1 << 12 ][12];
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/632898。

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
安卓链接正常显示，ios#符被转义%23导致链接访问404

安卓链接正常显示，ios#符被转义%23导致链接访问404

原因分析： url中含有特殊字符 中文未编码 都有可能导致URL转换失败，所以需要对url编码处理  如下： guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时，会被误伤转义为%23，导致链接无法访问
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2