Domanda:
Giochiamo un po' al campo minato?
Genus [CMA] autospeso
2010-04-20 12:42:53 UTC
Ho trovato un piccolo lasso di tempo per connettermi e postare una domanda che non mi sento di liquidare come banale. Confesso di non averci pensato più di tanto: se mi lascio attanagliare da questi problemini, ho finito di studiare. XD

Serve la conoscenza delle regole del campo minato (chiamasi "prato fiorito" per chi usa windows: ovviamente, pestare i fiori è estremamente pericoloso, non fatelo! XD)

Immaginiamoci prima una situazione più semplice: un campo 10 x 10, con 10 mine.
Come sapete, ogni casella reca un numero (o non ne reca, che equivale a 0) che conta le mine ad essa adiacenti.

Ciò che voglio considerare, data una disposizione delle 10 mine, è la somma dei numeri di tutte le caselle (assegnando il valore 0 alla mina, per convenzione).

Trovare delle configurazioni che minimizzano la somma è estremamente semplice: basta "ammucchiare" le mine nell'angolino.
Quest'idea si può formalizzare meglio, d'accordo, ma non è questo il problema.

Mi interessano piuttosto eventuali configurazioni che massimizzino questa quantità.
Qual è una disposizione - e perchè? - che massimizzi la somma cercata?


Più in generale, data una matrice m x n e k mine (con k < mn, ovviamente), esiste un algoritmo "standard" per individuare la configurazione (o una configurazione, dato che di sicuro non è unica) che massimizzi ∑a_i,j al variare di i <=m e j <=n?


Prima di darvi la parola, voglio sottolineare che questo è un problema estremamente semplice se lo si affronta con un calcolatore. E' oltretutto facilissimo implementarlo, anche se per grandi valori di m ed n potrebbe essere computazionalmente pesante (a meno di implementazioni particolarmente geniali e leggere).
Ciò che a me interessa è un approccio il meno possibile enumerativo al problema (cioè, non informatico).


Grazie per l'attenzione.
Tre risposte:
ag77
2010-04-24 03:13:54 UTC
tutto dovrebbe magicamente funzionare con queste due formule:

1) il numero minimo di mine che permette di arrivare alla somma massima è ottenibile, in una matrice NxM, con questa formula:

INT(MAX(N,M)/2)*(MIN(N,M))



2) è possibile calcolare anche la somma massima ottenibile, con questa seconda formula (valida per N,M>=2):

=((2+2)+(MIN(N,M)-2)*3)*(MAX(N,M)-1)



le formule si basano sull'allineamento consecutivo delle mine a colonne (o righe) alternate, che rappresentano l'allocazione ottimale di mine

spiego come sono arrivato a questo risultato passo passo, prima di tutto grazie alle risposte precedenti. Partendo da uno schema vuoto l'aggiunta di una mina da un valore aggiuntivo massimo di 8 se non si trova sui bordi. Se però non si parte da uno schema vuoto, occorre sottrarre a questo valore potenziale massimo di una mina in più il numero delle mine vicine *2 (uno, perchè la casella dove c'è la mina vale 0 quindi si perde il numero presente in questa casella; due, perchè tra tutte le caselle vicine ci sono degli spazi già occupati)



In uno schema 2x2, con una mina avreste una somma massima di 3, ma potete aggiungere una seconda mina, ovunque, raggiungendo la somma massima di 4

In uno schema 2x3, la soluzione ottimale che è quella di piazzare le 2 mine in questo modo (indico le mine con la lettera X, vicino segno i numeri del campo minato)

2 X 2

2 X 2

si può arrivare a questa allocazione utilizzando il concetto di "valore marginale" della mina che andate ad aggiungere, scegliendo di aggiungerla man mano laddove l'apporto marginale è massimo.

Lo schema iniziale è vuoto

0 0 0

0 0 0

le posizioni centrali sono quelle con il maggior valore marginale (5). posiziono la prima:

1 X 1

1 1 1

a questo punto mi chiedo se posso aggiungere un ulteriore mina e dove. aggiungerla allineata alla prima è la scelta migliore perchè ha ancora 4 celle vicine, e perdo solo un 1 (apporto marginale = 3)

