Fusion d'ensembles dans un graphe orienté

Question

Mon entrée est une liste d'ensembles d'entiers. Ce qui veut dire que chaque ensemble a un index dont j'ai besoin de suivre. Ces ensembles (uniques) contiennent des entiers et différents ensembles peuvent avoir un ou plusieurs de ces éléments entiers en commun (il est également possible que deux ensembles soient identiques).

Mon but est d'exprimer ces ensembles non pas comme une liste, mais plutôt comme une structure arborescente, afin que je puisse éliminer les éléments entiers qui sont partagés par plusieurs ensembles. La structure est un graphe orienté avec un noeud racine artificiel. Les autres nœuds sont les entiers trouvés dans les ensembles. Le nœud racine aura jusqu'à n enfants (n est le nombre de jeux). Ces enfants sont en fait un premier entier provenant des différents ensembles et doivent être ajoutés par l'algorithme. Il y a quelques conditions:

• Il doit être possible de recréer un tel ensemble en suivant un chemin à travers l'arbre.
• Un chemin à travers l'arbre doit être non ambigu, aucun sommet ne peut avoir plus d'un enfant.
• Il y a une exception: Le nœud racine artificielle est autorisé à avoir plusieurs enfants (les enfants seraient les points de départ pour les chemins pour recréer les ensembles)

De toute évidence, il ne sera pas possible d'éliminer tous les doublons, mais j'aimerais trouver un algorithme qui trouve le plus d'éliminations possible. C'est là que je dois demander de l'aide. Je peux le faire à la main, mais ne pas l'exprimer dans un algorithme formel qui fonctionnerait dans tous les cas).

Edit: Espérons que ce petit exemple illustre mieux le problème:

Nous avons trois listes, list0 = [0,3,4,7,8], list1 = [1,2,3,6,7], list3 = [5,6,7,8]. L'index de ces listes est la légende du premier tronçon à partir du nœud racine R. Suivre ce premier front conduit à un chemin non ambigu vers un nœud qui n'a pas d'enfants (dans cet exemple c'est le même nœud pour les trois listes, mais ce n'est pas forcément le cas). Toutes les légendes des noeuds sur ce chemin forment la liste avec l'index respectif.

Comme vous pouvez le voir, la valeur 7 apparaît trois fois, les valeurs 3, 6 et 8 chacune deux fois. Donc, le meilleur scénario serait de se débarrasser des 5 nœuds inutiles. Mais avec notre condition, qu'aucun nœud ne peut avoir plus d'un enfant, il n'est pas toujours possible de se débarrasser de tous les doublons. Le graphique ci-dessous montre une solution possible, où les 6 et 8 dupliqués n'ont pas pu être résolus. [remarque:. 6 ou 8 pourrait être échangé avec 3, et ont encore une solution de 12 noeuds]

Answer 1

Je ne sais pas d'un algorithme existant pour résoudre ce , mais je pense que je vois des attaques. Tout d'abord, retournez votre graphique et faites-en un arbre simple, avec comme racine. Ensuite, notez que vos "listes" ne sont pas ordonnées: elles fonctionneront mieux en tant qu'ensembles (en supposant qu'il n'y a pas de duplication de valeurs). Remarque: vous pouvez peut trivialement convertir ce problème en un seul problème - ajoutez simplement un nouveau symbole unique à chaque ensemble. Cela deviendra automatiquement le nœud racine. Maintenant, vous pouvez attaquer cela avec quelque chose de plus comme un arbre de décision. Un algorithme récursif pour un sous-arbre donnera des solutions disponibles.Votre préférence dont la décomposition à essayer en premier devrait être entraîné par heuristiques, comme

• la valeur qui apparaît le plus souvent dans les ensembles de sous-arbre
• le plus grand sous-ensemble commun de tous les ensembles.
• le sous-ensemble qui supprimera le plus d'éléments du problème. Par exemple, un sous-ensemble de 3 membres de 3 ensembles serait meilleur qu'un sous-ensemble de 4 membres de seulement 2 ensembles.

Ce dernier élément n'est pas quelque chose que vous résolvez dans CS 101, et ce n'est pas une solution optimale garantie sur le premier coup. Au cours des dernières 24 heures, je me suis surtout convaincu qu'il n'y avait pas d'attaque simple et simple pour obtenir une solution optimale pour tous les intrants.