La stima dello spazio è necessaria per memorizzare 275305224 di 5x5 MagicSquares? [chiuso]

Question

La stima dello spazio è necessaria per memorizzare 275305224 di 5x5 MagicSquares? [chiuso]

Naviga le tue risposte

#1 da (12 voti)
#2 da (2 voti)

-1

Ecco alcuni esempi di 5x5 Magic Squares trovati da alcuni buoni risolutori:

Generatore di quadrati magici di Marcel Roos

questo stato del programma che utilizza Intel a 2,4 GHz richiede circa 95 ore per generare tutte le soluzioni.

strumento open source

Magic squares 5x5
Sum must be: 65

Solution:             1
  1  2 13 24 25
  3 23 17  6 16
 20 21 11  8  5
 22  4 14 18  7
 19 15 10  9 12

Solution:             2
  1  2 13 24 25
  3 23 16  8 15
 21 19 10  6  9
 22  4 14 20  5
 18 17 12  7 11

Solution:             3
  1  2 13 24 25
  3 23 19  4 16
 21 15 10 12  7
 22  8  9 20  6
 18 17 14  5 11

 ...

Il numero di tutte le possibili soluzioni è 275305224. Poiché il calcolo di tutte le soluzioni richiede molto tempo, vorrei che una persona con un computer ad alta velocità trovasse tutte le soluzioni (in un lungo intervallo di tempo) e poi le condividesse sul web per gli altri.

Quale sarebbe un modo efficace per archiviare queste soluzioni, usando una sorta di compressione?

(semplice trucco logico) attirando il principio che la somma in tutte le righe e colonne e in diagonale è uguale a 65

abbiamo solo bisogno di conoscere il valore per solo 14 celle di 25 celle come mostrato di seguito, questo fa sì che lo spazio di archiviazione si riduca quasi a metà 14/25

legenda: + significa valore memorizzato e x significa valore saltato!

+ + + + x
+ + + + x 
+ + + + x
x + x + x
x x x x x

estimation array storage memory compression

posta Fereydoon Shekofte 14.08.2014 - 12:14

fonte

2 risposte

2

25 celle ciascuna di un numero < 255, significa che ognuno occupa 25 byte. 25 * 275305224 è 6,563 Mb o 6,4 Gb.

Questo non è compresso. Compresso: dipende dall'algoritmo di compressione, ma probabilmente stai guardando un paio di concerti, non importa quale.

risposta data 14.08.2014 - 12:18

fonte

Leggi altre domande sui tag estimation array storage memory compression

L'eleganza non è controproducente? [chiuso] Modifica quindi vendere il codice di un'altra persona [chiuso]

score 12 · Accepted Answer

Iniziamo quindi con il semplice approccio per calcolare il minimo indispensabile e trovare ulteriori mezzi per ridurre le dimensioni richieste.

Un quadrato magico 5x5 contiene i valori da 1 a 25. Detto in un altro modo, abbiamo 25 numeri potenziali da memorizzare.
Ci sono 25 celle nella griglia e 5 righe.

Primo approccio
L'approccio più semplice consiste nell'utilizzare 1 byte per cella.
Quindi questo è 25 byte per griglia.
25 byte per 275.305.224 combinazioni sono 6.882.630.600 byte o 6.4 GB.

Secondo approccio
Ma abbiamo solo bisogno di 5 bit per rappresentare quei 25 numeri potenziali. 5 bit per cella di tempo 25 celle ci dà 15 byte, 5 bit per griglia.
15.625 byte per ora di griglia 275.305.224 combinazioni è 4,301,644,125 byte o 4 GB.

3 ° approccio
Come indicato nella tua domanda, abbiamo solo bisogno di mantenere 14 delle 25 celle poiché possiamo calcolare in modo affidabile le celle mancanti per ricreare la griglia.

Quindi possiamo modificare il 2o approccio per ridurre ulteriormente la nostra memoria richiesta.
5 bit per cella di volte 14 celle ci danno 8 byte, 6 bit per griglia.
8.75 byte per ora di griglia 275.305.224 combinazioni è 2.408.920.710 byte o 2.2 GB

4 ° approccio
Secondo questo sito dedicato ai quadrati magici , ci sono 1.394 modi per aggiungere fino a 65 utilizzando i numeri 1 - 25 Quindi sono 1.394 riduzioni.

Abbiamo bisogno di 11 bit per rappresentare quelle 1.394 riduzioni.
E ora abbiamo solo bisogno di mantenere 5 riduzioni invece di 25 celle.
11 bit per 5 riduzioni ci dà 6 byte, 7 bit per griglia.
6.875 byte per tempo di griglia 275.305.224 combinazioni è 1.892.723.415 byte o 1.7 GB

5 ° approccio
Possiamo combinare la tecnica cellulare minima richiesta con un approccio di riduzione per ridurre ulteriormente lo spazio richiesto.

In questo approccio, abbiamo solo bisogno di mantenere 4 delle 5 riduzioni poiché possiamo calcolare la rimanente riga di valori.

11 bit volte 4 riduzioni ci danno 5 byte, 4 bit per griglia.
5,5 byte per ora di griglia 275.305.224 combinazioni è 1.514,178,732 o 1,4 GB.

6 ° approccio
Basato su Pieter B's osservazione dei quadrati magici , possiamo ridurre il numero di combinazioni potenziali che dobbiamo memorizzare.

You can rotate a magic square 90 degrees and it will still be good and you can mirror one and it will still be good, so 1 square can actually stand as a solution for 8 squares.

Che ci porta da 275.305.224 combinazioni a 34.413.153 combinazioni.

E usando il nostro quinto approccio, ora abbiamo:
11 bit volte 4 riduzioni ci danno 5 byte, 4 bit per griglia.
5,5 byte per ora di griglia 34,413,153 combinazioni ci danno 189,272,341,5 byte o 180,5 MB.

Note conclusive:

Un buon algoritmo di compressione dovrebbe essere in grado di trovare modelli aggiuntivi all'interno delle riduzioni elencate e ridurre ulteriormente la quantità di spazio richiesto. Ultimamente non ho giocato con le permutazioni calcolatrici, quindi non ho intenzione di scommettere su quanta ulteriore compressione si vedrebbe da un buon algoritmo di compressione.