Si consideri una griglia bidimensionale (il solito reticolo nel piano). Per i miei scopi, un modello o disposizione è un'assegnazione dei numeri 1 e 2 a qualche sottoinsieme connesso dei punti della griglia. Ad esempio, i seguenti mostra tre modalità distinte:Corrispondenza rapida di modelli bidimensionali
.......1.....1....
.222...2.....12...
.111...2.....2....
.222...22...12211.
.......1....11.1..
dico che un piccolo modello corrisponde una grande se la piccola può essere ruotato o riflessa tale che tutti i suoi numeri sono più piccoli dei numeri nella grande uno. Ad esempio, si consideri il seguente schema:
......
.1212.
....2.
......
non corrisponde più a sinistra la disposizione di cui sopra perché non può essere ruotato o riflessa per adattarsi in un quadrato 3x3. Esso corrisponde alla disposizione centrale perché può essere ruotato e riflesso per adattarsi al di sotto. Tuttavia, NON corrisponde alla disposizione più a destra perché tuttavia è ruotata o riflessa per adattarsi nella disposizione più a destra, i numeri sono più grandi nel modello piccolo rispetto alla disposizione di grandi dimensioni. (Se uno dei miei esempi non è chiaro o hai bisogno di ulteriori informazioni, basta chiedere via nell'area dei commenti. Alcuni chiarimenti in anticipo: il modello non può essere allungato e non può essere ruotato quindi è diagonale rispetto alla griglia . Ciò significa che ci sono quattro rotazioni e quattro riflessioni totali, ognuno dei quali può essere tradotto)
mi chiedo le seguenti domande:.
Come posso verificare rapidamente se un piccolo modello corrisponde a un grande accordo?
Supponiamo di avere molti piccoli motivi. Posso pre-elaborarli in qualche modo per capire rapidamente se almeno uno corrisponde ad un accordo?
suppongo che sarebbe stato bello se una soluzione risolve un problema più generale (come i numeri arbitrari - non solo 1 e 2 - o che consentono forme scollegato), ma ho davvero interessa solo il caso di cui sopra . Grazie.
Bene, è possibile verificare se nessuna corrisponde sommando i punti nelle disposizioni. Se la somma di un modello è maggiore della somma del miglior arrangiamento, sicuramente non c'è una corrispondenza. So che questo non è quello che hai chiesto, buttandolo fuori. – RedDeckWins
Questo è vero e una buona osservazione. (Puoi anche contare il numero di 2 secondi.) Nei miei casi, penso che risolverebbe solo alcune delle mie domande di corrispondenza del modello. –