2 X 2

2 X 2

aggiungere un ulteriore mina sarebbe un danno perchè ciascuna delle celle vuote rimaste ha un unico spazio libero vicino rimasto e costerebbe però la perdita di un 2 (apporto marginale = -1, mi fermo)



in una matrice 3 x3, conviene partire dalla posizione centrale, e rifacendo il ragionamento di prima potete vedere che l'allineamento delle successive mine è la scelta migliore

2 X 2

3 X 3

2 X 2

con somma complessiva pari a 14 (in questo caso essendoci simmetria è ovviamente equivalente mettere le tre X in orizzontale nella seconda riga)

qui però è interessante osservare che vi sarebbe anche una combinazione con 6 mine che porterebbe alla stessa somma pari a 14, e cioè questa:

X 4 X

X 6 X

X 4 X

ecco perchè nella prima formula ho specificato che si tratta del numero MINIMO di mine che porta alla somma massima.. questo implica anche che l'"approccio marginale" illustrato sopra non porta necessariamente all'unica soluzione ottimale e non pare ahimé generalizzabile.. in nessun caso invece è totalizzare più di 14 come somma massima



in una matrice 3 x 4:

2 X 4 X

3 X 6 X

2 X 4 X

con somma complessiva 21



in questo caso della 3x 4, è fondamentale la scelta di allineare le mine in verticale e non in orizzontale, dove avremmo due mine in meno ma totalizzeremo "solo" 20!



2 3 3 2

X X X X

2 3 3 2



e così via per matrici più ampie la situazione non cambia e il ragionamento si può generalizzare

l'importante è che quando N e M non sono uguali, occorre fare il numero maggiore possibile di file alternate di mine, da qui la prima parte della formula INT(MAX(N,M)/2). In una 3x4, allineando per colonna riesco a fare 2 file, per riga solo una, quindi scelgo l'allineamento mine in verticale. La seconda parte della formula moltiplica per l'altro lato della matrice, quindi questa volta il valore minimo tra N e M



