Minimo numero di simboli contrassegnati

Question

Ho una griglia 7x7, dove voglio trovare il minor numero di "posizioni contrassegnate", quindi un gruppo di posizioni non contrassegnate non è più grande di 4 (si muove solo su, giù, sinistra e destra e non diagonale). Di seguito è riportato un esempio con una soluzione utilizzando 19 simboli contrassegnati.

Qualcuno può trovare una soluzione utilizzando solo 18 o meno?

Answer 1

Mi aspetto che questa sia una soluzione ottimale, ma non ne ho ancora la prova.

Ha solo 17 quadrati contrassegnati.

. X . . . X .
 . . X . X . .
 . X . X . X .
 X . . X . . X
 . X . X . X .
 . . X . X . .
 . X . . . X .

Answer 2

È possibile risolvere questo problema di copertura degli insiemi tramite la programmazione lineare intera come segue. Per ogni pentomino$p$, permettere $C_p$essere l'insieme di (cinque) celle della griglia che lo compongono. Per ogni cella della griglia$(i,j)$, lascia la variabile di decisione binaria $x_{i,j}$indicare se quella cella è contrassegnata. Il problema è ridurre al minimo$\sum_{i,j} x_{i,j}$ soggetto a vincoli lineari: $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all $p$}$$ I valori ottimali per $n\in\{1,\dots,10\}$sono \ begin {matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \ hline \ min & 0 & 0 & 3 & 5 & 8 & 13 & 17 & 24 & 31 & 39 \\ \ end {matrice}