Généraliser l'algorithme pour le carrelage domino?

Ce problème est définitivement NP-hard et je peux le prouver. Il y a une réduction de 3-SAT à ce problème. Plus précisément, c'est une réduction de 3-SAT au sous-problème de ce problème dans lequel les dominos sont 1x3. Il peut aussi y avoir d'autres réductions pour d'autres tailles, mais celui-ci fonctionne bien.

Essentiellement, dans cette réduction, nous allons utiliser des positions domino pour encoder vrai ou faux. En particulier, je vais adopter la même notation que l'autre solution, c'est-à-dire que je vais utiliser des astérisques pour indiquer les espaces ouverts sur la grille. Je vais également utiliser des ensembles de trois lettres majuscules pour représenter les dominos et les lettres minuscules pour représenter les "signaux" qui sont des espaces qui peuvent ou non être remplis en fonction de l'état du système.

Pour intégrer un problème 3-SAT dans cet espace, nous allons avoir besoin d'un ensemble de ce que j'appellerai des gadgets qui ne permettent que certains États d'être possibles. La plupart de ces gadgets auront un nombre fixe de dominos en eux. L'exception sera les gadgets qui représentent les clauses qui auront un domino supplémentaire si la clause est vraie (satisfaite) mais pas quand elle est fausse (insatisfaite). Nous pouvons interconnecter ces gadgets en utilisant des chemins. Ensemble, cela nous permettra de construire un circuit 3-SAT. Nous aurons un nombre de base de dominos puisque chaque chemin et gadget prendra une quantité standard de dominos, nous pouvons les ajouter pour obtenir un numéro de base k et chaque gadget de clause peut avoir un domino supplémentaire si c'est vrai, donc si toutes les clauses peuvent être rendues vraies (et donc l'expression satisfaite) et qu'il y a n clauses, alors le nombre maximum de dominos sera n+K. sinon, le nombre maximum sera inférieur à n+k. C'est la forme de base de la réduction. Ensuite, je vais décrire les gadgets et donner des exemples.

Semblable à l'autre Réponse, Nous allons avoir deux positions qui encodent true et false pour une variable donnée. Donc, je vais commencer par une seule tuile qui peut être dans deux possibles lieu.

****

Cela peut soit être recouvert d'un domino comme

AAA* or *AAA

Évidemment, cela ne peut pas être recouvert de 2 dominos et le couvrir de 0 dominos ne serait jamais maximal. Pour mes besoins, nous allons considérer une saillie pour représenter la valeur "false "et un manque de saillie pour représenter"true". Nous pouvons donc considérer cette partie comme ayant deux signaux porteurs:

x**y

Et dans ce cas, un seul de x ou y sera couvert, donc nous pouvons considérer les signaux être x et la logique non de X. Pour nos besoins, celui qui est couvert est faux, celui qui n'est pas couvert est vrai. Ensuite, nous pouvons transmettre des signaux simplement à travers des chemins courbes droites. Si nous avons

x*****y

Nous aurons à nouveau exactement deux dominos et aboutirons à ce que x ou y soient couverts, mais pas les deux.

***y
*
*
x

Aura exactement le même comportement. Nous pouvons donc l'utiliser pour créer des chemins longs et incurvés dans des longueurs qui sont des incréments de 3. Cependant, pas toutes les longueurs nous pourrait vouloir utiliser des incréments de 3, nous avons donc besoin d'un gadget supplémentaire pour déplacer une distance différente. J'appelle cela le gadget fiddler et son seul but est de déplacer le signal des distances légèrement inégales pour que les choses se connectent avec succès. Son entrée provient de x et la sortie va à y et il transmet simplement le même signal le long. Il ressemble à ceci:

 ***y
 *
**x

, Il contient toujours exactement deux dominos et est rempli dans l'une des deux façons suivantes:

 BBB*     ABBB
 *        A   
AAA      *AX  

