作者推薦
視頻算法專題
本文涉及知識點
動態(tài)規(guī)劃匯總
廣度優(yōu)先搜索 狀態(tài)壓縮
LeetCode847 訪問所有節(jié)點的最短路徑
存在一個由 n 個節(jié)點組成的無向連通圖，圖中的節(jié)點按從 0 到 n - 1 編號。
給你一個數(shù)組 graph 表示這個圖。其中，graph[i] 是一個列表，由所有與節(jié)點 i 直接相連的節(jié)點組成。
返回能夠訪問所有節(jié)點的最短路徑的長度。你可以在任一節(jié)點開始和停止，也可以多次重訪節(jié)點，并且可以重用邊。
示例 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]
參數(shù)范圍：
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] 不包含 i
如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
輸入的圖總是連通圖
廣度優(yōu)先搜索
需要記錄那些節(jié)點已經(jīng)訪問，用狀態(tài)壓縮 (1 << i )表示第i個節(jié)點已訪問。
還要記錄此路徑的最后節(jié)點。
這兩個狀態(tài)相同，后面的路徑則相同。 由于是廣度優(yōu)先搜索，所以路徑短的先處理，每個狀態(tài)只會處理一次。
vDis 記錄各狀態(tài)的最短路徑數(shù)。
que 記錄狀態(tài)。
時間復雜度：O(n2nn) 枚舉起點O(n) 枚舉狀態(tài)數(shù)O(2^n) 每個狀態(tài)處理。
核心代碼
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);
}
}
動態(tài)規(guī)劃
節(jié)點的距離用多源路徑的最短距離。
動態(tài)規(guī)劃的狀態(tài)表示
mask&(1 << next)表示經(jīng)過了next節(jié)點。
vDis[node][mask] 有以下兩種含義：
一， 以node結尾，經(jīng)過mask指定節(jié)點的最短路徑經(jīng)過的節(jié)點數(shù)。
二，以node結尾，且只經(jīng)過node節(jié)點一次,經(jīng)過mask指定節(jié)點的最短路徑經(jīng)過的節(jié)點數(shù)。
含義二，如果存在，則是含義二，否則是含義一。 必須枚舉所有符合含義二的可能。
動態(tài)規(guī)劃的轉移方程
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節(jié)點
動態(tài)規(guī)劃的填表順序
mask從1到大，確保動態(tài)規(guī)劃的無后效性。某路徑的編碼是mask，經(jīng)過新節(jié)點next后，新編碼為iNewMask。則iNewMask-mask = 1 << next
1 << next 恒大于0。
動態(tài)規(guī)劃的初始值
全部為不存在的數(shù)
動態(tài)規(guī)劃的返回值
Min j = 0 m c ? 1 \Large_{j=0}^{m_c-1} j=0mc??1?vDis[j].back() -1
證明
將最短路徑的重復節(jié)點刪除，保留任意一個。刪除后為: 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! 超時。 用動態(tài)規(guī)劃，共2nn種狀態(tài)，空間復雜度O(2nn)，每種狀態(tài)轉移時間復雜度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;//已經(jīng)訪問
}
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;
};
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區(qū)（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成戰(zhàn)斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
相關
下載
想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。 |
| 子墨子言之：事無終始，無務多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
測試環(huán)境
操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實現(xiàn)。文章來源：http://www.zghlxwxcb.cn/news/detail-817359.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-817359.html
到了這里，關于【動態(tài)規(guī)劃】【廣度優(yōu)先搜索】【狀態(tài)壓縮】847 訪問所有節(jié)點的最短路徑的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
