Сортировка списка элементов, заданных парой чисел, по принципу последовательного сходства

Как отсортировать элементы в списке так, чтобы сумма квадратов разностей «концов» элементов была минимальной? Проблема напоминает задачу коммивояжера. Рассмотрим приблизительное решение.

Дан список элементов, каждый из которых представлен кортежем из пары чисел (x, y):

dominos = [
    (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)
... )

Проблема напоминает задачу коммивояжера. Один из приблизительных подходов к решению:

# Domino Packing
from bisect import bisect_left
from pprint import pprint


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


def find_nearest(values, target):
    """
    Assumes values is sorted. Returns closest value to target.
    If two numbers are equally close, return the smallest number.
    """
    idx = bisect_left(values, target)
    if idx == 0:
        return 0
    if idx == len(values):
        return -1
    before = values[idx - 1]
    after = values[idx]
    if after - target < target - before:
        return idx      # after
    else:
        return idx - 1  # before


if __name__ == '__main__':

    dominos = [(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)]

    dominos = sorted(dominos, key=lambda x: x[0])
    x_values, y_values = [list(l) for l in zip(*dominos)]
    packed = list()
    idx = 0

    for _ in range(len(dominos)):
        x = x_values[idx]
        y = y_values[idx]
        del x_values[idx]
        del y_values[idx]

        idx = find_nearest(x_values, y)
        packed.append((x, y))

    pprint(packed)
    print("loss :%f" % compute_loss(packed))

Результат:

[(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)]
loss :0.138100

Список кортежей сортируется по значению x. Функция bisect_left помогает найти в отсортированном списке индекс похожего значения для использования при подготовке следующего кортежа. Обратите внимание, что bisect_left предполагает, что список предварительно отсортирован.


За пример спасибо stacksonstacks.