Sfida: Prendere un'immagine 48x48, trovare aree contigue che risultato nella soluzione di Lego più economico per creare quell'immagine! [chiuso]

Question

Sfondo

Lego produce il X-Large grigio basetta, che è un piatto grande edificio che è largo 48 borchie e alto 48 borchie, risultando in una superficie totale di 2304 borchie. Essendo un Lego fanatico, ho modellato alcuni disegni a mosaico in stile che possono essere messi su queste piastre base e poi magari appesi sui muri o in un display (vedere: Android , Dream Theater , L'Impero Galattico , Pokemon ).

La sfida

La mia sfida è ora di ottenere il più basso costo per l'acquisto di questi disegni. L'acquisto di 2304 piatti individuali 1x1 può ottenere costoso. Utilizzando Bricklink , essenzialmente un eBay per Lego, posso trovare i dati per determinare quali sono le parti più economici sono per determinati colori. Ad esempio, una piastra 1x4 a $ 0.10 (o $ 0,025 per perno) sarebbe più conveniente che una piastra 6x6 a $ 2.16 (o $ 0,06 per perno). Possiamo anche determinare un elenco di tutti i possibili piastre che possono essere utilizzati per assemblare un'immagine:

1x1
1x2
1x3
1x4
1x6
1x8
1x10
1x12    
2x2 corner!    
2x2
2x3
2x4
2x6
2x8
2x10
2x12
2x16    
4x4 corner!    
4x4
4x6
4x8
4x10
4x12    
6x6
6x8
6x10
6x12
6x14
6x16
6x24    
8x8
8x11
8x16    
16x16

Il problema

Per questo problema, supponiamo che abbiamo una lista di tutte le lastre, il loro colore (s), e un "peso" o il costo per ogni piatto. Per semplicità, si può anche rimuovere i pezzi d'angolo, ma che sarebbe una sfida interessante per affrontare. Come si troverebbero i componenti più economici per creare l'immagine 48x48? Come si dovrebbe trovare la soluzione che utilizza i componenti minor numero (non necessariamente il più economico)? Se dovessimo aggiungere pezzi d'angolo come pezzi ammissibili, come ti spieghi loro?

Si può presumere abbiamo qualche lista di master che si ottiene interrogando Bricklink, ottenendo il prezzo medio per una data mattoni in un determinato colore, e aggiungendo che come un elemento della lista. Quindi, non ci sarebbe nero 16x16 piatto semplicemente perché non è fatto o per la vendita. La piastra di 16x16 verde brillante, però, avrebbe un valore di $ 3,74 che va dal corrente disponibile prezzo medio .

Spero che il mio write-up del problema è abbastanza succint. E 'qualcosa che ho pensato per un paio di giorni ormai, e sono curioso di sapere cosa pensate voi ragazzi. Ho contrassegnate come "intervista-domande" perché è impegnativo, non perché l'ho preso attraverso un colloquio (anche se credo che sarebbe una domanda divertente!).

Modifica

Ecco un link al 2x2 pezzo d'angolo e al 4x4 pezzo d'angolo . La risposta non deve necessariamente tener conto del colore, ma dovrebbe essere espandibile per coprire tale scenario. Lo scenario sarebbe che non tutti i piatti sono disponibili in tutti i colori, in modo da immaginare che abbiamo una serie di elementi che identificano un piatto, il suo colore, e il costo medio di tale piastra (un esempio è di seguito). Grazie a Benjamin per fornire una taglia!

1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]

Questa lista non sarebbe la voce:

8x8|yellow|imaginarydollaramount

Questo è perché un piatto giallo 8x8 non esiste. La lista è di per sé banale e dovrebbe essere pensato solo a fornire i riferimenti per la soluzione; essa non influisce sulla soluzione stessa.

EDIT2

cambiato alcune formulazioni per chiarezza.

Answer 1

L'approccio di Karl è fondamentalmente sana, ma si può usare qualche dettaglio in più. Sarà trovare la soluzione ottimale costo, ma sarà troppo lento per determinati input. Ampi spazi aperti soprattutto avranno troppe possibilità per la ricerca in ingenuamente.

In ogni modo, ho fatto una rapida implementazione in C ++ qui: http://pastebin.com/S6FpuBMc

Risolve riempiendo lo spazio vuoto (periodi), con 4 diversi tipi di mattoni:

0: 1x1 cost = 1000
1: 1x2 cost = 150
2: 2x1 cost = 150
3: 1x3 cost = 250
4: 3x1 cost = 250
5: 3x3 cost = 1

..........       1112222221
...#####..       111#####11
..#....#..       11#2222#13
..####.#..       11####1#13
..#....#..       22#1221#13
..........       1221122555
..##..#...  -->  11##11#555
..#.#.#...       11#1#1#555
..#..##...       11#11##221
..........       1122112211
......#..#       122221#11#
...####.#.       555####1#0
...#..##..       555#22##22
...####...       555####444  total cost = 7352

Quindi, l'algoritmo si riempie in una determinata area. E 'ricorsiva (DFS):

FindBestCostToFillInRemainingArea()
{  
  - find next empty square
  - if no empty square, return 0
  - for each piece type available
    - if it's legal to place the piece with upper-left corner on the empty square
      - place the piece
      - total cost = cost to place this piece + FindBestCostToFillInRemainingArea()
      - remove the piece
  return the cheapest "total cost" found
}

Una volta che capire il modo più economico per riempire una sottozona, faremo cache il risultato. Per identificare in modo molto efficiente una sottozona, useremo un integer a 64 bit utilizzando Zobrist hashing. Attenzione: collisioni hash possono causare risultati non corretti. Una volta che i nostri rendimenti di routine, siamo in grado di ricostruire la soluzione ottimale sulla base dei nostri valori memorizzati nella cache.

