Défi: Prendre une image 48x48, trouver des zones contiguës qui donnent lieu à la solution la moins chère Lego pour créer cette image! [fermé]

https://stackoverflow.com/questions/5307253

24-10-2019
|

Question

Historique

Lego produit le X-Large Gris embase , qui est d'une grande plaque de construction qui est de 48 plots de large et 48 de hauteur des plots, ce qui entraîne une superficie totale de 2304 clous. Être un fanatique Lego, j'ai modélisé quelques modèles de style mosaïque qui peuvent être mis sur ces plaques de base et peut-être accroché sur les murs ou sur un écran (voir: Android , Dream Theater , L'Empire galactique , Pokemon ).

Le défi

Mon défi est maintenant d'obtenir le prix le plus bas pour acheter ces modèles. L'achat 2304 assiettes individuelles 1x1 peut coûter cher. En utilisant Bricklink , essentiellement eBay pour Lego, je peux trouver des données pour déterminer ce que les pièces les moins chères sont pour les couleurs données. Par exemple, une plaque de 1x4 à 0,10 $ (ou 0,025 $ par montant) serait moins cher qu'une plaque de 6x6 à 2,16 $ (ou 0,06 $ par montant). Nous pouvons également déterminer une liste de toutes les plaques possibles qui peuvent être utilisées pour assembler une image:

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

Le problème

Pour ce problème, supposons que nous avons une liste de toutes les plaques, leur couleur (s), et un « poids » ou le coût pour chaque plaque. Par souci de simplicité, on peut même enlever les morceaux de coin, mais ce serait un défi intéressant à aborder. Comment voulez-vous trouver les composants les moins chers pour créer l'image 48x48? Comment voulez-vous trouver la solution qui utilise le plus petit nombre de composants (pas nécessairement le moins cher)? Si nous devions ajouter des morceaux de coin en morceaux admissibles, comment expliqueriez-vous pour eux?

Nous pouvons supposer que nous avons une liste principale qui est obtenue en interrogeant Bricklink, obtenir le prix moyen pour une brique donné dans une couleur donnée, et en ajoutant que comme un élément dans la liste. Donc, il n'y aurait pas de plaque noire 16x16 simplement parce qu'il ne se fait pas ou à la vente. La plaque Bright Green 16x16, cependant, aurait une valeur de 3,74 $, en passant par le prix moyen courant disponible .

J'espère que mon écriture-up du problème est assez succint. Ce quelque chose que j'ai pensé à quelques jours maintenant, et je suis curieux de savoir ce que vous en pensez. Je taggé comme « entrevue-questions » parce qu'il est un défi, non pas parce que je l'ai eu dans une interview (bien que je pense que ce serait une question de plaisir!).

EDIT

Voici un lien vers la pièce d'angle 2x2 et pièce d'angle 4x4 . La réponse ne doit pas nécessairement prendre en couleur compte, mais il doit être extensible pour couvrir ce scénario. Le scénario serait que toutes les plaques ne sont pas disponibles dans toutes les couleurs, alors imaginez que nous avons un ensemble d'éléments qui permettent d'identifier une plaque, sa couleur, et le coût moyen de cette plaque (un exemple est ci-dessous). Merci à Benjamin pour fournir une prime!

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

Cette liste ne se serait pas l'entrée:

8x8|yellow|imaginarydollaramount

En effet, une plaque jaune 8x8 n'existe pas. La liste elle-même est trivial et ne doit être pensé comme fournir des références pour la solution; il n'a pas d'impact de la solution elle-même.

EDIT2

Changé un libellé pour plus de clarté.

La solution

L'approche de Karl est fondamentalement saine, mais il pourrait utiliser quelques détails. Il trouvera la solution de coût optimal, mais sera trop lent pour certaines entrées. De grands espaces ouverts en particulier auront trop de possibilités de recherche par naïveté.

Quoi qu'il en soit, je fait une mise en œuvre rapide en C ++ ici: http://pastebin.com/S6FpuBMc

Il permet de résoudre remplir l'espace vide (périodes), avec 4 différents types de briques:

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

Ainsi, l'algorithme remplit dans une zone donnée. Il est récursive (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
}

Une fois que nous trouver le meilleur moyen de remplir une sous-zone, nous allons mettre en cache le résultat. Identifier très efficacement une sous-zone, nous allons utiliser un entier de 64 bits en utilisant Zobrist. Attention: les collisions de hachage peuvent provoquer des résultats incorrects. Une fois que nos déclarations de routine, nous pouvons reconstruire la solution optimale en fonction de nos valeurs mises en cache.

Optimisation: Dans l'exemple, 41936 noeuds (appels récursifs) sont explorés (recherche de haut à fond carré vide). Toutefois, si nous cherchons des places vides de gauche à droite, ~ 900.000 nœuds sont explorés.

