Задача: возьмите изображение 48x48, найдите смежные области, которые приводят к самым дешевым решению LEGO, чтобы создать это изображение! [закрыто

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

Вопрос

Фон

LEGO производит X-large grey снимая, которая представляет собой большую строительную пластину шириной 48 шпильков и высотой 48 шпильков, в результате чего общая площадь 2304 шпильки. Будучи фанатиком LEGO, я смоделировал несколько конструкций в стиле мозаики, которые можно положить на эти базовые панели, а затем, возможно, повесить на стены или на дисплее (см. Android, Театр мечты, Галактическая империя, Покемон).

Соревнование

Теперь моя задача состоит в том, чтобы получить самую низкую стоимость, чтобы приобрести эти дизайны. Покупка 2304 индивидуальные 1x1 пластины могут стать дорогими. С использованием Кирпич, по сути, eBay для LEGO, я могу найти данные, чтобы определить, какие самые дешевые детали для заданных цветов. Например, пластина 1x4 в 0,10 долл. США (или 0,025 долл. США за шпильку) будет дешевле, чем пластина 6x6 в 2,16 долл. США (или 0,06 долл. США за шпильку). Мы также можем определить список всех возможных пластин, которые можно использовать для сборки изображения:

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

Проблема

Для этой проблемы давайте предположим, что у нас есть список всех тарелок, их цвет (ы) и «вес» или стоимость для каждой тарелки. Ради простоты, мы можем даже снять угловые кусочки, но это было бы интересной задачей для решения. Как бы вы нашли самые дешевые компоненты для создания изображения 48x48? Как бы вы нашли решение, которое использует наименьшее количество компонентов (не обязательно самое дешевое)? Если бы мы добавили угловые кусочки в качестве допустимых кусочков, как бы вы их учитывали?

Мы можем предположить, что у нас есть какой -то основной список, который получен путем запроса Bricklink, получения средней цены для данного кирпича в заданном цвете и добавив это в качестве элемента в списке. Таким образом, не было бы черной тарелки 16x16 просто потому, что она не сделана или не продается. Ярко -зеленая пластина 16x16, однако, составит 3,74 долл. США, что будет текущая доступная средняя цена.

Я надеюсь, что моя статья о проблеме достаточно успешно. Это то, о чем я думал уже несколько дней, и мне любопытно, что вы думаете, ребята. Я пометил его как «вопросы интервью», потому что это сложно, а не потому, что я получил это через интервью (хотя я думаю, что это был бы забавный вопрос!).

РЕДАКТИРОВАТЬ

Вот ссылка на 2x2 угловой кусок и в 4x4 угловой кусок. Анкет Ответ не обязательно должен учитывать цвет, но он должен быть расширяемым, чтобы покрыть этот сценарий. Сценарий будет заключаться в том, что не все пластины доступны во всех цветах, поэтому представьте, что у нас есть множество элементов, которые идентифицируют тарелку, ее цвет и среднюю стоимость этой пластины (пример ниже). Спасибо Бенджамину за обеспечение щедрости!

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

В этом списке не было бы записи:

8x8|yellow|imaginarydollaramount

Это потому, что желтая пластина 8x8 не существует. Сам список тривиальен и должен рассматриваться только как о предоставлении ссылок на решение; Это не влияет на само решение.

Edit2

Изменил некоторую формулировку для ясности.

Это было полезно?

Решение

Подход Карла в основном звучит, но может использовать некоторые больше деталей. Он найдет оптимальное решение для затрат, но будет слишком медленным для определенных входов. Большие открытые площадки особенно будут иметь слишком много возможностей для поиска наивно.

В любом случае, я сделал быструю реализацию в C ++ здесь: http://pastebin.com/s6fpubmc

Он решает заполнение пустого пространства (периоды), с 4 различными видами кирпича:

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

Таким образом, алгоритм заполняется в данной области. Это рекурсивно (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
}

После того, как мы выясним самый дешевый способ заполнить подразделение, мы кэшируем результат. Чтобы очень эффективно идентифицировать подразделение, мы будем использовать 64-разрядное целое число Зобрист хешинг. ПРЕДУПРЕЖДЕНИЕ: Хэш -столкновения могут привести к неправильным результатам. Как только наша рутина возвращается, мы можем реконструировать оптимальное решение на основе наших кэшированных значений.

Оптимизация:В примере исследуются узлы 41936 (рекурсивные вызовы) (поиск пустых квадратных верхних до спинкой). Однако, если мы ищем пустые квадраты слева направо, исследуется ~ 900 000 узлов.

Для больших открытых площадок: Я бы посоветовал найти наиболее экономичную часть и заполнить большую часть открытой площадки этим произведением в качестве предварительного процесса. Другой метод - разделить ваше изображение на несколько регионов и оптимизировать каждую область отдельно.

Удачи! Я буду недоступен до 26 марта, так что, надеюсь, я ничего не пропустил!

Другие советы

Шаги

Шаг 1: Итерация через все решения.

Шаг 2: Найдите самое дешевое решение.

Создайте инвентаризацию произведений

Для множества возможных кусочков (включайте отдельные части каждого цвета), сделайте как минимум N дубликатов каждого произведения, где n = max (плата#/кусок# из каждого цвета). Следовательно, максимум n этого произведения может охватить все цвета всей платы по площади.

Теперь у нас есть огромная коллекция возможных предметов, ограниченных потому, что гарантируется, что подмножество этой коллекции полностью заполнит доску.

Затем это становится проблемой подмножества, которая является NP-полным.

Решение проблемы подмножества

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)

Оптимизация

Очевидно, что является алгоритмом O (2^n), рано обрезка дерева поиска имеет первостепенное значение. Оптимизация должна быть сделана рано, чтобы избежать длительных. n - очень большое количество; Просто рассмотрим доску 48x48 - у вас есть 48x48xc (где C = количество цветов) только для отдельных кусочков.

Следовательно, 99% дерева поиска должны быть обрезаны из первых нескольких сотен сложников, чтобы этот алгоритм завершился в любое время. Например, сохраните подсчет из самых низких затрат, найденных до сих пор, и просто прекратите поиск всех более низких слоев и возврата в возврат всякий раз, когда текущая стоимость плюс (количество пустых положений платы x самая низкая средняя стоимость для каждого цвета)> Текущее решение о самых низких затратах.

Например, в первую очередь еще больше оптимизируйте, всегда предпочитая самые большие части (или самые низкие показатели средней стоимости), чтобы как можно быстрее снизить базовое решение с самой низкой стоимостью и обрезать как можно больше будущих случаев.

Найти самое дешевое

Рассчитайте стоимость каждого решения, найдите самое дешевое!

Комментарии

Этот алгоритм общий. Он не предполагает, что кусок одинакового цвета (у вас могут быть разноцветные кусочки!). Он не предполагает, что большая часть дешевле, чем сумма более мелких кусочков. Это на самом деле ничего не предполагает.

Если могут быть сделаны некоторые предположения, то эта информация может быть использована для дальнейшей обрезки дерева поиска как можно раньше. Например, при использовании только одноцветных кусочков вы можете обрезать большие секции платы (с неправильными цветами) и обрезать большое количество кусочков в наборе (неправильного цвета).

Предложение

Не пытайтесь сделать 48x48 одновременно. Попробуйте что -то маленькое, скажем, 8x8, с достаточно небольшим набором кусочков. Затем постепенно увеличивайте количество предметов и размера доски. Я действительно понятия не имею, сколько времени займет программа - но хотел бы, чтобы кто -нибудь сказал мне!

Сначала вы используете наводнение, чтобы разбить проблему в заполнение непрерывных регионов кирпичей Lego. Затем для каждого из тех, что вы можете использовать DFS с запоминанием. Заполнение наводнения тривиально, поэтому я не буду описать это дальше.

Обязательно следите за правилом правой руки, расширяя дерево поиска, чтобы не повторять состояния.

Мое решение будет:

  1. Сортируйте все кусочки по стоимости.
  2. Для каждой части в списке отсортировки попробуйте поместить как можно больше на тарелку:
    • Растрое 2D изображение вашего дизайна в поисках регионов изображения с равномерным цветом, формой текущего куска и свободных шпильков для каждого шпилька, который будет использовать произведение.
    • Если цвет найденного региона не существует для этой конкретной части, игнорируйте продолжение поиска.
    • Если цвет существует: пометьте шпильки, используемые этими кусочками, и увеличьте счетчик для такого рода кусочков и этого цвета.
    • Шаг 2 будет сделан один раз для квадратных кусочков, дважды для прямоугольных кусочков (один раз вертикальный и один раз горизонтальный) и 4 раза для угловых кусочков.
  3. Итерация до 2 до тех пор, пока тарелка не будет заполнена или больше не будет доступно.

После прибытия до конца у вас будет количество кусочков каждого вида и каждый цвет, который вам нужен с минимальной стоимостью.

Если стоимость заглушает может измениться по цвету, то исходный сортированный список должен включать не только тип произведения также по цвету.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top