Si nous allons modèle 3-SAT, cependant, nous avons besoin de plus que cela. Plus précisément, nous avons besoin d'un moyen de modéliser les clauses. Pour ce faire, nous avons un gadget où un domino supplémentaire peut être emballé si la clause est vraie. La clause sera vraie lorsqu'une ou plusieurs de ses entrées sont vraies. Dans ce cas, cela signifie que nous pouvons emballer un domino supplémentaire quand au moins une des entrées ne dépasse pas. Cela ressemblera à ceci:

*x*y*
  *
  z

Si nous ajoutons un chemin supplémentaire à chacun pour plus de clarté, alors cela ressemble à ce:

 * *
 * *
 * *
*****
  *
  ****

Si x, y et z sont tous faux, alors ils auront tous des protubérances et ils seront remplis comme ce:

 A B
 C D
 C D
*C*D*
  *
  EEEF

Où le reste des dominos A, B et F continuent sur un chemin quelque part. Si au moins une des entrées est vraie, alors nous pouvons emballer dans un domino supplémentaire (G) comme ceci:

 C B         A D         A B
 C D         C D         C D
 C D    or   C D    or   C D
GGGD*       *CGGG       *CGD*
  *           *           G
  EEEF        EEEF        GEEE

Cependant, même si toutes les entrées sont vraies, alors nous ne pouvons pas emballer dans plus d'un domino. Ce scénario ressemblerait à ceci:

 C D
 C D
 C D
*****
  *
  *EEE

Et comme vous pouvez le voir, nous ne pouvons insérer exactement un domino dans l'espace vide, pas deux.

Maintenant, si les Termes n'étaient jamais répétés, alors nous serions terminés (ou presque). Cependant, ils peuvent être répétés, donc ensuite, nous avons besoin d'un séparateur de signal afin qu'une variable puisse apparaître dans plusieurs termes. Pour ce faire, nous utilisons le gadget suivant:

y*** ***z
   * *
   ***
   ***
    x

Dans ce gadget x est l'entrée et y et z sont les sorties. Dans ce gadget, nous pouvons toujours emballer 5 dominos. Si x dépasse de l'emballage 5 dominos seront toujours exiger couvrant y et z ainsi. Si x ne dépasse pas, il n'est pas nécessaire de couvrir y et z. L'emballage, où x ne dépasse pas ressemble à ceci:

yAAA BBBz
   C D  
   CED 
   CED  
    E 

