Тайлинг, как использовать рекурсию в этом случае?

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

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

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

Как вы можете видеть, когда FieldRightWidth решен и FieldBelowHeight также решен, я хочу, чтобы он вернулся к предыдущей плитке, чтобы проверить, решен ли FieldBelow. Я думаю, что именно здесь мне нужно поместить некоторый код, чтобы это заработало, но после нескольких часов гугления я так и не понял.

Псевдокод:

def Methods:
   create global tileset
   create local tileset (without duplicates)

   If globaltiles is empty: 
      solved    
      end
   else:
           if fieldRightWidth == solved:                  
               if fieldBelowHeight == solved:
                   return True???
               #FIELD BELOW
               else:
                    Search for Tile
                    Place Tile
                    Return Methods

           #FIELD RIGHT       
           else:
                Search for Tile
                Place Tile
                Return Methods

И изображение того, что я хочу, чтобы алгоритм делал: введите здесь описание изображения

И весь код: http://pastebin.com/8t4PeiZP

http://www.filedropper.com/tilingnew

Я все еще новичок в кодировании, поэтому любые советы или помощь очень ценятся!


python python-2.7 recursion algorithm tiling
person L.B    schedule 26.01.2016    source источник
comment
Есть ли у ваших ящиков приоритет? почему бы не заполнить область фиолетовым размером 1x1?   -  person Bear    schedule 26.01.2016
comment
У меня есть три приоритета, основанные на их ширине, высоте и величине. В примере шага 2 (после размещения зеленой плитки) я хотел бы перейти к полю A на этом шаге. Это поле — это то, что я имею в виду под полем ниже, но как мне его закодировать, чтобы он знал, что нужно перейти в это поле? Кроме того, если бы эта зеленая плитка была разрезана пополам по вертикали, тогда ей пришлось бы смотреть на левую половину плитки (то есть не на последнюю размещенную плитку, а на ту, что перед ней) и смотреть на поле ниже, соответствующее этой плитке. Вот тут-то и появляется рекурсия, но я действительно не знаю, как это сделать.   -  person L.B    schedule 26.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

хорошо, давайте подумаем, что площадь, которую вы хотите вычислить, является либо квадратной, либо прямоугольной (не повернутой), она начинается с минимального [x, y] и заканчивается максимальным [x, y] справа, например:

SMaxX = 5
SMinX = 0
SMaxY = 5
SMinY = 0

или, если вы знакомы с 2D-вектором, вы можете оптимизировать его следующим образом:

S = [5,5]

возможно, вы знаете о 2D-векторе, на всякий случай я объясню, что такое вектор в 2D-декартовых координатах:
введите здесь описание изображения S = [5,5] означает, что если S начинается с [0,0], оно заканчивается на [5,5], (проще ведь?)
поэтому и ящики будут такими:

#space each box taking
box1 = [3,3]
box2 = [2,2]
box3 = [1,1]

и так как у каждого ящика есть приоритет, скажем:

#priority of each box
box1 = 6
box2 = 4
box3 = 2

мы можем объединить пробел и приоритет в словарь следующим образом:

#Items
dic = {'box1':{'space':[3,3] , 'priority ':6},
       'box2':{'space':[2,2] , 'priority ':4},
       'box3':{'space':[1,1] , 'priority ':2}}

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

однако диаграмма алгоритма задачи Knapsack представляет собой одномерное решение, и если вы это сделаете, вы получите 10, поэтому Box1 и Box2. но поскольку это 2D, и у вас разные высота и ширина, поэтому стандартная формула 1D не будет работать, возможно, вам нужно изучить ее, чтобы посмотреть, сможете ли вы придумать формулу 2D, или поспрашивать, не делал ли кто-нибудь это раньше.

введите здесь описание изображения введите здесь описание изображения

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

вам нужно установить стандартный размер, например 1x1, а затем определить всю область с данными 1x1, сохранить ее в переменной и установить каждое значение True (логическое), затем с более высоким приоритетом полей заполнить область и установить для этих 1x1 дату False, тогда очень легко можно проверить, сколько из них True и какую область они занимают.

в любом случае, я пытаюсь понять то же самое в неправильной форме, так что это все, что я узнал, надеюсь, что это поможет вам.
(проверьте это

person Bear    schedule 26.01.2016