Algoritmo di verifica della forma

3

Normalmente ho un approccio molto intuitivo a un algoritmo efficiente. In sostanza, so qual è il collo di bottiglia e come posso migliorare l'algoritmo. Tuttavia, ora sono bloccato e ho bisogno di qualche "ispirazione".

Il problema

L'idea stessa è molto semplice. Ho una matrice di n x m booleani. Inserisco un'altra griglia, anche di n x m booleani. La domanda che questo algoritmo deve risolvere è se la forma di input può mai essere abbinata alla forma di output: ciò può essere fatto specchiando, ruotando e spostando la forma di input intorno. Ho solo bisogno di sapere se le due forme possono essere abbinate o meno: le trasformazioni attuali non contano.

Esempi:

Forma del bersaglio:

0 0 0
0 1 1 
0 0 0 

Input:

1 0 0
1 0 0
0 0 0

Chiaramente, questo può essere fatto. La trasformazione è semplice:

1) Ruota in senso antiorario:

0 1 1
0 0 0
0 0 0

2) Sposta giù:

0 0 0
0 1 1
0 0 0 

Un controllo rapido può essere fatto facilmente: conta quanti zeri o quanti sono nella matrice di input. Se questo non corrisponde al numero di zeri e quelli nella forma di destinazione, non è possibile creare la forma di destinazione.

Una domanda più ampia e generale sarebbe quale specifica classe di algoritmo sto cercando. Per me non è chiaro, anche se usando il mio esempio, direi che un algoritmo di path-path costruito con cura potrebbe funzionare.

Voglio anche sottolineare che non sono uno studente di informatica, la programmazione è uno dei miei hobby. Ho una corretta comprensione delle "manipolazioni di matrice di base" - forse c'è un meraviglioso "trucco matematico" per questo.

    
posta MathematicalRain 14.06.2015 - 23:28
fonte

2 risposte

1

Puoi semplicemente "ritagliare" le forme (rimuovi righe e colonne piene di 0) e poi prova le 8 rotazioni + riflessioni.

Questo ti dà anche un'altra euristica: dopo il ritaglio la dimensione deve essere uguale o una rotazione

    
risposta data 15.06.2015 - 02:09
fonte
1

Oltre a ciò che @miniBill ha già scritto: dopo aver ritagliato la forma (o "spostando" la forma sul bordo inferiore sinistro all'interno della matrice m x n), interpreta il risultato come un numero binario. Ora fai lo stesso con le altre 7 rotazioni e amp; riflessioni, che ti dà 8 numeri. Scegli il minimo tra questi 8 valori e assegna questo numero alla tua matrice originale, lascia chiamare questo numero il "numero di codice" della matrice

In questo modo, due matrici contengono la stessa forma se e solo se hanno lo stesso numero di codice. Ciò ti consentirà di lavorare in modo molto efficiente con i set di forme, ad esempio utilizzando un dizionario o un hashset per archiviare le matrici che hai già e altre che vuoi testare contro quel set.

    
risposta data 15.06.2015 - 13:30
fonte

Leggi altre domande sui tag