Approximations and Heuristics#

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

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

>>> from networkx.algorithms import approximation

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

Connectivity#

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

all_pairs_node_connectivity(G[, nbunch, cutoff])

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

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

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

node_connectivity(G[, s, t])

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

K-components#

快速近似算法用于k-分量结构

k_components(G[, min_density])

返回图 G 的近似 k-连通分量结构。

Clique#

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

maximum_independent_set(G)

返回一个近似最大独立集。

max_clique(G)

寻找最大团

clique_removal(G)

重复地从图中移除团。

large_clique_size(G)

寻找图中的一个大型团的大小。

Clustering#

average_clustering(G[, trials, seed])

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

Distance Measures#

距离度量近似于度量标准。

diameter(G[, seed])

返回图 G 的直径下界。

Dominating Set#

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

无向图 G 的 支配集 是指顶点集 V 的一个子集 D，使得 D 外的每个顶点都至少与 D 中的一个顶点相邻。 边支配集 是指边集 E 的一个子集 F，使得 F 外的每条边都至少与 F 中某条边的端点相邻。

min_weighted_dominating_set(G[, weight])

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

min_edge_dominating_set(G)

返回最小基数边支配集。

Matching#

图匹配#

给定一个图 G = (V, E)，G 中的匹配 M 是一组成对非邻接的边；也就是说，没有两条边共享一个公共顶点。

min_maximal_matching(G)

返回图 G 的最小极大匹配。即，在图 G 的所有极大匹配中，返回最小的匹配。

Ramsey#

拉姆齐数。

ramsey_R2(G)

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

Steiner Tree#

metric_closure(G[, weight])

返回图的度量闭包。

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

返回图的最小Steiner树的近似结果。

Traveling Salesman#

旅行商问题 (TSP)#

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

已实现的算法类别包括：

  • 克里斯托费德斯算法（提供3/2近似解）

  • 贪心算法

  • 模拟退火算法 (SA)

  • 阈值接受算法 (TA)

  • Asadpour 非对称旅行商算法

旅行商问题试图找到，在给定销售员必须访问的所有点之间的权重（距离）的情况下，满足以下条件的路线：

  • 销售员旅行的总距离（成本）最小化。

  • 销售员返回起点。

  • 注意，对于完全图，销售员每个点只访问一次。

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

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

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

christofides(G[, weight, tree])

近似求解旅行商问题

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

在 G 中找到连接指定节点的最短路径

greedy_tsp(G[, weight, source])

返回从 source 开始的低成本循环及其成本。

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

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

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

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

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

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

Treewidth#

计算树宽分解的函数。

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

树宽和树分解的概念之所以受到关注，部分原因是许多在任意图上难以处理（例如，NP难）的图和网络问题，在输入图的树宽被常数界定的情况下变得可以高效求解（例如，使用线性时间算法）[Rfd2b568a4a59-1]_ [2]。

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

[1]

Hans L. Bodlaender 和 Arie M. C. A. Koster. 2010. “树宽计算 I. 上界”. 信息计算 208, 3 (2010年3月), 259-275. http://dx.doi.org/10.1016/j.ic.2009.03.008

[2]

Hans L. Bodlaender. “发现树宽”. 信息与计算科学研究所，乌得勒支大学. 技术报告 UU-CS-2005-018. http://www.cs.uu.nl

treewidth_min_degree(G)

返回使用最小度启发式的树宽分解。

treewidth_min_fill_in(G)

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

Vertex Cover#

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

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

min_weighted_vertex_cover(G[, weight])

返回一个近似的最小加权顶点覆盖。

Max Cut#

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

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

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

计算图的节点划分及其对应的割值。
On this page