Réduire le problème suivant à SAT

cs.stackexchange https://cs.stackexchange.com/questions/6521

Question

Voici le problème. Compte tenu de k $, n, T_1, \ ldots, T_M $, où chaque T_i $ \ subseteq \ {1, \ ldots, n \} $. Y at-il un sous-ensemble $ S \ subseteq \ {1, \ ldots, n \} $ avec la taille au plus k $ $ tel que $ S \ cap T_i \ neq \ emptyset $ pour tous $ i $? Je suis en train de réduire ce problème à SAT. Mon idée d'une solution serait d'avoir une variable $ x_i de $ pour chacun de 1 à $ n $. Pour chaque $ T_i $, créez une clause $ (x_ {i_1} \ Vee \ cdots \ Vee {x_ I_k}) $ si $ T_i = \ {i_1, \ ldots, I_k \} $. Ensuite, et toutes ces clauses ensemble. Mais cela est évidemment pas une solution complète car elle ne représente pas la contrainte $ S $ doit avoir au plus $ k éléments de $. Je sais que je dois créer plusieurs variables, mais je ne suis tout simplement pas sûr de savoir comment. J'ai donc deux questions:

  1. Mon idée de solution sur la bonne voie?
  2. Comment les nouvelles variables créés afin qu'ils puissent être utilisés pour représenter la contrainte cardinalité $ k $?
Était-ce utile?

La solution

Il semble que vous essayez de calculer une hypergraphe transversal de taille $ k $. C'est, $ \ {T_1, \ points, T_M \} $ est votre hypergraphe, et $ S $ est votre transversale. Une traduction standard est d'exprimer les clauses que vous avez, et traduire la limitation de la longueur dans une contrainte de cardinalité.

Il faut donc utiliser l'encodage existant, soit $ \ bigwedge_ {1 \ le j \ le m} \ bigvee_ {i \ in T_j} x_i $ et ajouter des clauses codant pour $ \ sum_ {1 \ le i \ le n} x_i \ le k $.

$ \ sum_ {1 \ le i \ le n} x_i \ le k $ est une contrainte de cardinalité. Il existe différentes traductions de contrainte de cardinalité en SAT.

Le plus simple mais grande traduction de contrainte de cardinalité est juste $ \ bigwedge_ {X \ subseteq \ {1, \ points, n \}, | X | = K + 1} \ bigvee_ {i \ X} \ neg x_i $. Ainsi, chaque contrainte représente la disjonction $ \ neg \ bigwedge_ {i \ X} x_i $ - pour tous les sous-ensembles $ X $ de $ \ {1, \ points, n \} $ de taille k + 1. C'est, nous nous assurons qu'il n'y a aucun moyen que plus de k variables peuvent être réglées. Notez que ce n'est pas la taille polynôme en k $ $

Quelques liens vers des documents sur les traductions de contrainte de cardinalité plus efficace de l'espace qui sont de taille polynomiale $ k $ :

Si vous êtes réellement intéressé à résoudre ces problèmes, peut-être il est préférable de les formuler comme des problèmes pseudo-booléennes (voir wiki article sur les problèmes pseudo-booléennes ) et l'utilisation solveurs pseudo-booléennes (voir pseudo-booléenne concurrence ). De cette façon, les contraintes de cardinalité ne sont que des contraintes pseudo-booléennes et font partie de la langue -., Espérons-le solveur pseudo-booléennes les gère ensuite directement et donc plus efficacement

Autres conseils

Si vous n'êtes pas tout à fait mettre sur la SAT normale, votre idée est déjà une réduction MIN-ONES (sur CNF positives), qui est essentiellement SAT, mais où vous pouvez définir au plus k $ variables $ true (strictement c'est la version d'optimisation où nous réduisons le nombre de vraies variables).

De même, si vous vous dirigez dans une direction complexité paramétrées, alors vous avez déjà obtenu essentiellement WSAT ($ \ gamma_ {2,1} ^ {+} $), où $ \ gamma_ {2,1} ^ {+} $ est la classe de toutes les formules CNF positives (comme avant, la notation pourrait aider vos enquêtes cependant). Dans ce cas, vous auriez à commencer à regarder ce paramétrage serait utile dans votre cas.

Je suppose que vous êtes à la recherche d'une réduction explicite, mais sinon, vous pouvez toujours revenir à la page

Non affilié à cs.stackexchange
scroll top