Trier une liste d'éléments à deux faces en fonction de la similarité des éléments consécutifs.

Question

Je cherche une sorte d'algorithme de "Domino sort" qui trie une liste d'éléments à deux côtés en fonction de la similarité des côtés "tangents" des éléments suivants.

Supposons la liste suivante où les éléments sont représentés par des 2-tuples :

>>> 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)]

Le but est de trier cette liste de telle sorte que la somme des différences au carré des extrémités tangentes de chacun des deux éléments suivants (la perte) soit minimale :

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

Dans l'exemple ci-dessus, ce calcul peut être effectué en passant en revue toutes les permutations possibles, mais pour les listes comportant un plus grand nombre d'éléments, cela devient rapidement irréalisable ( O(n!) ).

L'approche de la sélection de la meilleure correspondance étape par étape, telle que décrite ici

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

donne le résultat suivant avec une perte de 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)]

Ce n'est cependant pas la meilleure solution qui serait

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

avec une perte de 0.0842 . De toute évidence, l'algorithme ci-dessus donne de bons résultats pour les premiers éléments, mais les différences pour les derniers éléments deviennent si importantes qu'elles dominent la perte.

Existe-t-il un algorithme capable d'effectuer ce type de tri dans un délai acceptable (réalisable pour des listes de plusieurs centaines d'éléments) ?

S'il n'est pas possible de faire ce genre de choses exactement en moins de O(n!) existe-t-il des approches approximatives susceptibles de rapporter un bon score (faible perte) ?

Answer 1

En général, ce problème consiste à trouver un chemin Hamiltonien avec une longueur minimale qui est étroitement liée à la célèbre Problème du voyageur de commerce (TSP) . Et cela ne ressemble pas à un cas particulier de ce problème qui peut être résolu en temps polynomial.

Il existe une quantité énorme d'heuristiques et d'algorithmes approximatifs pour résoudre les TSP. Cet article de wikipedia pourrait être un bon point de départ.

Answer 2

