完成 Asadpour 算法

我的 asadpour_atsp 实现现在已经可以工作了！回想一下，我上一篇帖子中给出的这个函数的伪代码是

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.

    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

    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)

    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

    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)

    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)

     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 论文第 385 页中括号内的一个单词的部分。

这个积分环流 $f^*$ 对应于一个包含 $\vec{T}^*$ 的有向（多）图 $H$。

基本上，如果最小流沿某条边的值始终大于 1，则需要添加相同数量的平行边，以确保所有边仍然是欧拉路径。正如以下示例所示，这在开发测试用例时很快就会成为问题。

如你所见，对于不正确的环流，顶点 2 和 3 不是欧拉路径，因为它们的入度和出度不匹配。

所有其他问题都是一些小细节，伪代码无法直接转换为 Python（毕竟，它不是 Python）。

理解输出#

我完成 asadpour_atsp 后做的第一件事是获取分数、对称 Held Karp 松弛测试图，并将其通过通用 traveling_salesman_problem 函数运行。由于这里涉及随机数，因此结果始终在 $O(\log n / \log \log n)$ 近似因子内，但有所不同。下面列出了三个示例。

我们首先要检查的是近似率。我们知道 traveling_saleman_problem 函数的最小成本输出是 304（这实际上低于无向版本中的最佳路径，稍后会详细说明）。接下来，我们需要知道我们的最大近似因子是多少。现在，Asadpour 算法是 $O(\log n / \log \log n)$，对于我们的六顶点图，它将是 $\ln(6) / \ln(\ln(6)) \approx 3.0723$。但是，在第 386 页中，他们将近似的系数给出为 $(2 + 8 \log n / \log \log n)$，这将是 $2 + 8 \times \ln(6) / \ln(\ln(6)) \approx 26.5784$。（请记住，Asadpour 论文中的所有 $\log$ 都指自然对数。）我们所有的示例都远低于这个下限。

例如 1

$$ \begin{array}{r l} \text{实际}: & 504 \\\ \text{预期}: & 304 \\\ \text{近似因子}: & \frac{504}{304} \approx 1.6578 < 3.0723 \end{array} $$

示例 2

$$ \begin{array}{r l} \text{实际}: & 404 \\\ \text{预期}: & 304 \\\ \text{近似因子}: & \frac{404}{304} \approx 1.3289 < 3.0723 \end{array} $$

示例 3

$$ \begin{array}{r l} \text{实际}: & 304 \\\ \text{预期}: & 304 \\\ \text{近似因子}: & \frac{304}{304} = 1.0000 < 3.0723 \end{array} $$

此时，你可能已经注意到，给出的示例严格来说，不是 哈密尔顿回路：它们多次访问顶点。这是因为我们拥有的图不完整。Asadpour 算法仅适用于完整图，因此 traveling_salesman_problem 函数会找到每对顶点之间的最短成本路径，并插入缺失的边。实际上，如果 asadpour_atsp 函数接受一个不完整的图，它将引发异常。以示例三为例，因为它只有一个重复顶点，即 5。

在后台，图是完整的，解决方案可能包含下图中的虚线边。

但是该边不在原始图中，因此在 traveling_salesman_problem 函数执行的后处理过程中，会插入红色边，而不是虚线边。

测试 Asadpour 算法#

在编写任何测试之前，我需要确保测试在每次执行时都保持一致。当时，情况并非如此，因为会生成随机数以对生成树进行采样。因此我不得不学习如何使用 @py_random_state 装饰器。

当此装饰器添加到函数顶部时，我们会将函数签名中参数的位置或该参数的关键字名称传递给它。然后，它将获取该参数，并根据输入参数配置 Python 随机对象。

• 参数为 None，使用新的 Random 对象。
• 参数为 int，使用带有该种子的新的 Random 对象。
• 参数为 Random 对象，直接使用该对象。

因此，我更改了 sample_spanning_tree 函数的函数签名，使其在末尾添加了 random=None。对于大多数用例，默认值不会更改，并且每次调用该方法时，结果都会有所不同，但是如果我们为其提供一个 int，则每次都会采样相同的树。但是，对于我的测试，我可以为其提供一个种子，以创建可重复的行为。由于 sample_spanning_tree 函数在 treveling_salesman 文件之外不可见，因此我还必须为 asadpour_atsp 创建一个直通参数，以便我的种子能够产生任何效果。

完成此操作后，我修改了 sample_spanning_tree 的测试，使其不会有 1/100 的概率自发失败。最初，我只是将一个 int 传递给它，但这迫使所有采样的树都相同（因为边以相同的方式进行了混洗，并且从相同的数字序列中采样），因此测试失败了。因此，我进行了一些调整，使用来自随机包的 Random 对象，这很好地解决了问题。

从这里开始，我将想要使用的完整 asadpour_atsp 参数包装在另一个函数 fixed_asadpour 中，如下所示

def fixed_asadpour(G, weight):
    return nx_app.asadpour_atsp(G, weight, 56)


path = nx_app.traveling_salesman_problem(
    G, weight="weight", cycle=False, method=fixed_asadpour
)

我使用 traveling_salesman_problem 和 asadpour_atsp 进行了测试。测试内容包括：

• 上面提到的分数、对称 Held Karp 图。
• 使用六个城市之间的航空票价的真实世界示例（还使用非整数节点名称）。
• 相同的真实世界示例，但要求的是路径，而不是回路。
• 使用断开的图（引发异常）。
• 使用不完整的图（引发异常）。
• 使用整数 Held Karp 解决方案（在 Held Karp 完成后直接返回，并给出精确解决方案）。
• 使用不可能的图（一个顶点只有出边）。

奖励功能#

甚至还有一个奖励功能！asadpour_atsp 函数接受第四个参数 source！由于两种返回方法都使用 eulerian_circuit 和 _shortcutting 函数，因此我可以将 source 顶点传递给电路函数，并确保返回的路径从所需顶点开始并返回到所需顶点。

通过包装该方法来访问它，只需确保源顶点位于图中，以避免异常。

def fixed_asadpour(G, weight):
    return nx_app.asadpour_atsp(G, weight, source=0)


path = nx_app.traveling_salesman_problem(
    G, weight="weight", cycle=False, method=fixed_asadpour
)

参考文献#

A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan 和 A. Saberi，《非对称旅行商问题 的 $O (\log n / \log \log n)$ 近似算法》，SODA ’10，工业与应用数学学会，2010 年，https://dl.acm.org/doi/abs/10.5555/1873601.1873633。