近似算法与启发式算法#

图属性的近似计算和优化问题的启发式方法。

此类中的函数不会被导入到顶级 networkx 命名空间中，因此使用它们的最简单方法是

>>> from networkx.algorithms import approximation

另一种选择是使用 from networkx.algorithms.approximation import function_name 导入特定函数。

连通性#

节点连通性的快速近似计算

all_pairs_node_connectivity(G[, nbunch, cutoff])

计算所有节点对之间的节点连通性。

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

计算源节点和目标节点之间的节点连通性。

node_connectivity(G[, s, t])

返回图或有向图 G 的节点连通性近似值。

K-分量#

K-分量结构的快速近似计算

k_components(G[, min_density])

返回图 G 的近似 K-分量结构。

团#

用于计算大团和最大独立集的函数。

maximum_independent_set(G)

返回近似最大独立集。

max_clique(G)

查找最大团

clique_removal(G)

从图中重复移除团。

large_clique_size(G)

查找图中大团的大小。

聚类#

average_clustering(G[, trials, seed])

估计图 G 的平均聚类系数。

距离度量#

近似的距离度量指标。

diameter(G[, seed])

返回图 G 直径的下界。

支配集#

用于查找节点支配集和边支配集的函数。

无向图 G 的支配集是指其顶点集 V 和边集 E 的子集 D，使得 V 中不在 D 内的每个顶点都与 D 中至少一个顶点相邻。边支配集是 E 的子集 F，使得 E 中不在 F 内的每条边都至少与 F 中一条边的端点相关联。

min_weighted_dominating_set(G[, weight])

返回近似最小权重节点支配集。

min_edge_dominating_set(G)

返回最小基数边支配集。

匹配#

给定图 G = (V,E)，G 中的匹配 M 是一组成对不相邻的边；也就是说，任意两条边都不共享同一个顶点。

维基百科：匹配

min_maximal_matching(G)

返回图 G 的最小极大匹配。

Ramsey#

Ramsey数。

ramsey_R2(G)

计算图 G 中的最大团和最大独立集。

Steiner树#

metric_closure(G[, weight])

返回图的度量闭包。

steiner_tree(G, terminal_nodes[, weight, method])

返回图的最小 Steiner 树的近似解。

旅行商#

旅行商问题 (TSP)#

解决和近似 TSP 问题的近似算法实现。

已实现的算法类别

  • Christofides 算法 (提供 TSP 的 3/2 近似解)

  • 贪心算法

  • 模拟退火算法 (SA)

  • 阈值接受算法 (TA)

  • Asadpour 非对称旅行商算法

旅行商问题旨在找到一条路径，给定旅行商必须访问的所有地点之间的权重（距离），使得

  • 旅行商行走的总距离（成本）最小化。

  • 旅行商回到起始点。

  • 注意，对于完全图，旅行商访问每个地点恰好一次。

函数 travelling_salesman_problem 通过寻找所有节点对之间的最短路径来处理非完全图，有效地将问题转换为完全图问题。它在该问题上调用一种近似方法，然后使用之前找到的最短路径将结果转换回原始图。

TSP 是组合优化中的一个 NP-hard 问题，在运筹学和理论计算机科学中非常重要。

http://en.wikipedia.org/wiki/Travelling_salesman_problem

christofides(G[, weight, tree])

近似求解旅行商问题

traveling_salesman_problem(G[, weight, ...])

查找图 G 中访问指定节点的最短环

greedy_tsp(G[, weight, source])

返回从源节点开始的低成本环及其成本。

simulated_annealing_tsp(G, init_cycle[, ...])

返回旅行商问题的近似解。

threshold_accepting_tsp(G, init_cycle[, ...])

返回旅行商问题的近似解。

asadpour_atsp(G[, weight, seed, source])

返回旅行商问题的近似解。

树宽#

用于计算树分解的函数。

无向图的树宽是与该图相关联的一个数字。它可以定义为图中树分解中最大顶点集（袋）的大小减一。

维基百科：树宽

树宽和树分解的概念之所以具有吸引力，部分原因是许多在任意图上难以处理（例如 NP-hard）的图和网络问题，当输入图的树宽由一个常数限制时，变得可以高效解决（例如，使用线性时间算法）[1] [2]。

有两种不同的函数用于计算树分解：treewidth_min_degree() 和 treewidth_min_fill_in()。

[1]

Hans L. Bodlaender and Arie M. C. A. Koster. 2010. “Treewidth computations I.Upper bounds”. Inf. Comput. 208, 3 (March 2010),259-275. http://dx.doi.org/10.1016/j.ic.2009.03.008

[2]

Hans L. Bodlaender. “Discovering Treewidth”. Institute of Information and Computing Sciences, Utrecht University. Technical Report UU-CS-2005-018. http://www.cs.uu.nl

treewidth_min_degree(G)

使用最小度启发式算法返回树分解。

treewidth_min_fill_in(G)

使用最小填充启发式算法返回树分解。

顶点覆盖#

用于计算近似最小权重顶点覆盖的函数。

一个顶点覆盖 是节点的子集，使得图中的每条边都至少与该子集中的一个节点相关联。

min_weighted_vertex_cover(G[, weight])

返回近似最小权重顶点覆盖。

最大割#

randomized_partitioning(G[, seed, p, weight])

计算图节点的随机划分及其割值。

one_exchange(G[, initial_cut, seed, weight])

计算图节点的划分和相应的割值。
在本页面上