2 NetworkX演算法-近似演算法與啟發式演算法（上）

0 引言

組合優化問題的求解有兩種方法，確定性方法（Exact Method）和近似方法（Approximate Method）[1,2]。

對於每一個解空間（Solution Space），確定性演算法可以保證找到最優解，而且事實上已經證明對於任何規模有限的組合優化問題的實例來說，演算法都可以在與問題有關的運行時間內找到最優解，但對於NP-hard問題，可行時間內在個空間中找到 全局最優解（Global Optimum ） 的可能性很小 （ 幾乎不可能）， 故需要使用近似演算法（Approximate Method） 在有限時間內來尋找一個近似最優解。

近似方法分為兩種 分別為 近似演算法（Approximate Algorithms） 和 啟發式演算法（ Heuristic Algorithms)，這種方法通過降低最優解的精度來換取求解速度的提升。

1.1 基礎概念與定義

1.1.1 基本概念

定義1 使非平凡連通圖G變成不連通圖或者平凡圖需要刪除的最少頂點數稱為圖G的（點）連通度，記為k（G）。

約定：不連通圖或者平凡圖的連通度為0.

定義2 若圖G的連通度不小於k，則稱G是k-連通圖。（也即，連通度為k的圖是1-，2-，3-，,,,，（k-1）-連通圖，或者說，對k-連通圖，如果刪除少於k個頂點，它一定還連通）

1.1.2 點連通度的確定性演算法——回溯法

回溯演算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就」返回，嘗試別的路徑。回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」[3]。

回溯法搜索圖G 中起點i 至終點f 的演算法的步驟如下[4]：

Step1 初始化。除了起始節點i 將圖G 中的每一個節點均標為「可行節點」（即每一個節點均未訪問過，都能成為路徑i-f 中的一點）,令初始路徑數n =0。

Step2 路徑搜索。依次從i 出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，每搜索到一條由i-f 的路徑，n=n+1，重複Step2 直至圖中所有和源點i 有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。

Step3 收斂判定。圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新的頂點，繼續遍歷。

演算法的Python代碼如下所示：

from collections import deque #deque是雙向隊列class Graph(object): # 定義圖類 def __init__(self, *args, **kwargs): # *args表示接受任何多個元組類參數，**kwargs表示接受字典類參數 self.order = [] # 用列表list存儲已訪問的節點序號 self.neighbor = {} # 用字典存儲相鄰節點 def add_node(self, node): key,val = node #將節點的鍵和值分別賦予key和val if not isinstance(val, list): # isinstance可以對參數類型進行辨別，判斷參數val是否為list類型 print(node value should be a list) self.neighbor[key] = val # neighbor的鍵-值對應 def depth_first(self, root): if root != None: search_queue = deque() # 令搜索隊列為雙向隊列 search_queue.append(root) visited = [] # 已訪問的點list為空 else: print(root is None) return -1 while search_queue: person = search_queue.popleft() self.order.append(person) if (not person in visited) and (person in self.neighbor.keys()): tmp = self.neighbor[person] tmp.reverse() for index in tmp: search_queue.appendleft(index) visited.append(person) def node_print(self): for index in self.order: print(index, end= ) if __name__ == __main__:# __name__ 是當前模塊名，當模塊被直接運行時模塊名為 __main__ 。# 這句話的意思就是，當模塊被直接運行時，以下代碼塊將被運行，# 當模塊是被導入時，代碼塊不被運行。 g = Graph() # 建立圖對象 g.add_node((1,[one, two,three])) # 添加節點1 g.add_node((one,[first,second,third])) # 添加節點one g.add_node((two,[1,2,3])) # 添加節點two print(

depth search first:) print( , end= ) g.depth_first(1) g.node_print() print()

由上述代碼，可見圖的回溯演算法，即深度優先演算法（Depth First Search, DFS）。現下複雜網路的研究日益興起，而實際生產生活中的複雜網路都擁有成千上萬個節點，上述演算法的時間複雜度為指數級別，這使得在求解大規模網路的點連通度時，耗時巨大。

文獻[4]針對上述問題，提出了一種改進的近似演算法。該演算法的時間複雜度呈線性增長，針對大規模網路的點連通度求解，具有較好的效果，如1.1.3所示。