il calcolo della somma (formula 2) poi è la diretta conseguenza del fatto che abbiamo allineamenti perfetti di mine, per cui troveremo sempre file di numeri rappresentate, sui bordi, da 2-3...-2 (con l'incognita rappresentata dal numero di 3, che dipende dalla grandezza della matrice, e più precisamente da un numero di 3 pari a N-2) e all'interno da 4-6...-4 (con numero di 6 uguale al numero di 3)
prete
2010-04-20 13:12:51 UTC
Solo un piccolo spunto iniziale.



Puoi usare un approccio alternativo e considerare una singola mina come una configurazione nella tua matrice così fatta:



1..1..1

1..0..1

1..1..1



nella tua matrice NxN. L'aggiunta di mine sarà data semplicemente dalla sovrapposizione lineare di blocchetti di questo tipo. Sommi i singoli valori e dove si sovrappongono gli "1" semplicemente li sommi. Mi sembra che, miracolosamente, così tutto torni.



Dunque, in teoria, sembrerebbe che qualsiasi sovrapposizione di mine genererebbe la stessa somma complessiva.

MA: ciò che fa la differenza è

- lo "zero" dove collochi la mina che azzera qualsiasi valore fosse presente nella casella e

- i bordi della matrice, perché eventuali "1" che escano dalla matrice sono persi.



Dunque: qualsiasi combinazione di mine in cui le mine

- abbiano come distanza minima tra loro due caselle

(cioè: una, ad esempio, in (1,2) e l'altra in (3,2))

- e come distanza minima dal bordo di nuovo due caselle

(nel senso che se la matrice ha indici che vanno da 1 ad N, le mine hanno come indice minimo 2)



ti genera la stessa somma su tutti gli elementi della matrice. E tale somma è la somma massima che puoi produrre. Perché tutti i singoli blocchetti aggiunti si sovrappongono linearmente ma nessuno "zero" di centro mina va ad azzerare un "uno" di confine con la mina; e nessun "uno" di confine esce dalla tabella.

La configurazione più semplice è quella a scacchiera. Ad esempio:



0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.0.0.0.0.0.0.0.0.0

0.0.0.0.0.0.0.0.0.0



Il numero generato da questa configurazione è pari a:

(numero di mine) x 8



La domanda successiva sarebbe: e quante mine al massimo si possono infilare in una matrice senza diminuirne la somma massima?

A naso ti direi, per una matrice NxM:



int[(N-1)/2] x int[(M-1)/2]



Ma qui ci ho pensato poco...



Ciao!

*********

Mi scuso con l'utente di sopra, ma rimango più convinto della mia formula. Ogni mina in realtà occupa uno slot da due, cui va aggiunta una casella per il bordo.

La mia formula mi convince in via "sperimentale":

N = 3 --> 1 mina

N = 4 --> 1 mina

N = 5 --> 2 mine

N = 6 --> 2 mine

N = 7 --> 3 mine

N = 8 --> 3 mine

...

La formula di sopra per N= 5 darebbe una sola mina, mentre invece ce ne stanno due





Stavo anche pensando a qualche generalizzazione per risolvere il problema più generale.

Una risposta complessiva è difficile.

Come spunto iniziale pensavo: una volta esaurite le caselle "libere", se ci sono caselle libere a bordo campo le più convenienti risultano le combinazioni di questo tipo:



....0.0.0.0

....0.x.x.0

....0.0.0.0

....0.x.0.0



Cioè: si iniziano ad aggiungere mine che:



- non sono sul bordo, se no si perdono tre punti almeno (5 sulla spigolo).

- con un numero minimo di vicini adiacenti (anche in diagonali).



Sono dunque da scartare la posizioni a bordo campo.

Le posizioni interne hanno tutte almeno due vicini e dunque perdono 4 punti.

Se il numero di righe o di colonne è pari, ci sono a bordo campo due colonne vuote dove si possono collocare mine perdendo soltanto due punti.

Notare che la combinazione presentata è meglio della:



....0.0.0.0

....0.x.0.0

....0.0.x.0

....0.x.0.0



che aggiungendo una mina con due vicini, perde 4 punti.

Dunque aggiungendo mine che "valgono" soltanto 6 punti si può arrivare alla combinazione massima del tipo:





0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.x.0.x.0.x.0.0.x.0

0.0.0.0.0.0.0.0.0.0



Notare che l'ultima mina in basso a destra l'ho inserita lì per amore di simmetria, ma avrei potuto inserirla in mille altri posti.



Il passo successivo è molto delicato. Non si possono più aggiungere mine con valore "sei" e dunque... che fare? Inserire una combinazione tipo



...0.x.x.x.0.



ha penalità quattro (aggiunge dunque solo 4 punti).

A questo punto sembrerebbe preferibile spostare la mina più a sinistra a bordo campo (perdendo tre punti) per inserirne un'altra. Ma quell'altra non si sa dove metterla. Questo vale anche se la scacchiera ha dimensione dispari. Andare ad infilarsi nelle righe vuote non aggiunge niente, perché sono sempre mine con almeno due vicini. Dunque la combinazione migliore mi sembrerebbe quella:



0.0.0.0.0.0.0.0.0.0

0.x.x.x.x.x.x.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.x.x.x.x.x.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.x.x.x.x.x.x.x.0

0.0.0.0.0.0.0.0.0.0

0.x.0.x.0.x.0.x.0.0

0.x.0.x.0.x.0.0.x.0

0.0.0.0.0.0.0.0.0.0



L'ultima riga è critica e non ci ho ancora pensato.

Però sto procedendo a braccia, non ho ancora una teoria elegante... E non escludo che esistano configurazioni "lontane" e vincenti. Anche se ne dubito.
?
2010-04-20 12:47:00 UTC
a occhio e croce spandere le mine il più possibile porta 8*10=80 come somma.



una coppia può al massimo valere 12 (per terne e simili il rapporto somma/Numero mine decrescerà ancora)


Questo contenuto è stato originariamente pubblicato su Y! Answers, un sito di domande e risposte chiuso nel 2021.
Loading...