Rilevamento di array multidimensionale simile

2

Sto cercando una sorta di algoritmo in modo da poter identificare rapidamente matrici simili, le matrici non sono memorizzate in modo permanente quindi avrei bisogno di un modo per mappare ciascuna matrice a valori facilmente memorizzabili, dopo di che posso usare lo stesso mappatura su matrici future e confronto rapido con i valori calcolati.

Il modo in cui sto definendo una matrice simile è semplicemente se sono identici o meno quando specchiati da una linea verticale, una linea orizzontale, una diagonale maggiore e una diagonale minore.

Ad esempio

1 2 3
4 5 6
7 8 9

è identificato come lo stesso di tutte le seguenti matrici

3 2 1
6 5 4
9 8 7
-----
7 8 9
4 5 6
1 2 3
-----
1 4 7
2 5 8
3 6 9
-----
9 6 3
8 5 2
7 4 1

Sono stato convinto su questo problema da giorni, le matrici non sono archiviate in modo permanente quindi non è possibile confrontarle direttamente. Qualcuno potrebbe indicarmi la giusta direzione? Grazie

    
posta rhysw 26.05.2015 - 05:05
fonte

4 risposte

1

Calcola un valore di hash per ognuna delle otto matrici simmetriche e mantieni solo il più piccolo di esse - questo dovrebbe fare il trucco. Questo ti dà lo stesso valore per ogni matrice di una classe di equivalenza.

    
risposta data 26.05.2015 - 21:14
fonte
0

Puoi usare la matematica per identificare la somiglianza. Ho assunto ogni esempio che hai fornito dopo la matrice iniziale per la similarità come condizione.

Per la matrice nel tuo esempio -

Let Ux = 1 2 3
         4 5 6
         7 8 9

Let Ix = 0 0 1
         0 1 0
         1 0 0

Se si esegue la moltiplicazione della matrice di Ux e Ix si otterrebbe -

Ux . Ix = 3 2 1
          6 5 4
          9 8 7 

Quale è la condizione 1.

Se lo fai

Ix . Ux = 7 8 9
          4 5 6
          1 2 3

Quale è la condizione 2. Quindi, è possibile utilizzare Ix per identificare due condizioni di somiglianza che hai definito.

Per la condizione 3 è Transpose (Ux).

Per la condizione 4 è Trasnpose (Ix. Ux. Ix).

Spero che questo aiuti!

    
risposta data 26.05.2015 - 12:54
fonte
0

Invece di memorizzare un valore di hash, memorizza 5 valori di hash

M0= 1 2 3
    4 5 6
    7 8 9

è identificato come lo stesso di tutte le seguenti matrici

Le operazioni che creano da M1 a M4 sono scritte sotto

M1= 3 2 1  (vertical mirror  M1:= VM(M0) )
    6 5 4
    9 8 7
-----
M2= 7 8 9 (horizontal mirror M2:= HM(M0) )
    4 5 6
    1 2 3
-----
M3= 1 4 7 (transpose M3= T(M0) )
    2 5 8
    3 6 9
-----
M4=     9 6 3 (M4= VM(T(MO) )
    8 5 2
    7 4 1

tutte le matrici equivalenti (totale 7 in aggiunta all'originale) possono essere scritte come combinazioni di VM (), HM () e T ().

quindi se si detengono 8 valori hash per una matrice, è possibile confrontare i propri valori hash.

Per calcolare un valore hash della matrice M0 (i numeri sono solo cifre nel tuo caso), puoi convertirlo nella stringa "123456789" e usare una funzione di hash.

Spero che questo aiuti.

    
risposta data 26.05.2015 - 12:04
fonte
0

Sulla base di alcune riflessioni sul retro dell'inviluppo, suggerirei il seguente approccio: Se sommi ogni singola riga, ogni colonna, ogni diagonale e i 4 angoli, otterrai un insieme di 9 numeri, che possono essere ordinati. Questo elenco ordinato di numeri sarà identico per tutti i casi che hai elencato e le loro rotazioni, ma dovrebbe essere unico (cioè, non entrare in collisione con altre disposizioni). Se questa analisi è vera, puoi usare una funzione hash banale di quell'elenco di 9 numeri come valore memorizzato.

(Naturalmente, se le rotazioni sono escluse dalla tua classificazione di somiglianza, allora dovrò tornare al tavolo da disegno.)

    
risposta data 26.05.2015 - 23:08
fonte

Leggi altre domande sui tag