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

Question

我正在寻找某种"多米诺排序"算法,该算法根据后续项目的"切线"边的相似性对双面项目列表进行排序.

假设以下列表中的项目由2元组表示:

>>> 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。这篇维基百科文章可能是一个很好的起点。