algorithm - 3 选择本地搜索 TSP？

Question

我了解 3-Opt Heuristic 涉及从图中删除三个边并添加三个边以重新完成巡回。然而，我看到很多论文都提到当删除三个边时，只剩下 2 种可能的方式来重新组合游览 - 这对我来说没有意义。

例如，this论文说:

The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1. A 3-opt move can actually be seen as two or three 2-opt moves.

但是，我计算了 8 种不同的方式来重新连接游览(如果不计算移除边缘之前的顺序，则有 7 种)。我在这里错过了什么？

此外，如果可能的话，有人可以将我链接到 3-opt 算法吗？我只是想更好地理解它，但我还没有遇到过。我找到的所有资源都简单地说“删除三个边，重新连接它们”。就是这样。

Answer 1

我同意脚注将其减少为四种方式，而不是两种。

在下面的代码中，您可以传入一个排列 p，它将执行 3-opt，四种可能性之一。如果您还传递了 broad=False，它将允许 8 个中的任何一个(包括标识)。

但是，我真的很欢迎查看此代码，或任何其他在线实现的链接。

请注意，此代码并未强制我们切割的边最初是不连续的。应该吗？

另请注意，这只是移动，它不会执行尝试所有移动并选择最佳移动的完整例程。

def three_opt(p, broad=False):
    """In the broad sense, 3-opt means choosing any three edges ab, cd
    and ef and chopping them, and then reconnecting (such that the
    result is still a complete tour). There are eight ways of doing
    it. One is the identity, 3 are 2-opt moves (because either ab, cd,
    or ef is reconnected), and 4 are 3-opt moves (in the narrower
    sense)."""
    n = len(p)
    # choose 3 unique edges defined by their first node
    a, c, e = random.sample(range(n+1), 3)
    # without loss of generality, sort
    a, c, e = sorted([a, c, e])
    b, d, f = a+1, c+1, e+1

    if broad == True:
        which = random.randint(0, 7) # allow any of the 8
    else:
        which = random.choice([3, 4, 5, 6]) # allow only strict 3-opt

    # in the following slices, the nodes abcdef are referred to by
    # name. x:y:-1 means step backwards. anything like c+1 or d-1
    # refers to c or d, but to include the item itself, we use the +1
    # or -1 in the slice
    if which == 0:
        sol = p[:a+1] + p[b:c+1]    + p[d:e+1]    + p[f:] # identity
    elif which == 1:
        sol = p[:a+1] + p[b:c+1]    + p[e:d-1:-1] + p[f:] # 2-opt
    elif which == 2:
        sol = p[:a+1] + p[c:b-1:-1] + p[d:e+1]    + p[f:] # 2-opt
    elif which == 3:
        sol = p[:a+1] + p[c:b-1:-1] + p[e:d-1:-1] + p[f:] # 3-opt
    elif which == 4:
        sol = p[:a+1] + p[d:e+1]    + p[b:c+1]    + p[f:] # 3-opt
    elif which == 5:
        sol = p[:a+1] + p[d:e+1]    + p[c:b-1:-1] + p[f:] # 3-opt
    elif which == 6:
        sol = p[:a+1] + p[e:d-1:-1] + p[b:c+1]    + p[f:] # 3-opt
    elif which == 7:
        sol = p[:a+1] + p[e:d-1:-1] + p[c:b-1:-1] + p[f:] # 2-opt

    return sol