Tu dis:
"Une liste de pannes distinctes peuvent être identifiées en réalisant plusieurs tests : chaque test présente un coût, et permet de dire si une panne a lieu parmi plusieurs.
Le problème est de définir les tests à mener, pour identifier de façon certaine la panne à moindre coût"
Je comprends qu'il y a un test par panne
dans ce cas, tu es morte il faut tout faire.
Mais en suite, le fait de parler de couverture m'indique que ca ne doit pas etre le cas.
Ca doit plutot etre un probleme de couverture qui peut se formaliser comme cela:
k-Couverture:
Instance: un graphe G=(V,E), un entier K
Question: existe t'il A \subset V telque |A| <= K et V = AuN(A)
avec N(A) le voisinage de A
Je ne sais pas si ce probleme est NP-Complet mais etant donné la question, je le suppose. (Ca ressemble un peu a stable max)
On voit bien quel est le PB de maximisation associé:
Couverture Min:
Instance: Un graphe G=(V,E)
Solution: un ensemble A \subset V telque V = AuN(A)
Mesure: |A|
Comment resoudre ca:
bah, en effet par une methode de Branch and Bound.
tu dis qu'une solution c'est un vecteur P de taille |V|
P_i = 1 si i\in A 0 sinon
et tu branche sur toute les combinaisons possible avec une petite fonction d'evaluation, en fait je ne sais pas trop comment.
Mais un PLNE relaxé pourrait faire l'affaire.
eventuelement d'ailleurs tu peux faire une recherche dichotomique
tu cherche une solution de valeur |V|/2
si il y en as tu cherche a 3*|V|/4 sinon a |V|/4 etc...
apres tu peux peut etre te tourner vers les methodes heuristiques
Il doit exister de bonne heuristique pour ce probleme
a base de: selectionner le noeud de degre max, le prendre
ensuite tu continue en prenant le noeud voisin du plus de sommet non deja distribué. Ca a peut etre meme une performance garantie ca...
Tu peux confirmer l'enoncé formel de ton probleme ?
A problem has been detected and windows has been shut down to prevent damage to your computer
