une variation sur la couverture de jeu

Question

Le problème d'optimisation de la couverture de jeu est: étant donné un univers U et un ensemble S de sous-ensembles de U (ie S \ subsetof 2^U), trouver le sous-ensemble minimal C de S de telle sorte que l'union de son éléments est U. Connu pour être NP-difficile.

La variation Je suis intéressé est, étant donné les mêmes choses (U et S), trouver le sous-ensemble minimal C de S telle que C est une couverture, et aussi pour un élément (non spécifié) u dans U, tous les jeux en S contenant u sont en C.

Le problème que je application à c'est: étant donné un ensemble de symptômes que je vois (U), je les causes possibles de ces problèmes (S - chaque élément de S est correspond à une « cause » de potentiellement symptômes multiples). Je veux le plus petit nombre de causes qui peuvent causer tous les symptômes que je vois, et je veux aussi avoir le résultat que la suppression de tous ces "causes" causera également au moins un symptôme à résoudre.

Est-ce que quelqu'un a des bonnes idées pour savoir si c'est plus facile que le problème original?

EDIT pour inclure la solution (intégrant commentaires)

Il est au moins aussi dur que la couverture de jeu.

SetCover(U,S) peut être résolu via SetCoverNew(U + {w}, S + {{w}}) avec w étant un élément non U et + désignant l'union de consigne.

Toute solution de l'instance SetCoverNew donnée doit inclure l'ensemble {w} (sinon ce n'est pas une couverture de U + {w}). Il est revendiqué qu'une solution du SetCover(U,S) est X = SetCoverNew(...) \ {{w}}. Tout d'abord, X doit être une couverture de U, sinon X + {{w}} ne peut pas être une couverture de U + {w}. Deuxièmement, X doit être une couverture minimale de U, sinon, SetCover(U,S) + {{w}} est une couverture de cardinalité inférieure à SetCoverNew(...).

Answer 1

Ceci est également NP-difficile puisque nous pouvons résoudre le problème de couverture de jeu d'origine en utilisant celui-ci. Supposons qu'on nous fournisse un algorithme pour résoudre ce nouveau problème (appelé SetCoverNew).

Voici un algorithme pour résoudre SetCover.

SetCover(U, S) 
    1. build new universe U1 = {U + w} (w is not in `U`, and `+` means `union`). 
    2. build the new set S1 = S + {w}. 
    3. result = SetCoverNew(U1, S1, w) 
    4. return result - {w}. 

EDIT désolé, je ne l'ai pas vu la unspecified u permettez-moi y réfléchir :)

Answer 2

Il y a quelque temps, je regardai le problème de travailler ce qui se passait mal dans un réseau de télécommunications, donné divers rapports à partir des nœuds. L'exigence consistait à attribuer quelques causes profondes pouvant expliquer un nombre potentiellement élevé d'alarmes (tempêtes d'alarme). Il existe un certain nombre de produits (très coûteux), qui adoptent une grande variété d'approches.J'ai décidé que le problème était si théoriquement intraitable que la seule façon pratique de l'aborder était d'organiser la collecte des données de façon à ce que le problème de savoir où les problèmes commençaient à être trivial (par exemple, s'assurer que chaque nœud pensait que c'était en train de faire et si c'était à travers les nœuds sur lesquels il comptait faire son travail). Compte tenu de cela, je pense que vous devriez être en mesure d'attribuer la plupart des alarmes aux causes profondes simplement en soustrayant les alarmes que vous attendez d'être produites par les causes profondes de votre instrumentation, vous êtes évidemment là.

Je ne sais pas quel est votre domaine de problème, mais je suggère que vous preniez un certain temps pour voir si la collecte des bonnes données facilitera le diagnostic.