【动态规划】【广度优先搜索】【状态压缩】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=0mc1vDis[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=0mc1vDis[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;
};

【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径,# 算法题,数据结构与算法,动态规划,宽度优先,c++,算法,LeetCode,图论,状态压缩

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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 访问所有节点的最短路径,# 算法题,数据结构与算法,动态规划,宽度优先,c++,算法,LeetCode,图论,状态压缩文章来源地址https://www.toymoban.com/news/detail-817359.html

到了这里,关于【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】【广度优先】LeetCode2258:逃离火灾

    视频算法专题 二分查找算法合集 动态规划汇总 二分查找 给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ,它表示一个网格图。每个格子为下面 3 个值之一: 0 表示草地。 1 表示着火的格子。 2 表示一座墙,你跟火都不能通过这个格子。 一开始你在最左上角的格子

    2024年02月05日
    浏览(39)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 【BFS三维路径规划】广度优先搜索算法无人机三维路径规划【含Matlab源码 270期】

    获取代码方式1: 完整代码已上传我的资源:【三维路径规划】基于matlab广度优先搜索算法无人机三维路径规划【含Matlab源码 270期】 获取代码方式2: 付费专栏Matlab路径规划(初级版) 备注: 点击上面蓝色字体付费专栏Matlab路径规划(初级版),扫描上面二维码,付费29.9元

    2024年02月02日
    浏览(51)
  • 蓝桥杯-回路计数(状态压缩、动态规划)

    蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 ​​ 到 21 21 21 ​​。对于两栋教学楼 a a a 和 b b b ​,当 a a a 和 b b b 互质时, a a a 和 b b b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。 小蓝现在在第一栋教学楼,他想要访问每栋教学楼正

    2024年02月08日
    浏览(60)
  • 深度优先搜索与动态规划|543, 124, 687

    好久没写二叉树了,主要还是看遍历的顺序是什么样的。 这个有点绕不出来。绕一遍, root -10 进去,root.left是root 9,root.right是root 20 root 9 进去得到的return是9,res更新得到9 root 20进去,root.left是root 15,root.right是root 7 root 15进去得到的return是15,res更新得到15 root 7进去得到的

    2024年02月13日
    浏览(39)
  • [动态规划,二进制状态压缩] 旅行商问题

    题目描述 一个国家有 n 个城市,每两个城市之间都开设有航班,从城市 i 到城市 j 的航班价格为 cost[i, j] ,而且往、返航班的价格相同。 售货商要从一个城市出发,途径每个城市 1 次(且每个城市只能经过 1 次),最终返回出发地,而且他的交通工具只有航班,请求出他旅

    2024年01月24日
    浏览(43)
  • 【状态压缩】【动态规划】【C++算法】691贴纸拼词

    视频算法专题 动态规划汇总 状态压缩 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。 返回你需要拼

    2024年01月19日
    浏览(39)
  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(39)
  • 【图论--搜索篇】宽度优先搜索,广度优先搜索

    今日语录: 成功是一种心态,如果你相信自己能做到,那你已经迈出成功的第一步。

    2024年01月24日
    浏览(46)
  • 快来看看萌新小白学习动态规划、深度优先搜索、贪心

    由于比赛临近,老师给我们布置了一些LeetCode算法题目,但是我在学完Hello算法的数据结构部分之后,就跑去学习算法第四版了。被一些安全比赛耽误,算法的学习进度比较慢,通过这篇文章就可以体现出我的技术还是比较菜的,还望谅解,哈哈。 LeetCode题目#206 反转链表 这是

    2024年04月14日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包