Herausforderung: Nehmen Sie ein 48x48 -Bild, finden Sie zusammenhängende Bereiche, die zu der billigsten LEGO -Lösung führen, um dieses Bild zu erstellen! [abgeschlossen

StackOverflow https://stackoverflow.com/questions/5307253

Frage

Hintergrund

Lego produziert die X-large graue Grundplatte, Das ist eine große Bauplatte, die 48 Bolzen breit und 48 Bolzen hoch ist, was zu einer Gesamtfläche von 2304 Bolzen führt. Da ich ein LEGO-Fanatiker bin, habe ich ein paar Designs im Mosaik-Stil modelliert, die auf diese Grundplatten gelegt und dann vielleicht an Wänden oder in einem Display aufgehängt werden können (siehe: Android, Dream Theater, Das galaktische Reich, Pokémon).

Die Herausforderung

Meine Herausforderung besteht nun darin, die niedrigsten Kosten für den Kauf dieser Designs zu erhalten. Der Kauf von 2304 einzelnen 1x1 -Platten kann teuer werden. Verwendung Maurer, Im Wesentlichen ein eBay für LEGO, kann ich Daten finden, um festzustellen, welche günstigsten Teile für bestimmte Farben sind. Beispielsweise wäre eine 1x4 -Platte bei 0,10 USD (oder 0,025 USD pro Studum) billiger als eine 6x6 -Platte bei 2,16 USD (oder 0,06 USD pro Stift). Wir können auch eine Liste aller möglichen Platten bestimmen, mit denen ein Bild zusammengestellt werden kann:

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

Das Problem

Nehmen wir für dieses Problem an, dass wir eine Liste aller Teller, ihrer Farbe (n) und eines "Gewichts" oder Kosten für jeden Teller haben. Der Einfachheit halber können wir sogar die Eckstücke entfernen, aber das wäre eine interessante Herausforderung für die Bekämpfung. Wie finden Sie die billigsten Komponenten, um das 48x48 -Bild zu erstellen? Wie würden Sie die Lösung finden, die die wenigsten Komponenten verwendet (nicht unbedingt die billigste)? Wenn wir Eckstücke als zulässige Stücke hinzufügen würden, wie würden Sie sie für sie berücksichtigen?

Wir können davon ausgehen, dass wir eine Master -Liste haben, die durch Abfragen von Maurelink, den Durchschnittspreis für einen bestimmten Ziegelstein in einer bestimmten Farbe erhalten wird und dies als Element in der Liste hinzugefügt wird. Es würde also keinen schwarzen 16x16 -Teller geben, nur weil er nicht hergestellt oder zum Verkauf steht. Die 16x16 hellgrüne Platte hätte jedoch einen Wert von 3,74 US Aktueller verfügbarer Durchschnittspreis.

Ich hoffe, dass mein Aufschreiben des Problems Succint genug ist. Es ist etwas, worüber ich jetzt seit ein paar Tagen nachgedacht habe, und ich bin gespannt, was ihr denkt. Ich habe es als "Interview-Fragen" bezeichnet, weil es eine Herausforderung ist, nicht weil ich es durch ein Interview bekommen habe (obwohl ich denke, es wäre eine lustige Frage!).

BEARBEITEN

Hier ist ein Link zum 2x2 Eckstück und zum 4x4 Eckstück. Die Antwort muss nicht unbedingt die Farbe berücksichtigen, sollte jedoch erweitert werden, um dieses Szenario abzudecken. Das Szenario wäre, dass nicht alle Platten in allen Farben erhältlich sind. Stellen Sie sich also vor, wir haben eine Reihe von Elementen, die eine Platte, seine Farbe und die durchschnittlichen Kosten dieser Platte identifizieren (ein Beispiel ist unten). Vielen Dank an Benjamin für die Bereitstellung eines Kopfgeldes!

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

Diese Liste hätte nicht den Eintrag:

8x8|yellow|imaginarydollaramount

Dies liegt daran, dass eine 8x8 gelbe Platte nicht existiert. Die Liste selbst ist trivial und sollte nur als Referenzen für die Lösung betrachtet werden. Es wirkt sich nicht auf die Lösung selbst aus.

Edit2

Für Klarheit etwas Formulierung geändert.

War es hilfreich?

Lösung

Karls Ansatz ist im Grunde genommen solide, könnte aber einige weitere Details verwenden. Es wird die optimale Kostenlösung finden, ist jedoch für bestimmte Eingaben zu langsam. Insbesondere große offene Bereiche haben zu viele Möglichkeiten, um naiv durchzusuchen.

Wie auch immer, ich habe hier eine schnelle Implementierung in C ++ durchgeführt: http://pastebin.com/s6fpubmc

Es löst das Ausfüllen des leeren Raums (Perioden) mit 4 verschiedenen Arten von Ziegeln:

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

Der Algorithmus füllt also einen bestimmten Bereich aus. Es ist rekursiv (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
}

Sobald wir den billigsten Weg herausgefunden haben, um eine Unterfläche zu füllen, werden wir das Ergebnis zwischenspeichern. Um eine Unterfläche sehr effizient zu identifizieren, werden wir eine 64-Bit-Ganzzahl verwenden Zobrist Hashing. WARNUNG: Hash -Kollisionen können zu falschen Ergebnissen führen. Sobald unsere Routine zurückgegeben wird, können wir die optimale Lösung basierend auf unseren zwischengespeicherten Werten rekonstruieren.

Optimierung:Im Beispiel werden 41936 Knoten (rekursive Anrufe) untersucht (suchen nach leerem quadratischem Top-to-Bottom). Wenn wir jedoch nach leeren Quadraten suchen, werden ~ 900.000 Knoten untersucht.

Für große offene Bereiche: Ich würde vorschlagen, das kosteneffizienteste Stück zu finden und einen Großteil des offenen Bereichs mit diesem Stück als Vorverarbeitungsschritt auszufüllen. Eine andere Technik besteht darin, Ihr Bild in einige Regionen zu teilen und jeden Bereich separat zu optimieren.

Viel Glück! Ich werde bis zum 26. März nicht verfügbar sein, also hoffentlich habe ich nichts verpasst!

Andere Tipps

Schritte

Schritt 1: Durch alle Lösungen iterieren.

Schritt 2: Finden Sie die billigste Lösung.

Erstellen Sie Stücke Inventar

Machen Sie für eine Reihe möglicher Stücke (einschließlich einzelnen Stücke jeder Farbe) mindestens N -Duplikate jedes Stücks, wobei n = max (Board#/Stück jeder Farbe). Daher können höchstens n dieses Stücks alle Farben des gesamten Bretts nach Gebiet abdecken.

Jetzt haben wir eine riesige Sammlung möglicher Stücke, die begrenzt sind, weil eine Teilmenge dieser Sammlung das Board vollständig füllt.

Dann wird es zu einem Teilmenschenproblem, das NP-Complete ist.

Lösen des Teilmenschproblems

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)

Optimierungen

Offensichtlich ist es von größter Bedeutung, ein O (2^n) -Algorithmus zu sein. Optimierungen müssen früh durchgeführt werden, um langlebig zu vermeiden. n ist eine sehr große Zahl; Betrachten Sie einfach ein 48x48 -Board - Sie haben allein für einzelne Stücke 48x48xc (wobei C = Anzahl der Farben) allein für einzelne Stücke.

Daher müssen 99% des Suchbaums aus den ersten hundert Lagen beschnitten werden, damit dieser Algorithmus in jeder Zeit abgeschlossen ist. Halten Sie beispielsweise eine Bilanz der bisher kostengünstigsten Lösung bei und suchen Sie einfach auf, alle niedrigeren Lagen und Rückschläge zu durchsuchen, wenn die aktuellen Kosten plus (die Anzahl der leeren Platinepositionen x niedrigste Durchschnittskosten für jede Farbe)> aktuelle niedrigste Kostenlösung.

Zum Beispiel weiter optimieren, indem Sie immer zuerst die größten Teile (oder die niedrigsten Durchschnittskosten) bevorzugen, um die Grundlösung für die niedrigste Kosten so schnell wie möglich zu verringern und so viele zukünftige Fälle wie möglich zu beschneiden.

Das billigste finden

Berechnen Sie die Kosten jeder Lösung, finden Sie das billigste!

Kommentare

Dieser Algorithmus ist generisch. Es geht nicht davon aus, dass ein Stück die gleiche Farbe hat (Sie können mehrfarbige Stücke haben!). Es geht nicht davon aus, dass ein großes Stück billiger ist als die Summe kleinerer Stücke. Es nimmt nichts an.

Wenn einige Annahmen getroffen werden können, können diese Informationen verwendet werden, um den Suchbaum so früh wie möglich weiter zu beschneiden. Wenn Sie beispielsweise nur einfarbige Stücke verwenden, können Sie große Abschnitte der Platine (mit den falschen Farben) und große Anzahl von Teilen im Set (der falschen Farbe) beschneiden.

Anregung

Versuchen Sie nicht, 48x48 gleichzeitig zu machen. Probieren Sie es an etwas Kleiner, sagen Sie 8x8 mit einigermaßen kleinen Teilen. Dann erhöhen Sie die Anzahl der Teile und die Brettgröße zunehmend. Ich habe wirklich keine Ahnung, wie lange das Programm dauern wird - aber würde es lieben, wenn jemand es mir erzählt!

Zuerst verwenden Sie die Überschwemmungsfüllung, um das Problem in die Füllung von kontinuierlichen Regionen von Lego -Ziegeln zu zerlegen. Dann können Sie für jedes von denen ein DFS mit einer Memoisierung verwenden, die Sie wünschen. Die Überschwemmungsfüllung ist trivial, daher werde ich sie nicht weiter beschreiben.

Stellen Sie sicher, dass Sie einer rechten Regel folgen, während Sie den Suchbaum erweitern, um die Zustände nicht zu wiederholen.

Meine Lösung wird sein:

  1. Sortieren Sie alle Teile nach Gestütskosten.
  2. Versuchen Sie für jedes Stück in der sortierten Liste so viele wie möglich in den Teller:
    • Raster Ein 2D -Bild Ihres Designs sucht nach Regionen des Bildes mit einheitlicher Farbe, der Form des aktuellen Stücks und kostenlosen Stufen für jeden Stift, den das Stück verwendet.
    • Wenn die gefundene Farbe der Region für dieses bestimmte Stück nicht vorhanden ist, ignorieren Sie eine weiterhin suchende Suche.
    • Wenn die Farbe vorhanden ist: Markieren Sie die von diesen Teilen verwendeten Stufen und erhöhen Sie einen Zähler für diese Art von Stück und diese Farbe.
    • Schritt 2 erfolgt einmal für quadratische Stücke, zweimal für rechteckige Stücke (einmal vertikal und einmal horizontal) und 4 Mal für Eckstücke.
  3. Iterieren auf 2, bis der Teller voll ist oder keine Art von Teilen mehr verfügbar ist.

Sobald Sie bis zum Ende angekommen sind, haben Sie die Anzahl der Teile jeder Art und jede Farbe, die Sie mit minimalen Kosten benötigen.

Wenn sich die Kosten nach Stubs um Farbe ändern können, muss die ursprüngliche sortierte Liste nicht nur die Art von Stück auch nach der Farbe enthalten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top