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

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

一般来说，这个问题是关于寻找一个Hamiltonian path与著名的Travelling salesman problem (TSP)密切相关的最小长度.而且它看起来不像是可以在多项式时间内解决的这个问题的特例。

有大量的启发式算法和近似算法可用于解决 TSP。 This wikipedia article可能是一个很好的起点。