Algoritmo di layout a blocchi

Question

Sto cercando aiuto per migliorare un algoritmo per posizionare blocchi di forme dispari. Il mio dominio del problema è strano, ma la migliore analogia per i miei blocchi sono i pezzi di Tetris, tranne che possono avere più di quattro pezzi. I blocchi sono ancora composti solo da angoli retti, ma possono essere lunghi e tortuosi, possono diramarsi, ecc.

Sto provando a sistemare più blocchi di grandi dimensioni di forma arbitraria nello spazio minimo (lo so, un contenitore di rifiuti problema) ma la mia attuale soluzione sembra brutta. In pratica ne sto piazzando uno, poi il bruto sta forzando il resto cercando di posizionarli all'origine della mia griglia e poi spingendoli lentamente in direzioni diverse fino a quando non collidono più. Non è lento, ma non fa alcun tentativo di adattarsi bene ai pezzi in modo da non sprecare lo spazio complessivo.

L'unica cosa che posso pensare di provare è ordinare i blocchi per dimensione, posizionando prima il più grande, quindi inserendo il più piccolo alla fine in tutti i fori rimanenti. Ma ci sono sicuramente dei modi che possono ritorcersi contro.

Esistono algoritmi euristici o di approssimazione che possono aiutarmi qui?

I risultati sarebbero simile a quanto segue:

Answer 1

Questo (Polyomino forma-imballaggio) generalmente

Inoltre, forse il mio gravatar commette che si tratta di Mega Man correlate ... sembra essere un problema di matematica non banale, e ti indicherò l'esperienza di alcuni altri che ci hanno lavorato. Questo ragazzo ha un sacco di esempi di poliomino sul suo sito web dove altri possono presentare soluzioni. Ha anche software di risoluzione in Java:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html.

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

Ci sono anche alcuni algoritmi scritti per questo da Stephen Montgomery-Smith, che sembrano essere più completo rispetto della precedenza (ha risolto alcuni problemi che non erano risolvibili con quella) alla fine ha reso in un xscreensaver (risolve in tempo reale e bello da guardare!). Il seguente screenshot, dallo screensaver, mostra solo forme fino ai pentamini, ma funziona su forme generali con contenitori generali.

http://www.math.missouri.edu/~stephen/software/

non sono sicuro se uno di questi software approssima la soluzione migliore di poliomini consentendo fori. Ma è decisamente "decidibile" in questo modo, nel senso che potresti inserire extra 1x1 di polyominoes nella tua soluzione e vedere se può trovare un risultato particolare che si adatta, quindi rimuovere i pezzi 1x1 per ottenere il risultato.

Per la vostra applicazione, potrebbe essere più efficiente di lavorare a ritroso. Tutti questi algoritmi hanno complessità nel numero di celle unitarie in ciascun blocco. Un buon modo per deporre i blocchi sarebbe considerarli come "suddivisioni" in celle più grandi, in modo che un quadrato 3x3 nel blocco corrisponda a un quadrato 1x1 in una versione riscalata. Quindi, riempire i blocchi con spazio vuoto in modo che siano tutti composti da blocchi più grandi, eseguire l'algoritmo e rimuovere lo spazio extra. Non solo sarà molto più veloce da eseguire, ma genererà anche lo spazio tra i blocchi necessari.