Pour les grandes surfaces ouvertes: Je suggère de trouver la pièce la plus rentable et de remplissage dans une grande partie de la zone ouverte avec ce morceau comme une étape de pré-processus. Une autre technique consiste à diviser l'image en plusieurs régions, et d'optimiser séparément chaque région.

Bonne chance! Je serai disponible jusqu'au 26 Mars si tout va bien je ne l'ai pas raté quelque chose!

Autres conseils

Étapes

Étape 1:. Itérer à travers toutes les solutions

Étape 2:. Trouvez la solution

Créer un inventaire des pièces

Pour un réseau d'éléments possibles (y compris des pièces uniques de chaque couleur), faites au moins n des doubles de chaque pièce, où n = max (carte # / # pièce de chaque couleur). Par conséquent, au plus n de cette pièce peut couvrir toutes les couleurs de l'ensemble du conseil par région.

Maintenant, nous avons une énorme collection de pièces possibles, limité car il est garanti qu'un sous-ensemble de cette collection remplira complètement le conseil d'administration.

Il devient alors un problème de sous-ensemble, qui est NP-complet.

Résoudre le problème du sous-ensemble

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)

Optimisations

étant évidemment un O (2 ^ n) algorithme, la taille de l'arbre de recherche précoce est d'une importance capitale. Optimisations doit être fait tôt pour éviter de longue durée. n est un nombre très important; il suffit de considérer un 48x48 conseil - vous avez 48x48xc (où c = nombre de couleurs) juste pour seul pièces uniques.

Par conséquent, 99% de l'arbre de recherche doit être élagué des premières quelques centaines de plis pour que cet algorithme complet en tout temps. Par exemple, garder un décompte de la solution la moins coûteuse trouvée jusqu'à présent, et juste arrêter la recherche toutes les couches inférieures et BackTrack chaque fois que le coût actuel plus (le nombre de postes de plateau vide x coût moyen le plus bas pour chaque couleur)> solution la plus économique actuelle.

Par exemple, optimiser en privilégiant toujours les plus gros morceaux (ou les plus bas pièces coût moyen) d'abord, de manière à réduire la solution la moins coûteuse de base le plus rapidement possible et de pruneau autant de cas futurs possibles.

Trouver le moins cher

Calculer le coût de chaque solution, trouver le moins cher!

Commentaires

Cet algorithme est générique. Elle ne suppose pas un morceau est de la même couleur (vous pouvez avoir des pièces multicolores!). Elle ne suppose pas qu'un gros morceau est moins cher que la somme des petits morceaux. Elle ne suppose pas vraiment quoi que ce soit.

Si certaines hypothèses peuvent être faites, cette information peut être utilisée pour pruneau encore l'arbre de recherche le plus tôt possible. Par exemple, lorsque vous utilisez uniquement des pièces uniques de couleur, vous pouvez tailler une grande partie de la carte (avec les mauvaises couleurs) et pruneau grand nombre de pièces dans le jeu (de la mauvaise couleur).

Suggestion

Ne pas essayer de faire 48x48 à la fois. Essayez-le sur petit quelque chose, par exemple, 8x8, avec un ensemble relativement restreint de pièces. Ensuite, augmenter le nombre de pièces et de la taille de la carte progressivement. Je ne sais vraiment pas combien de temps le programme prendra - mais aimerait quelqu'un me dire

Tout d'abord que vous utilisez pour remplir les inondations briser le problème en remplissant des régions continues de briques lego. Ensuite, pour chacun de ceux que vous pouvez utiliser un DSF avec memoization que vous souhaitez. Le remplissage d'inondation est trivial, donc je ne vais pas le décrire plus loin.

Assurez-vous de suivre une règle de la main droite tout en élargissant l'arbre de recherche aux Etats ne répéterai pas.

Ma solution sera:

Trier toutes les pièces par le coût stud.
Pour chaque morceau dans la liste triée, essayez de placer autant que vous pouvez dans la plaque:
- Raster une image 2D de votre conception à la recherche pour les régions de l'image avec une couleur uniforme, la forme de la pièce en cours et les montants gratuits pour chaque montant que la pièce utilisera.
- Si la couleur de la région trouvée n'existe pas pour ce morceau particulier, ignorer une recherche continue.
- Si la couleur existe:. Balise les goujons utilisés par morceaux et que incrémenter un compteur pour ce genre de pièce et que la couleur
- Etape 2 sera faite une fois pour des morceaux carrés, deux fois pour pièces rectangulaires (une fois vertical et horizontal une fois) et 4 fois pour les pièces de coin.
Itérer à 2 jusqu'à ce que la plaque est pleine ou pas plus type de pièces sont disponibles.

Une fois arrivé à la fin, vous aurez le nombre de pièces de chaque type et chaque couleur que vous avez besoin avec un coût minimum.

Si le coût par des talons peut changer par la couleur, la liste triée d'origine doit inclure non seulement le type de pièce par la couleur aussi.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow