greedy_tsp#

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

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

这近似求解旅行商问题。它找到一个包含所有节点的回路，旅行商可以在其中访问许多节点同时最小化总距离。它使用简单的贪心算法。本质上，此函数返回一个给定起点、总成本最小的大回路。

参数:
G图

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

weight字符串，可选 (默认=”weight”)

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

source节点，可选 (默认：列表list(G)中的第一个节点)

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

返回值:
cycle节点列表

返回旅行商可以遵循的回路（节点列表），以最小化旅行的总权重。

引发:
NetworkXError

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

备注

此贪心算法的实现基于以下原理：

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

  • 算法选择一个尚未在回路中的节点，该节点与前一个节点的连接给回路带来的成本增加最少。

贪心算法并不总是能给出最优解。但是，它可以构建一个初步的可行解，该解可以作为参数传递给迭代改进算法，例如模拟退火或阈值接受法。

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

示例

>>> 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
在此页