Sto lavorando a un progetto che consiste nel riempire più rettangoli in un rettangolo più grande (il riquadro di delimitazione). I rettangoli non possono sovrapporsi l'uno con l'altro o con i limiti del riquadro di delimitazione. I rettangoli possono ruotare, aumentando lo spazio degli stati in n! * 2^n per problemi di n rettangoli.
Sto provando a scrivere un programma Python che "risolve" questi problemi, ad esempio dovrebbe trovare tutte le possibili soluzioni dato un insieme di rettangoli e un rettangolo di selezione. In questo momento sto utilizzando un algoritmo di ricerca approfondito, ma mi sento come se mi mancassero molte ottimizzazioni per accelerare il mio programma. Il mio algoritmo funziona come segue:
- Ho una lista con valori che rappresentano l'altezza delle colonne nel riquadro di delimitazione più grande, inizializzato su tutti gli 0.
- Cerco il primo punto vuoto nel riquadro di delimitazione, che è rappresentato dalla colonna con il valore più piccolo.
- Se il rettangolo corrente si adatta a quel punto, I 'posiziona' il rettangolo aumentando l'altezza delle colonne a destra in base all'altezza del rettangolo.
- Ripeti 2 e 3 fino a quando non è più possibile inserire altri rettangoli e torna ad altre possibili soluzioni.
Nel codice (pseudo-) sembra che questo:
def solve(rectangles):
# Solution found
if rectangles is empty:
add_to_solutions()
return
position = find_first_empty_spot()
for rectangle in rectangles:
for r in [rectangle, rectangle.rotated()]:
if rectangle fits at given position:
place_rectangle_in_bounding_box(r)
remove r from rectangles
solve(remaining_rectangles)
remove_rectangle_from_bounding_box(r)
Le basi del mio algoritmo sono corrette o mi mancano alcuni (ovvi) miglioramenti? Sarebbe bello risolvere problemi di dimensioni fino a 20 rettangoli, ma il mio algoritmo attuale richiederebbe troppo tempo per risolverli.
E: sto cercando di trovare "tutte" le possibili soluzioni al problema, non posso semplicemente fermarmi dopo aver trovato una "soluzione", quindi molte euristiche trovate in letteratura non sono applicabili.