1.1.3 點連通度的近似演算法

（1）演算法思想

在回溯法中，基本的思想是選擇一條從起點i 至終點f 的路徑，標註已選擇的點，使後續的路徑不能再選擇該點。一直重複該過程直至不再有通路。但這種枚舉的方法先標最長的路，從而去除掉儘可能多的節點，再標次長的路……這種方法使得標完最長路徑後，去除節點過多，再找可行路徑比較困難。 針對這一缺陷，文獻[4]提出一種先選最短路的方法減少時間複雜度。

（2）演算法步驟

Step1 令所有點均為可行節點，n=0；

step2 尋找由i 至f 的最短路。若最短路存在，n=n+1，已標進可行路徑的點不再是可行節點；

step3 若i 至f 不存在最短路，演算法結束。

1.2 Networkx中點連通度近似演算法的調用

在NetworkX中，計算點連通度的函數共有3個：

all_pairs_node_connectivity(G[,nbunch,cutoff])

作用：計算各個節點之間的節點連通度

來源：networkx.algorithms.approximation.connectivity.all_pairs_node_connectivity

格式：all_pairs_node_connectivity(G, nbunch=None, cutoff=None)

參數：

• G：NetworkX圖
• nbunch（容器）：點容器（container，Python中的Container可以包括list，dictionary，set等,可參見），演算法僅會計算包含在nbunch中的節點，默認為None。
• cutoff：用以求解兩點間最大流的函數，後面再講。

返回值：將返回一個字典。此字典包含所有節點之間的連接度，如果參數中包含nbunch項，則返回nbunch中的點的連接度。

註：根據Menger定理，設u和v是圖G的不鄰接的兩個頂點，則u—v分離集中頂點的最小個數等於G中內部不相交u—v路的最大個數，即本函數所計算的。演算法來源於文獻[4]，可用於無向圖或有向圖。

local_node_connectivity(G, source, target[, . . . ])

作用：計算起訖點之間的節點連通度

來源：networkx.algorithms.approximation.connectivity.local_node_connectivity

格式：local_node_connectivity(G, source, target, cutoff=None)

參數：

• G：NetworkX圖
• source（節點）：起始節點
• target（節點）： 終點
• cutoff（整數）：

返回值：將返回一個整型數值，即指定兩點間的連通度

範例：

# 柏拉圖式的八面體圖的節點連通度為4from networkx.algorithms import approximation as approxG = nx.octahedral_graph()approx.local_node_connectivity(G, 0, 5)

運行結果如圖所示：

註：演算法亦來自於文獻[4]，通過基於深度優先的最短路演算法計算兩節點間的最短路。將路徑上的節點標位「已使用」並繼續搜索其他最短路（不包括已使用的節點），當沒有路徑可標時，演算法結束。當路徑增長時，可能會標出兩個不同的最短路，故該演算法非確定性演算法。因此該演算法僅保證了點連通度的嚴格下限。

node_connectivity(G[, s, t])

作用：返回有向圖或無向圖的近似連通度

來源：networkx.algorithms.approximation.connectivity.node_connectivity

格式：node_connectivity(G, s=None, t=None)

參數：

G：NetworkX圖

s：源點，可選項，默認為None

t：終點，可選項。默認為None

返回值：將返回一個整型數（integer），該整數記錄了圖G的點連通度，若提供起訖節點（即參數中的s和t），則返回指定兩點間的連通度。

1.3 Python源碼

