Couvrir optimal des éléments de matrice 2D donnés par des contraintes spatiales

Question

J'ai un problème particulier que je dois résoudre, mais je ne sais pas comment classer le problème ou choisir le bon algorithme pour le résoudre. J'espère que quelqu'un ici pourra me conduire dans la bonne direction.

J'ai généralisé et réduit le problème à cela:

Étant donné une matrice $ m times n $ avec des éléments dans $ {0, 1 } $, couvrez tous les éléments de 1 $ selon les règles suivantes:

• "Marquer" un élément couvre cet élément ainsi que les éléments directement au-dessus et en dessous
• Un maximum de $ frac {n} {2} $ Les éléments peuvent être marqués dans n'importe quelle rangée de la matrice

Tout en minimisant le nombre d'éléments de 1 $ qui sont couverts par un élément adjacent mais ne se sont pas marqués.

Par exemple,

Soit $ m = n = 4 $ et considérez la matrice suivante:

$ee

Parce que $ n = 4 $, seuls 2 éléments ou moins peuvent être marqués par rangée.

Une solution optimale est la suivante, où les éléments marqués sont indiqués en rouge, et les éléments couverts mais non marqués sont indiqués en bleu.

$ee {Red} {1} & 0 Color {Red} {1} & Color {Red} {1} & Color {Blue} {1} & Color {Blue} {1} 0 & 0 & 0 & Color {Red} {1} end {bMatrix} $$

Dans cette solution, il y a trois éléments de 1 $ qui sont couverts mais pas marqués (en bleu).

Pour ce problème, j'ai besoin d'une affectation réelle des marques pour chaque ligne, pas seulement du coût minimum final.

---

La relation spatiale entre les éléments voisins m'a initialement amené à réfléchir au problème en termes de graphique, j'ai donc essayé de le configurer comme un problème de flux maximum à coût minimum, mais je n'ai pas pu comprendre comment modéliser le graphique de flux.

Ensuite, j'ai commencé à étudier le couverture des sets et l'ILP, mais je ne sais pas comment spécifier la règle sur la relation entre les voisins verticaux comme contrainte.