Trouver la plus courte combinaison de mots qui contient tous les caractères d'un ensemble spécifié

Question

J'ai un tableau (appelons-le a1) de mots (comme "chien", "poisson", "exécuter", "programmation" quoi que ce soit) qui est vraiment énorme .

Je peux combiner l'un des mots de a1 avec n'importe quel autre des mots (par exemple, vous pourriez combiner "dog" et "programmation" dans "dog-programming"), puis encore et encore, jusqu'à ce que les cordes vraiment gros. J'ai également obtenu un tableau (appelons-le a2) de chaînes (telles que "de", "s", "x", "umh", encore une fois, ils pourraient être à peu près tout). Il est garanti qu'il n'y a aucune chaîne dans a2 qui ne peut être trouvée dans aucune chaîne de a1. Ce que je cherche est la chaîne la plus courte (le plus court en termes de nombre de combinaisons pour créer cette chaîne, pas combien de caractères contient cette chaîne) qui contient toutes les chaînes dans a2. S'il y a plus d'une chaîne qui a toutes cette longueur minimale, je peux en choisir une, et renflouer le programme. Maintenant, je ne pense pas que je puisse juste forcer cela parce que même si les tableaux sont relativement petits, il y a des possibilités pratiquement infinies de combiner les mots, mais j'aimerais bien avoir tort!

Existe-t-il un bon moyen d'obtenir la chaîne la plus courte qui produira sûrement le résultat le plus court ou dois-je utiliser des algorithmes heuristiques pour simplement chercher des chaînes assez courtes? EDIT: J'ai essayé juste de choisir une chaîne de a1 qui couvrait la plupart des chaînes de a2, puis en supprimant ces éléments de a2 et en recommençant, mais cela ne fonctionne pas! Il donne de très bons résultats, mais pas le meilleur.

Answer 1

si vous combinez les mots avec un tiret comme dans votre exemple, par ex.

dog + programming + sky = dog-programming-sky 

ET les mots A2 ne contiennent pas des tirets, alors il est juste SET-COVER déguisé, un problème d'optimisation NP-complet. Vous pouvez ensuite résoudre le problème à l'aide de toute stratégie de solution disponible pour SET-COVER. Il existe un algorithme d'approximation rapide pour SET-COVER, mais si vous voulez avoir la plus petite solution absolue, vous devez recourir à un algorithme exponentiel du pire cas.

Si vous combinez les mots sans un tiret, par ex.

dog + programming + sky = dogprogrammingsky 

le problème est plus difficile, parce que maintenant par exemple "ogpro" se trouve dans le mot combiné même s'il ne s'agit pas d'une sous-chaîne de l'une des chaînes constituantes.