Posizionare gli arcieri sulla parete

Question

Ho una matrice (con 0 e 1), che rappresenta un muro del castello e i suoi dintorni.

Il mio compito è di posizionare gli arcieri sulla parete in modo che coprano quanto più è possibile. Ci sono due regole:

: Ogni arciere ha gamma 1 - che significa, si può sparare solo su tessere adiacenti (ogni tessera ha 8-vicini di casa), che non sono a parete (fuoco amico è vietato in questo esercito!).

: Se accade, che più arcieri possono sparare alla stessa tessera, quella tessera conta come una sola.

Sto lottando per trovare una soluzione efficace per questo, in parte perché non lo so, se esiste in tempo polinomiale. C'è qualche?

Credo che il primo passo sia l'uso dell'algoritmo BFS per valutare ogni piastrella sulla matrice, ma non so come risolverlo con la seconda regola. La soluzione della forza bruta è abbastanza semplice: valuta tutte le posizioni e poi provale tutte, il che sarebbe molto poco efficace - penso che O (| possibili posizionamenti |^n), che non è bello.

semplice esempio:

Le piastrelle di colore grigio rappresenta la parete. I numeri all'interno di una tessera rappresentano la copertura dell'arciere piazzato su quella tessera. Giusto per essere sicuro, ho aggiunto quelli arancioni, che rappresentano la copertura dell'arciere in piedi sulla tessera b2. E l'ultima informazione - la soluzione corretta per questo è b2 e b6, con copertura di 14. Non può essere b2 e b4, perché copre solo 11 tessere.

Answer 1

non vedo come il problema può essere risolto in tempo polinomiale garantito, ma è possibile esprimere il problema come un programma intero lineare, che può essere risolto utilizzando un risolutore ILP come GLPK.

Lasciate c[i] essere 0-1 variabili intere, una per ogni quadrato di circostante. Questi rappresenteranno se questo quadrato è coperto da almeno un arciere.

Lasciate a[i] essere 0-1 variabili intere, una per ogni quadrato del muro del castello. Questi rappresenteranno se un arciere si trova su questa piazza.

Ci deve essere al massimo n arcieri: sum(a[i] for i in castle walls) <= n

Il c[i] deve essere zero se non c'è arciere adiacente: sum(a[j] for j castle wall adjacent to i) >= c[i] obiettivo

L'ottimizzazione è la massimizzazione sum(c[i]).

Ad esempio, supponiamo che questa sia la mappa (dove . è circondata e # muro del castello) e desideri posizionare due arcieri.

.... 
.### 
.... 

Quindi abbiamo questo problema ILP, in cui tutte le variabili sono 0-1 variabili intere.

maximize (
     c[0,0] + c[0,1] + c[0,2] + c[0,3] 
    + c[1,0] 
    + c[2,0] + c[2,1] + c[2,2] + c[2,3]) 

such that: 

a[1,1] + a[1,2] + a[1,3] <= 2 

c[0,0] <= a[1,1] 
c[0,1] <= a[1,1] + a[1,2] 
c[0,2] <= a[1,1] + a[1,2] + a[1,3] 
c[0,3] <= a[1,2] + a[1,3] 
c[1,0] <= a[1,1] 
c[2,0] <= a[1,1] 
c[2,1] <= a[1,1] + a[1,2] 
c[2,2] <= a[1,1] + a[1,2] + a[1,3] 
c[2,3] <= a[1,2] + a[1,3]