griglia algoritmo di puzzle

Question

Ho una griglia di una certa larghezza e altezza, in cui ogni cella può essere di tre possibili valori (presentato come bianco, verde e rosso in questa figura):

illustration http://corexii.com/grid-algorithm-problem-2.png

È possibile selezionare qualsiasi numero di cellule verdi (contrassegnato blu nell'illustrazione di seguito), che copre tutti i globuli rossi (contrassegnati giallo) in un predeterminato raggioquadrato (qui) intorno alle celle selezionate:

illustration http://corexii.com/grid-algorithm-problem-3.png

L'obiettivo è quello di:

• coprire il maggior numero di globuli rossi come possibile
• con il minor numero cellule blu possibile
• farlo il più velocemente possibile

Qualcuno ha qualche idee per un algoritmo?

Sto guardando molta teoria, ma quello che mi interessa di più è un'approssimazione per fare questo rapidamente piuttosto che con precisione. Un risultato veloce e ragionevole è preferibile al calcolo di quello ottimale per tutto il giorno.

(Le illustrazioni sopra possono presentare la più normale distribuzione di queste cellule, ma non devono essere considerati come assomigliare tutte le possibili distribuzioni.)

Answer 1

Questo problema è un caso speciale dell'importante NP-hard set cover problem . (L'universo è costituito da celle rosse e ogni insieme è costituito da celle rosse nel raggio di una delle celle verdi). Il greedy algorithm entra in un registro n fattore del risultato ottimale.

---

templatetypedef is right to point out che il fatto che questo problema è un caso speciale di un problema NP-hard non dimostra che in realtà è NP-hard troppo. Ecco perché sono stato attento nel mio fraseggio sopra a non implicare il secondo. Ma essere un caso speciale di un problema NP-duro è un segnale che non dovrebbe essere ignorato: molti casi speciali si rivelano ulteriori indagini per essere NP-hard stessi.

Quindi ecco uno schizzo approssimativo che questo problema è in realtà NP-hard, da una riduzione da VERTEX COPERTURA PER GRAFICI PLANARI DI GRADO A PIÙ DI QUATTRO.

Supponiamo di avere un grafo planare del grado massimo di quattro, per esempio:

rappresentare ogni vertice da un quadrato verde, e ciascun bordo da una catena alternata di quadrati rossi e verdi tali che ci sono un numero pari di quadrati verdi, un numero dispari di quadrati rossi, e ogni quadrato verde coprirà solo i due quadrati rossi su entrambi i lati, se scelto.Con un raggio di 2, questa è una possibile rappresentazione del grafico:

Per coprire tutti i quadrati rossi, dobbiamo scegliere almeno la metà dei quadrati verdi su ogni catena corrispondente ad un bordo il grafico originale. Se scegliamo esattamente la metà dei quadrati verdi su ciascuna catena, questo lascia un quadrato rosso scoperto a un'estremità di ciascun bordo (e possiamo scegliere quale fine). Quindi otteniamo il set minimo di quadrati verdi se riusciamo a trovare il set minimo di vertici in modo tale che ogni spigolo sia incidente a un vertice in quel set.

Nell'esempio, possiamo coprire i quadrati rossi utilizzando otto quadrati verdi se prendiamo vertici un e d:

E questo corrisponde alla copertura minima vertice nel originale grafico: