Recherche d'un sous-ensemble minimal d'objets avec des attributs.

Question

J'ai un problème algorithmique. Je ne sais pas comment le résoudre. Peut-être quelqu'un peut me aider?

J'ai des objets. Chaque objet a les mêmes caractéristiques. Il pourrait être illustré dans le tableau:

    Feature1 Feature2 Feature3 Feature4 
     Object1  1   0   1   1 

     Object2  0   0   0   1 

     Object3  0   1   1   1 

     Object4  0   1   0   0 

Maintenant, je veux trouver tous les sous-ensembles minimum d'objets. Chaque sous-ensemble doit avoir au moins une valeur "1" pour chaque entité. Pour le tableau ci-dessus, les résultats sont deux sous-ensembles: {Object1, Object3} et {Object1, Object4}. Je ne peux pas générer tous les sous-ensembles possibles car cela pourrait prendre trop de temps.

Answer 1

C'est exactement le set cover problem. Le problème est NP-difficile, donc si vous avez besoin de exactement minimum, la génération de tous les sous-ensembles possibles ne serait pas pire que d'autres solutions dans le temps.

Mais il existe quelques algorithmes d'approximation temporelle polynomiale. Voir la page Wikipedia pour plus de détails. Le « meilleur » est l'algorithme glouton, qui fonctionne comme ceci:

1. Initialiser les fonctions non implémentées comme {Feature1, Feature2, Caractéristique3, ...}
2. Sélectionnez l'objet qui implémente des fonctionnalités les plus inappliquées.
3. Répétez 2 jusqu'à ce que toutes les fonctionnalités soient implémentées.

Answer 2

Vous pouvez réduire le problème en incluant par nécessité tous les objets qui sont les seuls à posséder une ou plusieurs caractéristiques. Object1 est le seul qui a Feature1 donc vous savez que vous avez besoin de celui-ci dans votre solution.