Appariement des paires de skis

On cherche l’appariement optimal entre des skieurs et des paires de skis sachant que les skis les plus appropriés pour un skieur font sa taille. On note représente l’ensemble des tailles des skieurs et celui des paires de skis. S’il y a autant de paires que de skieurs, le problème revient à trouver la meilleure permutation qui minimise:

Dans ce cas, on montre que les paires de skis doivent être triées par ordre de croissant. Pour cela, on raisonne par l’absurde en supposant que cela n’est pas vrai. Donc il existe et tels que et . Si c’est possible, alors :

Si les paires de skis sont tous les deux plus petites que les tailles de skieurs ou l’inverse, les deux quantités sont égales. En revanche, si , alors :

C’est faux si . C’est aussi faux si car .

On en déduit que l’ordre importe peu lorsque toutes les paires sont plus ou plus petites que tous les skieurs mais que les paires ordonnées associées au skieurs ordonnés est la solution optimale lorsqu’il y a chevauchement.

Dans un premier temps, on implémente une solution par récurrence.

def appariement(tailles, skis):
    # tailles.sort()
    if len(tailles) == len(skis):
        skis.sort()
        return skis

    if len(tailles) == len(skis) - 1:
        # il suffit d'enlever une paire, on les essaye toute jusqu'à trouver
        # celle qui minimise l'appariement
        meilleur = None
        for p in range(len(skis)):
            app = appariement(tailles, skis[:p] + skis[p + 1 :])
            cout = sum([abs(t - s) for t, s in zip(tailles, app)])
            if meilleur is None or cout < meilleur:
                meilleur = cout
                meilleur_appariement = app
        return meilleur_appariement

    if len(tailles) <= len(skis) - 2:
        # il suffit d'enlever une paire, on les essaye toute jusqu'à trouver
        # celle qui minimise l'appariement
        meilleur = None
        for p in range(len(skis)):
            app = appariement(tailles, skis[:p] + skis[p + 1 :])
            cout = sum([abs(t - s) for t, s in zip(tailles, app)])
            if meilleur is None or cout < meilleur:
                meilleur = cout
                meilleur_appariement = app
        return meilleur_appariement
    return None


tailles = [5, 6, 3, 4, 4, 8]
skis = [5, 6, 3, 4, 4, 8, 7, 9]
print(appariement(tailles, skis))

[3, 4, 4, 5, 6, 8]

Il existe une solution au coût polynômial. On s’inspire de la distance d’édition. On définit les i premières tailles de skieurs triées par ordre croissant, les j premières paires triées par ordre croissant puis le coût d’appariement.

Si on ajoute un skieur, alors dans la meilleure solution, soit il est associé à la dernière paire, soit il ne l’est pas.

Il ne reste plus qu’à l’implémenter. L’appariement consiste à constuire le chemin qui permet d’atteindre le coût minimum.

---

Notebook on github