Geringste Anzahl markierter Symbole

Question

Ich habe ein 7x7-Raster, in dem ich die geringste Anzahl "markierter Positionen" finden möchte, damit eine Gruppe nicht markierter Positionen nicht größer als 4 ist (nur nach oben, unten, links und rechts und nicht diagonal). Unten finden Sie ein Beispiel mit einer Lösung für die Verwendung von 19 markierten Symbolen.

Kann jemand eine Lösung mit nur 18 oder weniger finden?

Answer 1

Ich erwarte, dass dies eine optimale Lösung ist, habe aber noch keinen Beweis dafür.

Es hat nur 17 markierte Quadrate.

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

Answer 2

Sie können dieses Set-Covering-Problem wie folgt durch ganzzahlige lineare Programmierung lösen. Für jeden Pentomino$p$, Lassen $C_p$sei die Menge von (fünf) Gitterzellen, aus denen es besteht. Für jede Gitterzelle$(i,j)$Lassen Sie binäre Entscheidungsvariable $x_{i,j}$Geben Sie an, ob diese Zelle markiert ist. Das Problem ist zu minimieren$\sum_{i,j} x_{i,j}$ unterliegt linearen Einschränkungen: $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all $p$}$$ Die optimalen Werte für $n\in\{1,\dots,10\}$sind \ 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 {matrix}