greedy_tsp

greedy_tsp(G, weight='weight', source=None)

从以下位置开始返回低成本周期 source 以及它的成本。

这近似于旅行商问题的解。它找出推销员可以访问的所有节点的循环，以便在最小化总距离的情况下访问多个节点。它使用一种简单的贪婪算法。本质上，这个函数返回一个大的周期，给定一个源点，周期的总成本是最小的。

参数

G图

图应该是一个完全的加权无向图。应包括所有节点对之间的距离。

weight字符串，可选(默认为“权重”)

与边权重对应的边数据关键点。如果任何边不具有该属性，则权重设定为1。

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

起始节点。如果没有，则默认为 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