我不知道如何處理以下問題。假設我有一個帶有end節點和start節點的無向??圖，我需要找到這兩個節點之間的最短路徑，但路徑必須包含所有 mustpass 節點型別。
這些型別最多可以有 10 種。這意味著我應該訪問每種型別的至少一個節點（在影像中用字母標記）然后走到最后。一旦我訪問型別為 的節點之一B，我可以但不必訪問型別 B 的其他節點。標有數字的節點只是形成一條路徑，不需要訪問。
這個問題與此非常相似。建議找到所有關鍵節點之間的最短路徑，然后使用 DFS 演算法。我可以對這個問題應用相同的演算法嗎？
uj5u.com熱心網友回復：
令 N 為頂點數，M 為邊數。
將解決方案分為兩個階段。
階段 1： 計算每對邊之間的距離。如果邊沒有加權，這可以通過從每個節點啟動 BFS 輕松完成，總共花費 O(N(N M)) 時間。如果邊緣是加權的，你可以在每個節點上使用 Dijkstra 演算法，總共花費 O(N(NlogN M)) 時間。
在這個階段之后，我們計算了任意一對節點 x,y 的 dist(x,y)。
階段 2： 現在我們可以使用階段 1 中的預計算值查詢 O(1) 中任意一對節點之間的距離，是時候將所有內容放在一起了。我可以在這里提出兩種可能性
可能性一： 我們采用與您鏈接的執行緒類似的方法。有1個！您可以訪問每個節點的階乘順序。假設我們已經修復了一個可能的順序 [s,t1,t2,...,t10,e] （其中 s 和 e 是開始/結束節點，ti 代表一種型別），我們試圖找出會發生什么是按該順序從頭到尾訪問節點的最佳方式。由于每種型別都可以有多個屬于它的節點，因此并不像查詢每個連續型別 t_i 和 t_{i 1} 的距離那么簡單。相反，如果對于每個節點 x，計算從節點 x 到達末端節點的最快方式，同時尊重型別 [s,t1,...,t10,e] 的順序，我們應該怎么做。因此，如果 x 的型別為 t_i，那么我們正在尋找一種從 x 到達 e 的方法，同時按順序訪問型別為 t_{i 1}、t_{i 2}、... t_{10} 的節點。將此值稱為 dp[x]（其中 dp 代表動態編程）。我們正在尋找 dp[s]。我們如何計算給定節點 x 的 dp[x]？簡單 - 遍歷所有型別為 t_{i 1} 的節點 y 并考慮 d(x,y) dp[y]。然后對于型別為 t_{i 1}} 的所有 y，我們有 dp[x] = min{dist(x,y) dp[y]。請注意，我們需要從 t_10 型別的節點開始一直到 t_1 型別的節點計算 dp[x]。這里的復雜度是 O(10! * N^2)
可能性2： 實際上有一種更快的方法可以找到答案并將復雜性降低到 O(2^10 * N^3) （這可以為大 N 帶來巨大的收益，尤其是對于更多的節點型別（比如 20 而不是 10 ））。為此，我們執行以下操作。對于型別集合 {1,2,...10} 的每個子集 S，以及對于型別在 S 中的每一對節點 x，y，定義 dp[S][x][y]，它表示最快的方式從節點 x 開始遍歷圖，以節點 y 結束，并為 S 中的每種型別訪問所有至少一個節點。請注意，我們不關心實際順序。要計算給定 (S,x,y) 的 dp[S][x][y]，我們需要做的就是檢查第二種訪問的所有可能性（型別為 t3 的節點 z）。然后我們根據 dist(x,z) dp[S-t1][z][y] 更新 dp[S][x][y] （其中 t1 是節點 x 的型別）。所有可能的子集以及開始和結束節點的數量為 2^10 * N^2。為了計算每個 dp，我們考慮了第二個節點訪問的 N 種可能性。所以總的來說我們得到 O(2^10 * N^3)
注意：在我上面的所有分析中，您可以將值 10 替換為更通用的 K，表示可能的不同型別的數量。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514876.html
標籤：算法图形