3-Opt局部搜索算法用于TSP问题？

Question

3-Opt局部搜索算法用于TSP问题？

algorithmheuristicstraveling-salesman

7

我知道3-Opt启发式算法涉及从图中删除三条边并添加三条边以重新完成旅行。然而，我看到很多论文提到当移除三条边时，只剩下两种重新组合旅游路径的可能性 - 这对我来说不太合理。

例如，这篇文章说：

“3-opt 算法的工作方式类似于2-opt算法，但是我们要删除三条边而不是两条。这意味着我们有两种将三条路径重新连接成有效旅游路径的方法1。实际上，3-opt移动可以看作是两个或三个2-opt移动。”

然而，我数了8种不同的方法来重新连接旅游路径（如果不考虑在删除边之前的顺序则为7种）。我错过了什么？

另外，有人能链接给我一个3-opt算法吗？如果可能的话，我只是想更好地理解它，但是我还没有找到任何资料。所有我找到的资源都只说“删除三条边，重新连接它们”。以上是需要翻译的内容，请核对。

- u3l

根据这篇文章，你是完全正确的：http://isd.ktu.lt/it2011/material/Proceedings/1_AI_5.pdf 在第2.3节中，从一个图形中生成了8个案例，但其中4个是2-opt的变体，并且新边仅在另外4个案例中被选择。 - elaspog

2个回答

1

在页面底部澄清了它不会将连接视为与单个2-OPT移动相同。如果我没有搞错的话，这就减少到了四种方式。其中三种看起来像图4旋转过后的样子，但总体上我不会说它们是等价的。

- luchovl2

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jmmcd · Accepted Answer

我同意脚注将其减少到了四种方式，而非两种。

在下面的代码中，您可以传递一个排列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