破圈演算法
❶ 運籌學有哪些演算法
圖像法，單純形法，對偶單純法，兩階段法。圖像法只能解一般的含兩個未知數的不等式。後3種是解多個未知數的不等式。運籌學還有整數規劃，一般有分支定界法，隱枚舉法，匈牙利法。運輸問題——一般為產銷問題，用最小元素法先做，再用位勢法調整目標規劃問題——先建模，再用單純形法解，一般現在用excel解決動態規劃——逆序法，順序法最小支撐樹圖——避圈法，破圈法最短路問題——dijkstra演算法
❷ 為什麼破圈法和避圈法為什麼不能求一點至另一點的最短距離
1.1最小生成樹
最小生成樹：一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結點，並且有保持圖連通的最少的邊，如圖1.1.1所示。
圖1.1.1 最小生成樹示意圖
設G = (V, E)是無向連通帶權圖，即一個網路。E中的每一條邊（v, w）的權為W(v, w)。如果G的子圖G』是一棵包含G的所有頂點的樹，則稱G』為G的生成樹。生成樹上各邊權的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。
1.1.1避圈法
避圈法的主要思想就是：開始選一條最小權的邊，以後每一步中，總從與已選邊不構成圈的那些未選邊中，選擇一條權最小的（每一步中，如果有兩條或兩條以上的邊都是權值最小的邊，則從中任選一條）。避圈法主要分為兩種：Prim演算法和Kruskal演算法，下面分別進行介紹。
1.1.1.1 Prim演算法
設G = (V, E)是連通帶權圖，V = {1,2,…,n}。構造G的最小生成樹Prim演算法的基本思想是：首先置S = {1}，然後，只要S是V的真子集，就進行如下的貪心選擇：選取滿足條件i∈S, j∈V – S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S = V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。圖1.1.2顯示了某一帶權圖。最小生成樹的生成過程如下：
→=
c
13;1
→=
c
36;4
32;5
→=
c
c
→=
25;3
最終得到的最小生成樹如圖1.1.3所示。
圖1.1.2 帶權圖G
圖1.1.3 帶權圖G的最小生成樹示意圖
1.1.1.2 Kruskal演算法
給定無向連通帶權圖G = (V, E), V = {1,2,...,n}。Kruskal演算法構造G的最小生成樹的基本思想是：
(1) 將G的n個頂點看成n個孤立的連通分支，並將所有的邊按權從小到大排序；
(2) 從第一條邊開始，依據每條邊的權值遞增的順序檢查每一條邊，並按照下述方法連接兩個不同的連通分支：當查看到第k條邊(v, w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2的端點時，就用邊(v, w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接查看第k+1條邊，這個過程一個進行到只剩下一個連通分支時為止。此時，已構成G的一棵最小生成樹。
仍以圖1.1.2所示的帶權圖G為例說明其最小生成樹的生成過程，生成過程如下所示：
→=
c
13;1
25;3c →=
36;4c →=
23;5c →=
最終得到的最小生成樹和圖1.1.3所示是一樣的。
1.1.2 破圈法
破圈法可以描述如下：
(1) 如果我們給的連通圖G 中沒有迴路，那麼G 本身就是一棵生成樹；
(2) 若G 中只有一個迴路，則刪去G 的迴路上的一條邊（不刪除結點），則產生的圖仍是連通的且沒有迴路，則得到的子圖就是圖G 的一棵生成樹；
(3) 若G 的迴路不止一個，只要刪去每一個迴路上的一條邊，直到G 的子圖是連通沒有迴路且與圖G 有一樣的結點集，那麼這個子圖就是一棵生成樹。
由於我們破壞迴路的方法可以不一樣，所以可得到不同的生成樹，但是在求最小生成樹的時候，為了保證求得的生成樹的樹權最小，那麼在刪去迴路上的邊的時候，總是在保證帶權圖仍連通的前提下刪掉權值較大的邊，保留權值較小的邊。破圈法就是在帶權圖的迴路中找出權值最大的邊，將該邊去掉，重復這個過程，直到圖連通且沒有圈為止，保留下來的邊所組成的圖即為最小生成樹。下面仍利用圖1.1.2對破圈法進行說明。
首先是去除權值大的邊，並且檢測去除該邊後整個圖是否連通，對於圖1.1.2來說，即第一步去掉權值為6的邊，如圖1.1.4所示。
圖1.1.4 去掉權值為6的G 的示意圖
從圖中可以看出，去掉權值為6的邊後整個圖仍是連通的。所以接下來去除權值為5的邊，並且檢測去除該邊後圖是否連通，結果如圖1.1.5所示。由圖可知，去掉所有權值為5的邊會造成圖G 不連通，因此23;5c →=這條邊是必須保留的。然後再去除權值為4的
邊。由於權值為1、2、3、4的邊分別連接著獨立的節點，故都必須保留，得到的最小生成
圖1.1.5 去掉權值為5的G的示意圖
樹結果與圖1.1.3也是一樣的。
1.1.3避圈法與破圈法比較
Prim演算法是從空圖出發，將點進行二分化，從而逐步加邊得到最小生成樹。它是近似求解演算法，雖然對於大多數最小生成樹問題都能求得最優解，但相當一部分求得的是近似最優解，具體應用時不一定很方便。但是它可以看作是很多種最小樹演算法的概括，在理論上有一定的意義。
Kruskal演算法也是從空圖出發。它是精確演算法，即每次都能求得最優解，但對於規模較大的最小生成樹問題，求解速度較慢。
破圈法是從圖G出發，逐步去邊破圈得到最小生成樹。它最適合在圖上工作，當圖較大時，可以幾個人同時在各個子圖上工作，因此破圈法在實用上是很方便的。
￥
5.9
網路文庫VIP限時優惠現在開通,立享6億+VIP內容
立即獲取
破圈法vs避圈法
1.1最小生成樹
最小生成樹：一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結點，並且有保持圖連通的最少的邊，如圖1.1.1所示。
圖1.1.1 最小生成樹示意圖
設G = (V, E)是無向連通帶權圖，即一個網路。E中的每一條邊（v, w）的權為W(v, w)。如果G的子圖G』是一棵包含G的所有頂點的樹，則稱G』為G的生成樹。生成樹上各邊權的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。
第 1 頁
1.1.1避圈法
避圈法的主要思想就是：開始選一條最小權的邊，以後每一步中，總從與已選邊不構成圈的那些未選邊中，選擇一條權最小的（每一步中，如果有兩條或兩條以上的邊都是權值最小的邊，則從中任選一條）。避圈法主要分為兩種：Prim演算法和Kruskal演算法，下面分別進行介紹。
1.1.1.1 Prim演算法
設G = (V, E)是連通帶權圖，V = {1,2,…,n}。構造G的最小生成樹Prim演算法的基本思想是：首先置S = {1}，然後，只要S是V的真子集，就進行如下的貪心選擇：選取滿足條件i∈S, j∈V – S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S = V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。圖1.1.2顯示了某一帶權圖。最小生成樹的生成過程如下：