greedy_tsp#

greedy_tsp(G, weight='weight', source=None)[source]#

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

这近似解决了旅行商问题。它找到一个包含所有节点的循环，使得销售员可以按顺序访问多个节点，同时最小化总距离。它使用一个简单的贪心算法。本质上，该函数返回一个给定源点的大循环，使得循环的总成本最小化。

Parameters:
GGraph

该图应为一个完整的加权无向图。 所有节点对之间的距离应包含在内。

weightstring, 可选 (默认=”weight”)

对应边权重的边数据键。 如果任何边没有此属性，则权重设置为1。

sourcenode, 可选 (默认: 列表中的第一个节点)

起始节点。如果为None，默认为 next(iter(G))

Returns:
cyclelist of nodes

返回销售员可以遵循以最小化旅行总权重的循环（节点列表）。

Raises:
NetworkXError

如果 G 不完整，算法会引发异常。

Notes

该贪心算法的实现基于以下内容：

  • 算法在每次迭代中向解决方案添加一个节点。

  • 算法选择一个尚未在循环中的节点，其与前一个节点的连接为循环增加了最小的成本。

贪心算法并不总是给出最佳解决方案。然而，它可以构造一个初始可行解，该解可以作为参数传递给模拟退火或阈值接受等迭代改进算法。

时间复杂度：运行时间为:math:O(|V|^2)

Examples

>>> from networkx.algorithms import approximation as approx
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     {
...         ("A", "B", 3),
...         ("A", "C", 17),
...         ("A", "D", 14),
...         ("B", "A", 3),
...         ("B", "C", 12),
...         ("B", "D", 16),
...         ("C", "A", 13),
...         ("C", "B", 12),
...         ("C", "D", 4),
...         ("D", "A", 14),
...         ("D", "B", 15),
...         ("D", "C", 2),
...     }
... )
>>> cycle = approx.greedy_tsp(G, source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31
On this page