Complexité de l'homogénéisation d'une chaîne

Motivation : lors du développement d'outils de gestion des versions de données, nous avons fini par chercher des algorithmes pour «différencier» deux ensembles d'entiers, en proposant une séquence de transformations qui amènent un ensemble d'entiers à l'autre. Nous avons pu réduire ce problème au problème très naturel suivant qui semble avoir des connexions pour modifier la distance, le regroupement par échange et la partition de chaîne commune minimale .

Problème : On nous donne une chaîne, c'est-à-dire une séquence de lettres, et notre objectif est de l' homogénéiser à moindre coût. Autrement dit, nous voulons une séquence réarrangée de telle sorte que toutes les lettres qui se ressemblent sont côte à côte.

La seule opération autorisée est de récupérer une sous-séquence de lettres qui sont semblables et de déplacer cette sous-séquence n'importe où, et cela me coûte 1 unité.

Toute aide caractérisant la complexité de ce problème serait très appréciée!

Exemple :

• aabcdab: entrée
• bcd aa ab: après avoir déplacé le premier aa à la position juste après "d"
• b bcdaaa: après avoir déplacé le b de fin vers la première position

Puisque la chaîne résultante est homogène, nous avons un coût de 2.

Notez que nous ne sommes soumis à aucune contrainte en ce qui concerne la sortie: tant qu'elle est homogène, nous n'avons pas besoin de garantir un ordre spécifique.

Ce problème est NP-complet, par réduction de l' ensemble de frappe minimum .

En jeu minimum frapper, nous donne un univers, , et un ensemble d'ensembles tels que . L'objectif est de trouver de plus petite taille telle que tel que .$U$$S$$\forall s \in S, s \subset U$$H \subset U$$\forall s \in S, \exists h \in H$$h \in s$

La réduction est la suivante:

• La chaîne est la suivante: Pour chaque élément , il y aura deux caractères de la chaîne, . Entre ces caractères sera un caractère pour chaque tel que . Entre les paires de , il y aura des caractères uniques qui ne seront pas répétés dans la chaîne.$u \in U$$u'$$s'$$s \in S$$u \in s$$u'$

• Pour homogénéiser la chaîne, le caractère doit être déplacé fois, pour chaque . De plus, pour chaque , le caractère doit être déplacé une fois, à moins que chaque entre la paire de n'ait été déplacé ailleurs.| s | - 1 s u u ′ s ′ u $s'$$|s|-1$$s$$u$$u'$$s'$$u'$

• Par conséquent, pour minimiser le nombre de mouvements nécessaires pour homogénéiser la chaîne, nous souhaitons maximiser le nombre de telle sorte que chaque ait été déplacé ailleurs. Les où les n'ont pas été déplacés ailleurs doivent contenir ensemble un pour chaque , donc ils doivent pour un set de frappe. De plus, un tel ensemble de frappe peut servir de lieux de fin s, en déplaçant chaque vers le qui le frappe.s ′ u ′ s ′ s ′ s ∈ S s ′ s $u'$$s'$$u'$$s'$$s'$$s \in S$$s'$$s$$u$

• Ainsi, le nombre de mouvements pour homogénéiser cette chaîne est égal à, où est l'ensemble de frappe minimum.H $\sum |s| + |H^*|$$H^*$

Étant donné que le jeu de frappe minimum est NP-Hard, l'homogénéisation optimale d'une chaîne l'est également. Puisque les mouvements constituent un témoin, c'est NP-Complete.

Regardez le nombre de changements d'une lettre à l'autre dans votre chaîne, que vous pouvez voir comme une mesure de l'inhomogénéité de la chaîne. À chaque déplacement (utile) d'une sous-séquence, vous réduisez ce nombre de un si la sous-séquence que vous déplacez est précédée et suivie de deux lettres distinctes. Sinon, vous réduisez l'inhomogénéité de deux.

Donc, pour une chaîne avec k changements, vous avez besoin d'au plus k - l + 1 mouvements où l est le nombre de lettres différentes dans la chaîne, car à la fin l - 1 changements resteront. Comme une chaîne de longueur n peut avoir au plus n-1 changements de lettres, elle peut nécessiter au plus n - l mouvements. Le moins possible est la moitié de cela.

La meilleure stratégie semble donc rechercher des sous-séquences de la forme abbba et en éloigner le bbb. Quand il n'en reste plus, bougez quoi que ce soit. Vous pouvez toujours essayer de faire ces opérations qui créent de nouvelles situations d'abbba, mais je pense que le gain sera très faible. Étant donné que la pire stratégie possible (sans mouvements stupides qui augmentent l'inhomogénéité) utilise au plus deux fois plus de mouvements que l'optimal, le peu que vous pourriez gagner ne semble pas être en relation raisonnable avec l'effort comme la réponse de isaacg avec la caractérisation comme NP-hard suggère. À moins, bien sûr, que vous ne comptiez vraiment que le nombre d'opérations de déplacement et que vous ne vous souciez pas du temps pour décider des mouvements à effectuer.

Le pire des cas est donc une chaîne où chaque lettre est différente de son prédécesseur (et vous ne recevez aucun bonus abbba). Ici, vous avez besoin d'un certain nombre d'opérations linéaires dans la longueur de la chaîne et presque égales à cette longueur.

Dans votre exemple, vous avez 5 -> 4 -> 3 changements, et 3 est égal au nombre de lettres (4) moins 1.

Note latérale: Pour un alphabet de taille seulement deux, chaque mouvement qui ne déplace pas un préfixe ou un suffixe de la chaîne réduit l'inhomogénéité de deux et donc chaque séquence de mouvements raisonnables est optimale.