【动态规划】【广度优先搜索】【状态压缩】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]= MinSelfn 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。

动态规划的初始值

全部为不存在的数

动态规划的返回值

Minj = 0 m c − 1 \Large_{j=0}^{m_c-1}j=0mc1vDis[j].back() -1

证明

将最短路径的重复节点删除,保留任意一个。删除后为: i1 \Large_11 i2 \Large_22 …in \Large_nn 。任意ik \Large_kk到ik + 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;

};


相关文章
|
5月前
|
存储 算法
算法BFS经典例题(迷宫,多源BFS,BFS解决拓扑排序,FloodFill算法)
算法BFS经典例题(迷宫,多源BFS,BFS解决拓扑排序,FloodFill算法)
|
5月前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
6月前
|
人工智能 算法 BI
【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目
【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目
|
6月前
|
监控 算法 测试技术
【动态规划】【树形dp】【C++算法】968监控二叉树
【动态规划】【树形dp】【C++算法】968监控二叉树
|
6月前
|
存储 人工智能
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(中)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
44 0
|
6月前
|
算法 测试技术 C#
【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径
【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径
【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 算法
秒懂算法 | BFS与最短路径
搜索包括BFS和DFS,这两种算法是算法竞赛的基础。本篇介绍BFS的扩展应用。
546 0
秒懂算法 | BFS与最短路径
|
定位技术
BFS:迷宫最短路径
BFS:迷宫最短路径
106 0
|
算法 机器人 C++
数据结构与算法之最短路路径与最短路径和&&动态规划
数据结构与算法之最短路路径与最短路径和&&动态规划
251 0
数据结构与算法之最短路路径与最短路径和&&动态规划