好吧，我们终于来到了这个 GSoC 项目的节点，终点已经若隐若现。我已经完成了 Held Karp 松弛，生成了一个生成树分布，现在正在从该分布中采样。这意味着是时候开始考虑如何将这些独立的组件连接到一个算法中。
回想一下，从 Asadpour 的论文中，算法概述如下：
算法 1 一个针对 ATSP 的 $O(\log n / \log \log n)$-近似算法
输入： 一个包含 $n$ 个点的集合 $V$，以及一个满足三角不等式的成本函数 $c\ :\ V \times V \rightarrow \mathbb{R}^+$。
输出： 由 $V$ 和 $c$ 描述的非对称旅行商问题实例的 $O(\log n / \log \log n)$-近似解。
- 求解 ATSP 实例的 Held-Karp LP 松弛，得到一个最优极点解 $x^*$。定义 $z^*$ 如 (5) 所示，将其设为 $x^*$ 的对称化和缩小版本。向量 $z^*$ 可以被视为一个点，位于 $x^*$ 支撑上无向图的生成树多面体中，该图是在忽略弧方向后获得的（参见第 3 节）。
- 令 $E$ 为 $z^*$ 在忽略弧方向后的支撑图。找到权重 ${\tilde{\gamma}}_{e \in E}$，使得生成树上的指数分布，$\tilde{p}(T) \propto \exp(\sum_{e \in T} \tilde{\gamma}_e)$（近似地）保留了由 $z^*$ 施加的边际，即对于任何边 $e \in E$，
$\sum\_{T \in \mathcal{T} : T \ni e} \tilde{p}(T) \leq (1 + \epsilon) z^\*\_e$, 对于足够小的 $\epsilon$ 值。（在这篇论文中，我们证明了 $\epsilon = 0.2$ 对于我们的目的来说已经足够了。请参阅第 7 节和第 8 节，了解如何计算这种分布的描述。）- 从 $\tilde{p}(.)$ 中采样 $2\lceil \log n \rceil$ 个生成树 $T_1, \dots, T_{2\lceil \log n \rceil}$。对于这些树中的每一个，将所有边定向，以最小化其相对于我们的（非对称）成本函数 $c$ 的成本。令 $T^*$ 为在所有采样树中成本最小的树。
- 找到包含定向树 $\vec{T}^*$ 的最小成本整数环流。将此环流缩短为一个环路，并输出它。（参见第 4 节）。
我们现在已牢固地处于步骤 3 和 4 的区域。回顾我 2021 年 5 月 24 日发布的标题为 Networkx 函数桩 的文章，唯一剩下的函数是 asadpour_tsp，它是需要完成整个算法的主要函数。但在我们开始为它创建伪代码之前，步骤 4 还需要经过仔细检查。
环流和缩短#
一旦我们从图中采样了足够的生成树，并将最小生成树转换为 $\vec{T}^*$，我们就需要找到图中包含 $\vec{T}^*$ 的最小成本整数环流。虽然 NetworkX 提供了一个最小成本环流函数，即 min_cost_flow，但它不能直接用于 Asadpour 算法。这里的问题在于我们没有节点需求，而是有边需求。然而，经过一些阅读和与我的导师之一 Dan 的讨论，我们可以将当前问题转换为可以使用 min_cost_flow 函数解决的问题。
我们试图解决的问题被称为最小成本环流问题，而 min_cost_flow 能够解决的问题是，嗯，最小成本流问题。碰巧的是，这些是等价问题，因此我可以通过将最小边需求转换为节点需求，将最小成本环流转换为最小成本流问题。
回想一下，此时我们有一个定向最小采样生成树 $\vec{T}^*$，并且通过 $\vec{T}^*$ 中每条边的流都需要至少为 1。从流问题的角度来看，$\vec{T}^*$ 正在将一些流移动到图的周围。但是，为了将 $\vec{T}^*$ 扩展成一个欧拉图，以便我们可以遍历它，我们需要抵消这种流，使每个节点的净流为 0 $(f(\delta^+(v)) = f(\delta^-(v))$ 在 Asadpour 论文中)。
因此，我们找到每个节点的净流，然后将其需求指定为该数字的负值，以便流将在该节点处平衡。如果任何节点 $i$ 的总流为 $\delta^+(i) - \delta^-(i)$，那么我们为该节点指定的需求为 $\delta^-(i) - \delta^+(i)$。一旦我们将需求分配给节点，我们就可以暂时忽略边下限容量，找到最小流。
有关转换过程的更多信息，请参阅 [2]。
找到最小流后，我们取流的支撑，将其添加到 $\vec{T}^*$ 中，以创建一个多重图 $H$。现在我们知道 $H$ 是弱连通的（它包含 $\vec{T^*}$），并且它是欧拉图，因为对于每个节点，入度等于出度。可以使用 eulerian_circuit 在此图中找到闭合欧拉路径或欧拉回路。
这是一个在简单图上执行此过程的示例。我怀疑流并不总是生成树的回边，并且这种情况只发生在这里，是因为顶点数较少。
最后，我们取欧拉回路并将其缩短。从好的方面来说，缩短过程与 Christofides 算法相同，因此已经存在于旅行商文件中的 _shortcutting 辅助函数中。这实际上是在三角不等式成立时至关重要的，因为缩短不会增加环流的成本。
asadpour_tsp 的伪代码#
让我们从函数签名开始。
def asadpour_tsp
Input: A complete graph G with weight being the attribute key for the edge weights.
Output: A list of edges which form the approximate ATSP solution.
这正是我们所期望的，获取一个满足三角不等式的完全图 $G$，并返回非对称旅行商问题的近似解中的边。回顾一下我之前的文章 Networkx 函数桩，主要旅行商函数 traveling_salesman_problem 将确保我们得到一个满足三角不等式的完全图，方法是使用全对最短路径计算，并且将处理我们是否需要返回一个真正的循环或只是一个路径的情况。
Asadpour 算法的第一步是 Held Karp 松弛。我计划在此处稍微调整算法的流程。如果 Held Karp 松弛找到一个整数解，那么我们知道它是一个最优 TSP 路径，因此没有必要继续算法：我们可以直接将其返回作为最优解。然而，如果 Held Karp 松弛找到一个分数解，我们将继续执行算法。
z_star = held_karp(G)
# test to see if z_star is a graph or dict
if type(z_star) is nx.DiGraph
return z_star.edges
一旦我们有了 Held Karp 解，我们就创建 z_star 的无向支撑，以便在下一步创建生成树的指数分布时使用。
z_support = nx.MultiGraph()
for u, v in z_star
if not in z_support.edges
edge_weight = min(G[u][v][weight], G[v][u][weight])
z_support.add_edge(u, v, weight=edge_weight)
gamma = spanning_tree_distribution(z_support, z_star)
这完成了本文开头 Asadpour 概述中的步骤 1 和 2。接下来，我们采样 $2 \lceil \log n \rceil$ 个生成树。
for u, v in z_support.edges
z_support[u][v][lambda] = exp(gamma[(u, v)])
for _ in range 1 to 2 ceil(log(n))
sampled_tree = sample_spanning_tree(G)
sampled_tree_weight = sampled_tree.size()
if sampled_tree_weight < minimum_sampled_tree_weight
minimum_sampled_tree = sampled_tree.copy()
minimum_sampled_tree_weight = sampled_tree_weight
现在我们有了最小采样树，我们需要定向边方向，以使成本保持与该最小树相同。我们可以通过迭代 minimum_sampled_tree 中的边，并检查原始图 $G$ 中的边权来完成此操作。如果我们在创建 z_support 时没有记录最小方向，那么这里需要使用 $G$。
t_star = nx.DiGraph
for u, v, d in minimum_sampled_tree.edges(data=weight)
if d == G[u][v][weight]
t_star.add_edge(u, v, weight=d)
else
t_star.add_edge(v, u, weight=d)
接下来，我们为最小成本流问题创建节点到节点需求的映射，这在本文前面已经讨论过了。我认为使用字典是最佳选择，因为它可以一次性传递到 set_node_attributes 中，然后在找到最小成本流之前进行分配。
for n in t_star
node_demands[n] = t_star.out_degree(n) - t_star.in_degree(n)
nx.set_node_attributes(G, node_demands)
flow_dict = nx.min_cost_flow(G)
取欧拉回路，并在输出时将其缩短。在这里，我们可以直接将流的支撑添加到 t_star 中，以模拟将两个图加在一起。
for u, v in flow_dict
if edge not in t_star.edges and flow_dict[u, v] > 0
t_star.add_edge(u, v)
eulerian_curcuit = nx.eulerian_circuit(t_star)
return _shortcutting(eulerian_curcuit)
应该就是这些了。一旦 asadpour_tsp 的代码编写完成，就需要对其进行测试。我还不太确定如何创建测试用例，但我确实计划使用真实世界的航空机票价格对其进行测试，因为这是我最常用的非对称旅行商问题的示例。
参考文献#
A. Asadpour, M. X. Goemans, A. Mardry, S. O. Ghran，以及 A. Saberi，针对非对称旅行商问题的一个 o(log n / log log n)-近似算法，运筹学，65 (2017)，pp. 1043-1061。
D. Williamson，ORIE 633 网络流讲座 11，2007 年 10 月 11 日，https://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture11.pdf.