根据连续项的相似性对双面项列表进行排序

Question

我正在寻找某种“多米诺排序”算法，该算法基于后续项的“切”边的相似性来排序一个双面项列表。

>>> items
[(0.72, 0.12),
 (0.11, 0.67),
 (0.74, 0.65),
 (0.32, 0.52),
 (0.82, 0.43),
 (0.94, 0.64),
 (0.39, 0.95),
 (0.01, 0.72),
 (0.49, 0.41),
 (0.27, 0.60)]

目标是对该列表进行排序，使得每两个后续项的切线端差的平方和（损失）最小：

>>> loss = sum(
...     (items[i][1] - items[i+1][0])**2
...     for i in range(len(items)-1)
... )

对于上面的示例，这可以通过处理所有可能的排列来计算，但是对于包含更多项的列表，这很快就变得不可行(O(n！）)。

一步一步地选择最佳匹配的方法

def compute_loss(items):
    return sum((items[i][1] - items[i+1][0])**2 for i in range(len(items)-1))


def domino_sort(items):
    best_attempt = items
    best_score = compute_loss(best_attempt)
    for i in range(len(items)):
        copy = [x for x in items]
        attempt = [copy.pop(i)]
        for j in range(len(copy)):
            copy = sorted(copy, key=lambda x: abs(x[0] - attempt[-1][1]))
            attempt.append(copy.pop(0))
        score = compute_loss(attempt)
        if score < best_score:
            best_attempt = attempt
            best_score = score
    return best_attempt, best_score

给出以下结果，损失0.1381:

[(0.01, 0.72),
 (0.72, 0.12),
 (0.11, 0.67),
 (0.74, 0.65),
 (0.49, 0.41),
 (0.39, 0.95),
 (0.94, 0.64),
 (0.82, 0.43),
 (0.32, 0.52),
 (0.27, 0.6)]

但这不是最好的解决办法

[(0.01, 0.72),
 (0.82, 0.43),
 (0.27, 0.6),
 (0.49, 0.41),
 (0.32, 0.52),
 (0.39, 0.95),
 (0.94, 0.64),
 (0.72, 0.12),
 (0.11, 0.67),
 (0.74, 0.65)]

丢失0.0842。显然，上述算法对前几个项目表现良好，但对后几个项目的差异变得如此之大，以至于它们主导了损失。

如果不可能在小于O(n！）的情况下准确地进行这种排序，有没有可能返回一个好的分数（小损失）的近似方法？

Answer 1

一般而言，该问题是关于寻找与著名旅行商问题(TSP)密切相关的最小长度哈密顿路径的问题。而且它看起来不像是这个问题的一个特例，可以在多项式时间内解决。

求解TSP问题有大量的启发式算法和近似算法。这篇维基百科文章可能是一个很好的开始。