Lorsque x fait saillie (nous utilisons X pour indiquer la fin du domino faisant saillie dans l'Espace x), l'emballage maximal couvre nécessairement à la fois y et z:

AAAC DBBB
   C D
   C*D
   EEE
    X

Je vais prendre un moment pour noter qu'il serait possible d'emballer cela avec cinq dominos lorsque x ne dépasse pas de telle sorte que y ou z dépassent. Cependant, cela entraînerait des termes qui pourraient être vrais (pas en saillie) devenant faux (en saillie). Permettre à certains termes (pas des variables, mais des termes réels dans les clauses) de ne différer en valeur qu'en devenant faux inutilement n'aura jamais pour résultat de satisfaire une expression autrement non satisfaisante. Si notre expression 3-SAT était (x / y / z) & (!x | y | !z) permettant alors à la fois x et !x faux ne ferait que rendre les choses plus difficiles. Si nous devions permettre aux deux extrémités de quelque chose d'être certes, cela entraînerait des solutions incorrectes, mais nous ne le faisons pas dans ce schéma. Pour l'encadrer en termes de notre problème spécifique, faire saillie inutilement n'entraînera jamais plus de dominos pouvant être emballés plus tard dans la ligne.

Avec les chemins et ces trois gadgets, nous pouvons maintenant résoudre planaire 3-SAT, qui serait le sous-problème de 3-SAT où si nous dessinons un graphique où les Termes et les clauses sont des sommets et il y a un bord entre chaque terme et chaque clause qui contient ce terme, que le graphique est planaire. Je crois que planar 3-SAT est probablement NP-dur parce que planar 1-en-3-SAT est, mais au cas où ce n'est pas le cas, nous pouvons utiliser des gadgets pour faire un croisement de signal. Mais c'est vraiment assez complexe (si quelqu'un voit un moyen plus simple, faites-le moi savoir) donc d'abord je vais faire un exemple de résolution de planar 3-SAT avec ce système.

Donc, un simple problème planaire 3-SAT serait (x | y / z) & (!x | y | !Z). Évidemment, c'est satisfaisant, en utilisant n'importe quelle affectation où y est vrai ou plusieurs autres missions. Nous allons construire notre problème de dominos ainsi:

    *******
    *     *
    *     *
 ****   ***
 *       *
***      ****
  *         *
  *         *        
  * ******* *
  * *     * *
  * *     * *
 *z*x*   *****
   *       *
   **** ****
      * *
      ***
      ***
       *
       *
       *           
       y

Notez que nous avons dû utiliser des violoneux au sommet pour que les choses soient correctement espacées, sinon cela aurait été beaucoup moins complexe.

Additionnant le total des Dominos des gadgets et des chemins, nous avons 1 séparateur (5 dominos), deux violoneux (2 dominos chacun), et un total de 13 chemins réguliers, pour un total de 5 + 2*2 + 13 = 22 dominos garantis, même si les clauses ne peuvent être satisfaites. Si ils peuvent être, alors nous aurons plus de 2 dominos qui peuvent être remplis, pour un total de 24. Un emballage optimal avec 24 dominos est le suivant:

    QRRRSSS
    Q     T
    Q     T
 OPPP   *UT
 O       U
*ON      UVVV
  N         W
  N         W        
  M IIIJJJK W
  M H     K X
  M H     K X
 *zGH*   LLLX*
   G       *
   GEEE FFF*
      B D
      BCD
      BCD
       C
       A
       A
       A

Ce carrelage contient 24 dominos, donc nous pouvons savoir que l'expression originale est satisfiable. Dans ce cas, le carrelage correspond à y et x true et z false. Notez que ce n'est pas le seul carrelage (et pas la seule affectation satisfaisante des valeurs booléennes), mais qu'il n'y a pas d'autre carrelage qui augmentera le nombre de tuiles au-delà de 24, Il est donc un carrelage maximum. (Si vous ne voulez pas compter tous les dominos, vous pouvez noter que j'ai utilisé toutes les lettres sauf Y et Z.)

Si le carrelage maximal avait contenu 22 ou 23 dominos, alors nous saurions que l'une des clauses n'était pas satisfaite (les dominos GGG et / ou LLL ne pourraient pas être placés) et nous saurions donc que l'expression originale n'était pas satisfaisante.

Pour être certain que nous pouvons le faire même si planar 3-SAT n'est pas NP-hard, nous pouvons construire un gadget qui permet aux chemins de se croiser. Ce gadget est malheureusement un peu grand et complexe, mais c'est le plus petit que j'ai pu comprendre. Je vais d'abord décrire les pièces, puis tout le gadget.

Pièce 1: point de croisement. x et y sont entrées. a,b,et c sont les sorties. Ils devront être combinés en utilisant d'autres gadgets pour relayer réellement x et y du côté opposé l'un de l'autre.

   ***c
   *
  ***
  * *
  * *
  * *
  ***
  ***
 ax*yb

Ce gadget s'adaptera toujours exactement 7 Domino. Il existe quatre combinaisons d'entrées possibles. Si aucune entrée ne dépasse (les deux sont vraies), aucune sortie ne dépasse et elle sera remplie comme dans (tt1) ou (tt2) ci-dessous. Si seule l'entrée x fait saillie, seul c fera saillie comme dans (ft) ci-dessous. Si seule l'entrée y fait saillie, la sortie a ou c fera saillie comme dans (tf) ci-dessous. Et si l'entrée x et y font tous deux saillie, la sortie c fait saillie comme dans (ff) ci-dessous.

 (tt) AAAc         (ft) AAAc         (tf) AAAc         (ff) BAAA     
      *                 *                 *                 B        
     BBB               BBB               BBB               CBD       
     C D               C D               C D               C D       
     C D               C D               C D               C D       
     C D               C D               C D               E G       
     EEE               EEE               EEE               EFG       
     FFF               FFF               FFF               EFG       
    aGGGb             aXGGG             GGGYb             aXFYb      

Je n'ai pas inclus la possibilité que dans le (ft) ou (tf) scénarios que c pourrait être couvert au lieu de a ou B. Cela est possible dans le cadre de ce gadget, mais une fois combiné avec d'autres gadgets pour former le croisement complet, si elle devait le faire, il ne se traduirait jamais par un plus grand nombre de clauses étant satisfait afin que nous puissions l'exclure. Avec cela à l'esprit, nous pouvons alors observer que, dans ce cas, la valeur de l'entrée x est égal à la valeur de b & c et l'entrée y est égale à la valeur de a & c (notez que ce serait logique, ou plutôt que logique et si la protrusion était considérée comme vraie plutôt que fausse). Nous avons donc juste besoin de diviser c et ensuite utiliser un gadget logique et pour connecter connecter les valeurs de c avec A et B respectivement et nous aurons alors terminé avec succès notre croisement.

La logique et est notre gadget le plus simple jusqu'à présent et il ressemble à ceci:

  ****
  *
 x*y

Vous remarquerez peut-être qu'il y en a un intégré vers le haut du gadget crossover point. Ce gadget contiendra toujours précisément 2 Domino. On sera en haut pour servir de sortie. L'autre Sert de commutateur qui ne sera orienté horizontalement que si x et y sont tous deux vrais (non saillants) et orientés verticalement sinon comme nous pouvons le voir dans les diagrammes suivants:

 BBB*     ABBB     ABBB     ABBB
 *        A        A        A   
AAA      XAy      xAY      XAY  

Ainsi, nous pouvons compléter le crossover en divisant c, puis en ajoutant deux de ces portes, une pour a & c et une pour b & C. mettre tout cela ensemble nécessite également d'ajouter des gadgets fiddler et ressemble à ce:

             ******* ****
             *     * *  *
             *     ***  *
            ***    *** ***
              *     *  *
           ****     *  ****
           *        *     *
           *     ****     *
          ***    *       ***
            *   ***      *
         ****   * *      ****
    y    *      * *         *    x
    *    *      * *         *    *
    * ****      ***         **** *
    ***         ***            ***
      **********x*y*************

Je ne vais pas remplir d'exemples de carrelages pour cela. Vous devrez le faire vous-même si vous voulez le voir en action. Donc, hourra! Nous pouvons maintenant faire arbitraire 3-SAT. Je devrais prendre un moment pour noter que faire cela sera une transformation du temps polynomial parce que même dans le pire des cas, nous pouvons juste faire une grande grille avec toutes les variables et leurs opposés le long du dessus et tous les Termes sur le côté et faire des croisements O(N^2). Il y a donc un temps polynomial simple algorithme pour poser tout cela et la taille maximale du problème transformé est polynomiale dans la taille du problème d'entrée. QED.

---

Modifier la note: Suite à L'excellent travail de Tom Sirgedas pour trouver une erreur dans le gadget splitter, j'ai apporté quelques modifications à la réponse. Essentiellement, mon vieux séparateur ressemblait à ceci et pouvait être emballé avec 6 quand x ne dépasse pas (plutôt que le 5 que j'avais prévu) comme ceci:

y*** ***z   AAAC DBBB
   * *         C D
   ***         C*D
   ***         EEE
   *x*         FFF

Donc je l'ai révisé en supprimant les deux espaces de chaque côté de X. Ceci élimine l'emballage de six dominos tout en permettant un emballage de 5 dominos dans lequel y et z sont découverts lorsque x est découvert.