如果我有一個無向加權圖 G = (V, e) 和一組節點 P，我如何找到包含 P 中所有節點的最小回圈？
我有一個大圖 G 和一組基于用戶輸入的節點 P。在我得到用戶輸入后，我想在 G 上找到包含 P 中所有節點的最短路徑。
有一個恒定的開始/結束節點，它將始終位于 P[0]。
我認為這可能是對旅行商問題的一些修改，它找到了包括所有頂點的最短路徑。
uj5u.com熱心網友回復：
我可以想到兩個命題，一個是基于貪心演算法的，它可能會給你一條路徑，另一個應該給你最好的路徑，如果存在的話。
貪心解決方案
- 設定起始節點
p_start = P[0] - 設定
G(v,e)帶有節點v和邊的圖形e - 從起始節點
p_start，運行Dijkstra 演算法，直到P到達集合中的所有節點 p_start保存從到集合中任何其他節點的所有可能路徑中的最短路徑p。讓我們將最短路徑記為從p_start到節點的路徑P[ii]P[ii]從集合中移除P并移除邊緣e- 回傳步驟 3. 直到集合
p為空
解釋
正如我所說，這個解決方案是貪婪的，因為它保存了從起點到集合中任何候選節點的最岸路徑P。即使可能存在答案，該解決方案也可能不會回傳答案，因為該解決方案可能在某些點需要更長的路徑才能成功完成回圈。
解決方案建議
現在我們奠定了基礎，我們可以轉向我建議的解決方案。這個問題可以看一個自我避免行走問題。我已經撰寫了一個解決方案的實作，以在此處找到自我避免問題中的所有可能路徑，但這更有問題。對于少量節點，您可以運行附件中的解決方案，即計算所有可能的路徑，然后從通過所有節點的所有路徑中選擇最好的一個P。但是，對于大圖，我建議進行以下調整：
設定起始節點，從集合
p_start = P[0]中移除P[0]設定
G(v,e)帶有節點v和邊的圖形e將起始路徑設定為空串列
path = []設定
state_stack為空串列[]從
p_start，將 Dijkstra 演算法運行到集合 'P' 中的其余節點對于
ii長度（'P'）：6.1。注意
e_ii是選擇連接p_start到的邊緣P[ii]6.2. 注意
P_ii是沒有設定P的P[ii]6.3. 創建一個新的元組
(P[ii], G(v, e\e_ii), P_ii, path e_ii)并添加到state_stack（新的起始狀態，新的圖，新的必須通過集，到目前為止采取的路徑）彈出另一個狀態
state_line：new_state = state_stack.pop()設定
p_start = new_state[0]；G = new_state[1];P = new_state[2]回傳第 5 步。直到
state_stack為空選擇最佳累積路徑
解釋
此程序將使用 Dijkstra 計算最短路徑。該路徑將被保存，并且從每個目的地，將計算到所有剩余目的地的新路徑等。該演算法將按初始集的大小因子增長，P但如果存在這樣的解決方案，它將回傳最佳解決方案，因為它計算P在選擇最佳排列并回傳之前，集合中所有可能的訪問排列。
uj5u.com熱心網友回復：
我認為您指的是最小生成樹。它計算最小總邊權重以連接圖中的每個頂點。實作 MST 有兩種主要演算法（最小生成樹。一種是Prim 演算法，一種是Kruskal 演算法。我建議您研究這兩種解決方案，但是在您的問題中您提到您有一個初始起始頂點 P[0 ]，在這種情況下，我建議您研究 Prim 的演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452498.html
上一篇：鏈表-跟蹤每個節點