Version légèrement plus efficace de l'approche naïve utilisant bisect.
(félicitations pour la mise en œuvre : https://stackoverflow.com/a/12141511/6163736 )

# 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))

sortie :

[(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

Answer 3

La question théorique a déjà été abordée dans d'autres réponses. J'ai essayé d'améliorer votre algorithme du "plus proche voisin non visité".

Avant d'entrer dans les alogrithmes, notez que vous pouvez évidemment remplacer sorted + pop(0) par pop(min_index) :

min_index, _ = min(enumerate(copy), key=lambda i_x: abs(i_x[1][0] - attempt[-1][1]))
attempt.append(copy.pop(min_index))

Méthode 1 : améliorer l'approche de base

J'ai été guidé par une idée très simple : au lieu de considérer seulement le côté gauche du domino suivant pour voir si elle correspond au côté droit de la séquence actuelle, pourquoi ne pas ajouter une contrainte sur son côté droit également ?

J'ai essayé ceci : vérifier si le côté droit du candidat est proche du côté gauche des dominos restants. Je pensais qu'il était plus facile de trouver le domino "suivant" avec un côté droit proche de la moyenne des côtés gauches restants. J'ai donc apporté les modifications suivantes à votre code :

mean = sum(x[0] for x in copy)/len(copy)
copy = sorted(copy, key=lambda x: abs(x[0] - attempt[-1][1]) + abs(x[1]-mean)) # give a bonus for being close to the mean.

Mais ce n'était pas une amélioration. La perte cumulée pour 100 séries aléatoires de 100 éléments (toutes les valeurs entre 0 et 1) était :

• plus proche voisin non visité : 132.73
• le plus proche voisin non visité et le côté droit proche de la moyenne : 259.13

Après quelques ajustements, j'ai essayé de transformer le bonus en pénalité :

mean = sum(x[0] for x in copy)/len(copy)
copy = sorted(copy, key=lambda x: 2*abs(x[0] - attempt[-1][1]) - abs(x[1]-mean)) # note the 2 times and the minus

Cette fois, il y a eu une nette amélioration :

• voisin le plus proche non visité : 145.00
• le plus proche voisin non visité et le côté droit loin de la moyenne : 93.65

Mais pourquoi ? J'ai fait une petite recherche. Évidemment, l'algorithme original est plus performant au début, mais le nouvel algorithme "consomme" les gros dominos (avec un grand écart entre la gauche et la droite) et est donc plus performant à la fin.

C'est pourquoi je me suis concentré sur l'écart :

copy = sorted(copy, key=lambda x: 2*abs(x[0] - attempt[-1][1]) - abs(x[1]-x[0]))

L'idée est claire : consommer les gros dominos avant les autres. Cela a bien fonctionné :

• plus proche voisin non visité : 132.85
• le plus proche voisin non visité et le côté droit loin de la moyenne : 90.71
• voisin le plus proche non visité et gros dominos : 79.51

Méthode 2 : Améliorer une séquence donnée

Ok, maintenant une heuristique plus sophistiquée. Je me suis inspiré de l'heuristique Lin-Kernighan . J'ai essayé de construire des séquences de swap répondant à la condition suivante : arrêter la séquence dès que le dernier swap a produit une diminution de la perte locale pour l'un des dominos échangés. Chaque séquence de swap est estimée pour trouver la meilleure.

Un code sera plus clair qu'une longue explication :

def improve_sort(items, N=4):
    """Take every pair of dominos and try to build a sequence that will maybe reduce the loss.
    N is the threshold for the size of the subsequence"""
    ret = items
    ret = (items, compute_loss(items))
    for i in range(len(items)):
        for j in range(i+1, len(items)):
            # for every couple of indices
            r = try_to_find_better_swap_sequence(ret, [i, j], N)
            if r[1] < ret[1]:
                ret = r

    return ret

def try_to_find_better_swap_sequence(ret, indices, N):
    """Try to swap dominos until the local loss is greater than in the previous sequence"""
    stack = [(indices, ret[0])] # for an iterative DFS
    while stack:
        indices, items = stack.pop()

        # pop the last indices
        j = indices.pop()
        i = indices.pop()
        # create a copy and swap the i-th and the j-th element
        items2 = list(items)
        items2[i] = items[j]
        items2[j] = items[i]
        loss = compute_loss(items2)
        if loss < ret[1]:
            ret = (items2, loss)
        if len(indices) <= N-3: # at most N indices in the sequence
            # continue if there is at least one local improvement
            if local_loss(items2, i) < local_loss(items, i): # i was improved
                stack.extend((indices+[i,j,k], items2) for k in range(j+1, len(items2)))
            if local_loss(items2, j) < local_loss(items, j): # j was improved
                stack.extend((indices+[j,i,k], items2) for k in range(i+1, len(items2)))

    return ret

def local_loss(items, i):
    """This is the loss on the left and the right of the domino"""
    if i==0:
        return (items[i][1] - items[i+1][0])**2
    elif i==len(items)-1:
        return (items[i-1][1] - items[i][0])**2
    else:
        return (items[i-1][1] - items[i][0])**2+(items[i][1] - items[i+1][0])**2

• pas de tri + tri amélioré : 46.72
• le plus proche voisin non visité et les gros dominos : 78.37
• plus proche voisin non visité et gros dominos + improve_sort : 46.68

Conclusion

La deuxième méthode est toujours sous-optimale (essayez-la sur la version originale de l items ). Elle est évidemment plus lente que la première mais donne de bien meilleurs résultats et ne nécessite même pas de tri préalable. (Pensez à utiliser un shuffle pour éviter les cas dégénérés).

Vous pouvez également jeter un coup d'œil à este . La méthode pour marquer le prochain domino possible consiste à mélanger un grand nombre de fois les dominos restants et à additionner les pertes pour chaque mélange. La perte cumulée minimale vous donnera probablement un bon prochain domino. Je n'ai pas essayé...