threshold_accepting_tsp#

threshold_accepting_tsp(G, init_cycle, weight='weight', source=None, threshold=1, move='1-1', max_iterations=10, N_inner=100, alpha=0.1, seed=None)[源代码]#

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

该函数使用阈值接受方法来逼近节点的最小代价周期。从次优解决方案开始，阈值接受方法会扰乱该解决方案，接受使解决方案不比阈值增加更差的任何更改。成本的改善是可以接受的，但导致成本小幅增加的变化也是可以接受的。这允许解在解空间中离开次最优局部极小值。随着迭代的进行，阈值缓慢降低，有助于确保最优。总之，该函数返回一个从 source 从而使总成本最小化。

参数

G图

G should be a complete weighted undirected graph. The distance between all pairs of nodes should be included.

init_cycle名单或“贪婪”

初始解决方案(循环遍历所有节点，返回到起点)。这一论点没有默认的理由让你去思考。如果是“贪婪”，请使用 greedy_tsp(G, weight) 。其他常见的启动周期包括 list(G) + [next(iter(G))] 或者最终的结果是 simulated_annealing_tsp 在做的时候 threshold_accepting_tsp 。

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

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

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

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

threshold整型，可选(默认值=1)

该算法的阈值参数。它表示初始阈值的值

move“1-1”或“1-0”或函数，可选(默认为“1-1”)

在寻找新的试验解决方案时使用什么移动的指示器。字符串表示两个特殊的内置动作：

“1-1”：1-1交换，将当前溶液中两个元素的位置互换。调用的函数为 swap_two_nodes() 。例如，如果我们在解决方案中应用1-1交换 A = [3, 2, 1, 4, 3] 通过1和4元素的换位，我们可以得到以下结果： A' = [3, 2, 4, 1, 3]
“1-0”：1-0交换，将解决方案中的节点移动到新位置。调用的函数为 move_one_node() 。例如，如果我们在解决方案中应用1-0交换 A = [3, 2, 1, 4, 3] 我们可以将第四个元素转移到第二个位置： A' = [3, 4, 2, 1, 3]

您可以提供自己的函数来执行从一个解决方案到相邻解决方案的移动。函数必须将解决方案作为输入，同时还必须使用 seed 控制随机数生成的输入(请参阅 seed 在此输入)。您的函数应该将解保持为一个循环，第一个节点和最后一个节点相等，所有其他节点出现一次。您的函数应该返回新的解决方案。

max_iterations整型，可选(默认值=10)

当外部循环的这个连续迭代次数在最佳成本解决方案中没有任何变化时被声明为完成。

N_inner整型，可选(默认为100)

内部循环的迭代次数。

alpha浮动在(0，1)之间，可选(默认为0.1)

当至少有一个邻居的解决方案被接受时，阈值百分比降低。如果不接受内部循环移动，则阈值保持不变。

seed整数、随机状态或无（默认）

随机数生成状态的指示器。见 Randomness .

返回

cycle节点列表: 返回销售人员可以遵循的周期(节点列表)，以最小化行程的总重量。

加薪

NetworkXError: 如果 G 如果未完成，则该算法将引发异常。

参见

simulated_annealing_tsp

笔记

阈值接受是一种元启发式局部搜索算法。该算法的主要特点是为了避开低质量的局部最优解而接受偶数解，从而导致代价的增加。

该算法需要一个初始解。这个解可以用一个简单的贪婪算法来构造。在每一次迭代中，它都会仔细地选择一个相邻的解决方案。考虑 \(c(x)\) 当前解决方案的成本和 \(c(x')\) 邻居解决方案的成本。如果 \(c(x') - c(x) <= threshold\) 然后，邻居解成为下一次迭代的当前解，其中阈值被命名为阈值。

与模拟退火法相比，阈值接受算法不接受质量非常低的解(由于阈值的存在)。在模拟退火法的情况下，即使是非常低质量的解也可能被接受 \(p\) 。

时间复杂性：它有一个运行时间 \(O(m * n * |V|)\) 哪里 \(m\) 和 \(n\) 分别是外部循环和内部循环运行的次数。

有关更多信息以及算法的灵感来源，请参阅：https://doi.org/10.1016/0021-9991(90)90201-B

实例

>>> 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.threshold_accepting_tsp(G, "greedy", source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31
>>> incycle = ["D", "B", "A", "C", "D"]
>>> cycle = approx.threshold_accepting_tsp(G, incycle, source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31