Ottimizzazione: Nell'esempio, 41936 nodi (chiamate ricorsive) sono esplorate (ricerca per vuoto quadrato dall'alto in basso). Tuttavia, se si cerca per piazze vuote da sinistra a destra, ~ 900.000 nodi sono esplorate.

Per le grandi aree aperte: Mi piacerebbe consiglio di cercare il pezzo più conveniente e riempimento in un sacco di spazio aperto con quel pezzo come una fase di pre-processo. Un'altra tecnica è quella di dividere l'immagine in alcune regioni, e ottimizzare ogni regione separatamente.

In bocca al lupo! Sarò disponibile fino a 26 marzo, quindi speriamo che non mi manca nulla!

Answer 2

Passi

Passaggio 1:. Scorrere tutte le soluzioni

Passaggio 2:. Trovare la soluzione più economica

Crea pezzi inventario

Per una serie di possibili pezzi (includere singoli pezzi di ogni colore), fare almeno n duplicati di ogni pezzo, dove n = max (scheda # / piece # di ogni colore). Pertanto, al massimo n di quel pezzo può coprire tutti i colori dell'intera tavolo per zona.

Ora abbiamo una vasta collezione di pezzi possibili, delimitata perché è garantito che un sottoinsieme di questa collezione sarà completamente riempire la scheda.

Poi diventa un problema sottoinsieme, che è NP-completo.

Risolvere il problema sottoinsieme

For each unused piece in the set
  For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4)
    For each possible position in the *remaining* open places on board matching the color and rotation of the piece
      - Put down the piece
      - Mark the piece as used from the set
      - Recursively decent on the board (with already some pieces filled)

Ottimizzazioni

Ovviamente essendo un O (2 ^ n) algoritmo, potatura dell'albero di ricerca precoce è della massima importanza. Ottimizzazioni deve essere fatto in anticipo per evitare di lunga esecuzione. n è un numero molto grande; basta considerare un bordo 48x48 - avete 48x48xc (dove c = numero di colori) solo per solo singoli pezzi.

Di conseguenza, il 99% della struttura di ricerca deve essere potata dalle prime poche centinaia di strati in modo che questo algoritmo per completo in qualsiasi momento. Ad esempio, mantenere un conteggio della soluzione più economica trovato finora, e solo interrompere la ricerca tutti gli strati inferiori e traccia posteriore quando il costo attuale più (il numero di posizioni di bordo vuote x disponibilità costo medio per ogni colore)> corrente soluzione più economica.

Per esempio, ottimizzare ulteriormente favorendo sempre più grandi pezzi (oi pezzi medio-costo più basso) in primo luogo, in modo da ridurre la soluzione di costo più basso della linea di base il più rapidamente possibile e di potare il maggior numero di casi futuri possibili.

trovare il più conveniente

Calcola il costo di ciascuna soluzione, trovare il più economico!

Commenti

Questo algoritmo è generico. Essa non si assume una parte è dello stesso colore (è possibile avere i pezzi multi-colored!). Essa non presuppone che un grosso pezzo è più conveniente rispetto alla somma delle parti più piccole. Essa in realtà non dare niente per scontato.

Se alcune ipotesi possono essere fatte, allora questa informazione può essere utilizzata per ulteriori potare l'albero di ricerca il più presto possibile. Ad esempio, quando si utilizza solo pezzi singoli di colore, è possibile potare grandi sezioni della scheda (con i colori sbagliati) e il gran numero di prugna di pezzi nel set (del colore sbagliato).

Suggerimento

Non cercare di fare 48x48 in una sola volta. Provalo su qualcosa di piccolo, per esempio, 8x8, con una ragionevolmente piccola serie di pezzi. Quindi aumentare il numero di pezzi e le dimensioni della scheda progressivamente. Io davvero non ho idea di quanto tempo il programma si prenderà - ma mi piacerebbe che qualcuno mi dica

Answer 3

Per prima cosa utilizzare il riempimento di inondazione per rompere il problema in riempimento regioni continue di mattoncini Lego. Poi per ciascuno di quelli che si possono utilizzare un DFS con Memoizzazione che si desidera. Il riempimento delle inondazioni è banale quindi non voglio descriverlo più lontano.

Assicurati di seguire una regola della mano destra mentre espandendo la struttura di ricerca per gli stati non ripetere.

Answer 4

La mia soluzione sarà:

1. Ordina tutti i brani di costo perno.
2. Per ogni pezzo nella lista ordinata, provare a posto come molti come si può nel piatto:
   • Raster un'immagine 2D del vostro disegno in cerca di regioni dell'immagine con il colore uniforme, la forma del pezzo corrente e borchie gratuiti per ogni prigioniero che il pezzo userà.
   • Se il colore della regione ha trovato non esistono per quel pezzo particolare, ignorare una continua ricerca.
   • Se il colore esiste:. Tag i perni utilizzati da che i pezzi e incrementare un contatore per quel tipo di pezzo e quel colore
   • Fase 2 verrà effettuata una volta per pezzi squadrati, due volte per pezzi rettangolari (una volta verticale e una volta orizzontale) e 4 volte per pezzi angolari.
3. Iterate per 2 fino a quando la piastra è pieno o più tipi di pezzi sono disponibili.

Una volta arrivati ??alla fine si avrà il numero di pezzi di ogni tipo e di ogni colore che avete avuto bisogno, con un costo minimo.

Se il costo da mozziconi può cambiare in base al colore, quindi l'elenco ordinato originale deve includere non solo il tipo di pezzo per anche il colore.