Создание алгоритма черепицы для заданного пространства

Question

Мы должны создать алгоритм, чтобы полностью заполнить заданное пространство HxW. У нас есть 125 тестовых конфигураций с заданным набором плиток, который может заполнить поле. Код для набора плиток и поля указан, и нам нужно написать код, который может поместить плитки и заполнить поле (вы можете поменять их, если необходимо). У кого-то есть предложения о том, как создать такой алгоритм, потому что мы застряли и у вас нет вдохновения.

Мы создали жадный алгоритм, который сначала заполняет самые большие плитки, а затем пытается вписаться в маленькие, но это только разрешило 1 набор плиток и застряло с большими наборами плиток.

Под 2 Данные конфигурации:

ширина: 12 высота: 17 шкала: 20 2 раза 5x5 1 раз 7x3 3 раза 5x4 1 раз 5x3 1 раз 6x2 1 раз 3x3 2 раза 4x2 1 раз 6x1 1 раз 3x2 1 раз 2х2 1 раз 3x1 1 раз 2x1

ширина: 42 высота: 39 шкала: 10 1 раз 15x14 1 раз 14x14 1 раз 14x8 1 раз 11x9 1 раз 12x6 1 раз 14x5 1 раз 11x6 1 раз 16x4 1 раз 12x5 1 раз 10х5 2 раза 8х6 2 раза 8x5 1 раз 9x4 1 раз 6x6 1 раз 7x5 2 раза 6x5 1 раз 7x4 1 раз 6х4 1 раз 10x2 1 раз 5x4 3 раза 6x3 2 раза 7x2 1 раз 12x1 2 раза 6x2 1 раз 11x1 1 раз 10x1 1 раз 5x2 1 раз 8x1 1 раз 6x1 2 раза 3x2 1 раз 5x1 2 раза 2х2 3 раза 3x1 3 раза 2x1 1 раз 1x1

Answer 1

Конечно, это проблема NP-hard (NP-complete, если вы только хотите знать, возможно ли это, но похоже, что вы уже пообещали это, и в любом случае вам нужна какая-то конфигурация) не является чисто плохая вещь - в то время как это означает, что это, вероятно, не будет чрезмерно эффективным, это также предлагает много углов атаки, так что это не нужно подходить с нуля.

Например целочисленного линейного программирования, с помощью модели, такие как (ну это довольно простой один)

minimize: 0 
subject to: 
for all (x,y), sum[all i such that tp[i] covers (x,y)] x[i] = 1 
for all tiles k, sum[all i such that tp[i] is tile k] x[i] = 1 

Где tp содержит все возможные «плитки-размещения», с копией каждый раз, когда для в каждом месте, в котором он может находиться.

Первая партия ограничений заставляет все позиции в сетке покрываться плиткой, вторая ванна ограничений заставляет все плитки использоваться ровно один раз.

С помощью этого я мог бы решить 42x39 экземпляр:

Другие приемы могут быть необходимы для больших экземпляров. Некоторые из сокращений, упомянутых here, применяются, но когда я решаю это с Gurobi, он проводит больше времени, чтобы найти приемлемое решение, а не столько в целочисленной фазе.