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

Ответ 1

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

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

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

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 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-битное целое, используя Zobrist хеширование. Предупреждение: столкновение с хешем может привести к неправильным результатам. Как только наша процедура вернется, мы сможем восстановить оптимальное решение на основе наших кешированных значений.

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

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

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

Ответ 2

Действия

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

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

Создание инвентаря предметов

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

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

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

Решение задачи подмножества

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, с достаточно маленьким набором штук. Затем постепенно увеличивайте количество штук и размер доски. Я действительно не знаю, как долго будет проходить программа - но мне бы хотелось, чтобы кто-нибудь сказал мне!

Ответ 3

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

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

Ответ 4

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

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

Как только вы дойдете до конца, у вас будет количество штук каждого вида и каждого цвета, который вам нужен, с минимальными затратами.

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