Come posso ottimizzare la mia soluzione di forza bruta a questo problema?
Sto lavorando a una soluzione al problema spiegato di seguito. Sto usando la forza bruta, ho raggiunto il punto in cui le soluzioni sono proibitive, quindi ho bisogno di ottimizzare di più (se possibile). Naturalmente, sarà ancora meglio se esiste un modo migliore per risolvere il problema (non la forza bruta).
C'è qualcosa che posso fare per migliorare la mia soluzione o un riferimento che posso esaminare (problemi simili, ecc.)?
Il problema
Iniziamo con una tavola rettangolare. Ogni cella può essere in N stati e lo stato iniziale per ogni cella è casuale (0 <= stato < N) per ogni cella. Abbiamo anche una serie di forme, tutte adatte alla tavola. Ogni forma è continua.
Ogni forma deve essere posizionata una volta (e solo una volta) nel tabellone. Quando viene posizionata una forma, ogni cella che appartiene alla forma avrà il suo valore aumentato di 1. Se il valore della scheda in qualsiasi cella raggiunge N, viene modificato in 0.
L'obiettivo è trovare le posizioni in cui ogni forma deve essere posizionata in modo che il tabellone finale abbia tutte le celle con valore 0. C'è sempre almeno una soluzione. Supponiamo che il problema sia generato partendo dalla tavola finita e applicando forme casuali in posizioni casuali.
La dimensione del tabellone, il numero di stati N e il numero di forme sono la configurazione del gioco e continuano ad aumentare (a velocità diverse) per ogni "livello".
Quello che sto facendo attualmente
Sono in grado di risolvere il problema fino a una certa dimensione usando solo la forza bruta. Ho alcune ottimizzazioni in atto. Sono arrivato a un punto in cui la soluzione è proibitiva, quindi vorrei migliorare la mia logica.
La prima cosa che sto facendo è ordinare la forma dal più grande al più piccolo, il più piccolo verrà spostato nelle iterazioni interne. Il presupposto (che non ho dimostrato, ma testato per essere più veloce) è che è meglio spostare di più le forme più piccole, poiché hanno maggiori possibilità di generare una soluzione.
In secondo luogo, per le forme ripetute, evito di controllare tutte le permutazioni, poiché producono lo stesso risultato. Controllo anche solo un insieme di posizioni quando una coppia di stesse forme si sovrappone (poiché tutte le sovrapposizioni producono lo stesso risultato).
Un'ultima ottimizzazione che penso sarà di grande aiuto, ma che sto ancora implementando è: ad ogni forma nella sequenza, conta il totale delle celle nelle forme che rimangono da spostare. Questo numero, meno i giri di cella totali necessari per ottenere una scheda finita, deve essere un multiplo di N. In caso contrario, non ha senso forzare bruscamente le posizioni delle forme rimanenti e dobbiamo riposizionare una forma in un ciclo esterno.
Ulteriori dettagli
Sono interessato a qualsiasi altro suggerimento su come ottimizzare questo. Algoritmi noti, anche una buona denominazione per questo insieme di problemi, che posso usare per ricercare di più sarebbe fantastico.
Risposte
Programmazione lineare intera
Il tuo problema può essere formulato nel modo seguente: ci vengono dati dei vettori$v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, dove si trova il tabellone$d$celle, e l'obiettivo è, dato un vettore$c \in (\mathbb{Z}/N\mathbb{Z})^d$, trovare una funzione$f$affinché$\sum_i v_{i,f(j)}=c$. Questo problema potrebbe quindi essere risolto dalla programmazione lineare intera. Questo è legato ad a$d$problema della somma di sottoinsiemi multidimensionali, quindi potresti anche essere in grado di trovare altri algoritmi per la somma di sottoinsiemi multidimensionali e provarli anche tu.
Come lo formuliamo in questo modo? Se la griglia ha$d$cellule, possiamo pensare a una forma come a$d$-vettore di 0 e 1, con 1 nelle celle coperte dalla forma. Ogni forma può essere collocata in un numero di posizioni diverse, producendo vettori diversi.$v_{i,j}$corrisponde al$j$esimo posto dove forma$i$può essere posizionato.$c$corrisponde ai numeri originariamente nella griglia (beh, la negazione di quei numeri, modulo$N$). Tutta l'aritmetica è fatta modulo$N$.
Forza bruta leggermente più intelligente
In alternativa, ecco un modo per migliorare un po' la forza bruta, scambiando la memoria con il tempo. Supponiamo che tu abbia$k$forme. Inizia elencando tutti i modi per posizionare il primo$k/2$forme su una scheda vuota di tutti zeri e memorizza tutte le posizioni risultanti in una tabella hash o in un elenco ordinato. Quindi, enumera tutti i modi per posizionare l'ultimo$k/2$forme sulla posizione iniziale e cerca ciascuna delle posizioni risultanti nella tabella hash o nell'elenco ordinato. Se trovi una corrispondenza, questo produce una soluzione. Ciò ti consentirà di spingere un po 'più in là la forza bruta, potenzialmente fino a circa il doppio delle forme, se disponi di una quantità illimitata di memoria. Ci sono molti dettagli coinvolti nell'ottimizzazione al massimo, ma è un'idea che potresti prendere in considerazione se la tua forza bruta ti avvicina ma non è all'altezza. È ancora un algoritmo a tempo esponenziale, quindi raggiungerà comunque un limite.