""" Fast approximation for node connectivity"""import itertoolsfrom operator import itemgetterimport networkx as nx__all__ = [local_node_connectivity, node_connectivity, all_pairs_node_connectivity]INF = float(inf)def local_node_connectivity(G, source, target, cutoff=None): """Compute node connectivity between source and target. Pairwise or local node connectivity between two distinct and nonadjacent nodes is the minimum number of nodes that must be removed (minimum separating cutset) to disconnect them. By Mengers theorem, this is equal to the number of node independent paths (paths that share no nodes other than source and target). Which is what we compute in this function. This algorithm is a fast approximation that gives an strict lower bound on the actual number of node independent paths between two nodes [1]_. It works for both directed and undirected graphs. Parameters ---------- G : NetworkX graph source : node Starting node for node connectivity target : node Ending node for node connectivity cutoff : integer Maximum node connectivity to consider. If None, the minimum degree of source or target is used as a cutoff. Default value None. Returns ------- k: integer pairwise node connectivity Examples -------- >>> # Platonic octahedral graph has node connectivity 4 >>> # for each non adjacent node pair >>> from networkx.algorithms import approximation as approx >>> G = nx.octahedral_graph() >>> approx.local_node_connectivity(G, 0, 5) 4 Notes ----- This algorithm [1]_ finds node independents paths between two nodes by computing their shortest path using BFS, marking the nodes of the path found as used and then searching other shortest paths excluding the nodes marked as used until no more paths exist. It is not exact because a shortest path could use nodes that, if the path were longer, may belong to two different node independent paths. Thus it only guarantees an strict lower bound on node connectivity. Note that the authors propose a further refinement, losing accuracy and gaining speed, which is not implemented yet. See also -------- all_pairs_node_connectivity node_connectivity References ---------- .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf """ if target == source: raise nx.NetworkXError("source and target have to be different nodes.") # Maximum possible node independent paths if G.is_directed(): possible = min(G.out_degree(source), G.in_degree(target)) else: possible = min(G.degree(source), G.degree(target)) K = 0 if not possible: return K if cutoff is None: cutoff = INF exclude = set() for i in range(min(possible, cutoff)): try: path = _bidirectional_shortest_path(G, source, target, exclude) exclude.update(set(path)) K += 1 except nx.NetworkXNoPath: break return Kdef node_connectivity(G, s=None, t=None): r"""Returns an approximation for node connectivity for a graph or digraph G. Node connectivity is equal to the minimum number of nodes that must be removed to disconnect G or render it trivial. By Mengers theorem, this is equal to the number of node independent paths (paths that share no nodes other than source and target). If source and target nodes are provided, this function returns the local node connectivity: the minimum number of nodes that must be removed to break all paths from source to target in G. This algorithm is based on a fast approximation that gives an strict lower bound on the actual number of node independent paths between two nodes [1]_. It works for both directed and undirected graphs. Parameters ---------- G : NetworkX graph Undirected graph s : node Source node. Optional. Default value: None. t : node Target node. Optional. Default value: None. Returns ------- K : integer Node connectivity of G, or local node connectivity if source and target are provided. Examples -------- >>> # Platonic octahedral graph is 4-node-connected >>> from networkx.algorithms import approximation as approx >>> G = nx.octahedral_graph() >>> approx.node_connectivity(G) 4 Notes ----- This algorithm [1]_ finds node independents paths between two nodes by computing their shortest path using BFS, marking the nodes of the path found as used and then searching other shortest paths excluding the nodes marked as used until no more paths exist. It is not exact because a shortest path could use nodes that, if the path were longer, may belong to two different node independent paths. Thus it only guarantees an strict lower bound on node connectivity. See also -------- all_pairs_node_connectivity local_node_connectivity References ---------- .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf """ if (s is not None and t is None) or (s is None and t is not None): raise nx.NetworkXError(Both source and target must be specified.) # Local node connectivity if s is not None and t is not None: if s not in G: raise nx.NetworkXError(node %s not in graph % s) if t not in G: raise nx.NetworkXError(node %s not in graph % t) return local_node_connectivity(G, s, t) # Global node connectivity if G.is_directed(): connected_func = nx.is_weakly_connected iter_func = itertools.permutations def neighbors(v): return itertools.chain(G.predecessors(v), G.successors(v)) else: connected_func = nx.is_connected iter_func = itertools.combinations neighbors = G.neighbors if not connected_func(G): return 0 # Choose a node with minimum degree v, minimum_degree = min(G.degree(), key=itemgetter(1)) # Node connectivity is bounded by minimum degree K = minimum_degree # compute local node connectivity with all non-neighbors nodes # and store the minimum for w in set(G) - set(neighbors(v)) - set([v]): K = min(K, local_node_connectivity(G, v, w, cutoff=K)) # Same for non adjacent pairs of neighbors of v for x, y in iter_func(neighbors(v), 2): if y not in G[x] and x != y: K = min(K, local_node_connectivity(G, x, y, cutoff=K)) return Kdef all_pairs_node_connectivity(G, nbunch=None, cutoff=None): """ Compute node connectivity between all pairs of nodes. Pairwise or local node connectivity between two distinct and nonadjacent nodes is the minimum number of nodes that must be removed (minimum separating cutset) to disconnect them. By Mengers theorem, this is equal to the number of node independent paths (paths that share no nodes other than source and target). Which is what we compute in this function. This algorithm is a fast approximation that gives an strict lower bound on the actual number of node independent paths between two nodes [1]_. It works for both directed and undirected graphs. Parameters ---------- G : NetworkX graph nbunch: container Container of nodes. If provided node connectivity will be computed only over pairs of nodes in nbunch. cutoff : integer Maximum node connectivity to consider. If None, the minimum degree of source or target is used as a cutoff in each pair of nodes. Default value None. Returns ------- K : dictionary Dictionary, keyed by source and target, of pairwise node connectivity See Also -------- local_node_connectivity all_pairs_node_connectivity References ---------- .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf """ if nbunch is None: nbunch = G else: nbunch = set(nbunch) directed = G.is_directed() if directed: iter_func = itertools.permutations else: iter_func = itertools.combinations all_pairs = {n: {} for n in nbunch} for u, v in iter_func(nbunch, 2): k = local_node_connectivity(G, u, v, cutoff=cutoff) all_pairs[u][v] = k if not directed: all_pairs[v][u] = k return all_pairsdef _bidirectional_shortest_path(G, source, target, exclude): """Return shortest path between source and target ignoring nodes in the container exclude. Parameters ---------- G : NetworkX graph source : node Starting node for path target : node Ending node for path exclude: container Container for nodes to exclude from the search for shortest paths Returns ------- path: list Shortest path between source and target ignoring nodes in exclude Raises ------ NetworkXNoPath: exception If there is no path or if nodes are adjacent and have only one path between them Notes ----- This function and its helper are originaly from networkx.algorithms.shortest_paths.unweighted and are modified to accept the extra parameter exclude, which is a container for nodes already used in other paths that should be ignored. References ---------- .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf """ # call helper to do the real work results = _bidirectional_pred_succ(G, source, target, exclude) pred, succ, w = results # build path from pred+w+succ path = [] # from source to w while w is not None: path.append(w) w = pred[w] path.reverse() # from w to target w = succ[path[-1]] while w is not None: path.append(w) w = succ[w] return pathdef _bidirectional_pred_succ(G, source, target, exclude): # does BFS from both source and target and meets in the middle # excludes nodes in the container "exclude" from the search if source is None or target is None: raise nx.NetworkXException( "Bidirectional shortest path called without source or target") if target == source: return ({target:None},{source:None},source) # handle either directed or undirected if G.is_directed(): Gpred = G.predecessors Gsucc = G.successors else: Gpred = G.neighbors Gsucc = G.neighbors # predecesssor and successors in search pred = {source: None} succ = {target: None} # initialize fringes, start with forward forward_fringe = [source] reverse_fringe = [target] level = 0 while forward_fringe and reverse_fringe: # Make sure that we iterate one step forward and one step backwards # thus source and target will only tigger "found path" when they are # adjacent and then they can be safely included in the container exclude level += 1 if not level % 2 == 0: this_level = forward_fringe forward_fringe = [] for v in this_level: for w in Gsucc(v): if w in exclude: continue if w not in pred: forward_fringe.append(w) pred[w] = v if w in succ: return pred, succ, w # found path else: this_level = reverse_fringe reverse_fringe = [] for v in this_level: for w in Gpred(v): if w in exclude: continue if w not in succ: succ[w] = v reverse_fringe.append(w) if w in pred: return pred, succ, w # found path raise nx.NetworkXNoPath("No path between %s and %s." % (source, target))

參考文獻

1. Talbi E G. Metaheuristics: From Design to Implementation[J]. Proceedings of SPIE - The International Society for Optical Engineering, 2009, 42(4):497-541.
2. 張燕. 蟻群優化演算法[D].西北師範大學碩士學位論文,2009.
3. 王岩冰,鄭明春,劉弘.回溯演算法的形式模型[J].計算機研究與發展,2001(09):1066-1079.
4. White D R, Newman M. Fast approximation algorithms for finding node-independent paths in networks[J]. Santa Fe Institute Working Pape .2001.

推薦閱讀：