Математико-программерская задача

[Инквизитор]

Привет всем!

 

Имеется задача по программированию:

-------------------------------------------------------------------------------

Дано (все величины - целочисленные):

1. площадка X*Y
   
2. число плиток N
   
3. плитки прямоугольной формы.
   
4. соотношение длин сторон плитки от a:b до b:a То есть, если a = 1 и b = 3, то возможны плитки с соотношением сторон 1:1, 1:2, 1:3, 2:1, 2:2, 2:3, 3:1, 3:2, 3:3.
   
5. Максимальная и минимальная площади плитки - Smax и Smin. То есть, имеется ограничение плитки по размеру. Например, если Smax = 4 и Smin = 1, то возможны плитки размеров 1х1, 1х2, 1х3, 2х1, 2х2, 3х1, но не 2х3 или 4х1.
   

Надо замостить площадку плитками так, чтобы выполнялись следующие требования:

1. все N плиток должны поместиться на площадке
   
2. на площадке не должно остаться незакрытых мест
   
3. размеры плиток и их расположение должны быть случайным
   

Желательно:

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

 

В общем, должно получиться что-то такое (расцветил для наглядности):

-------------------------------------------------------------------------------

 

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

 

Пока меня хватило только на это:

1) проверить, решаема ли задача вообще (помещаются ли N плиток на площадку): Smin * N <= X*Y

[Guest feo-gabber]

Привет всем!

 

Имеется задача по программированию:

-------------------------------------------------------------------------------

Дано (все величины - целочисленные):

1. площадка X*Y
   
2. число плиток N
   
3. плитки прямоугольной формы.
   
4. соотношение длин сторон плитки от a:b до b:a То есть, если a = 1 и b = 3, то возможны плитки с соотношением сторон 1:1, 1:2, 1:3, 2:1, 2:2, 2:3, 3:1, 3:2, 3:3.
   
5. Максимальная и минимальная площади плитки - Smax и Smin. То есть, имеется ограничение плитки по размеру. Например, если Smax = 4 и Smin = 1, то возможны плитки размеров 1х1, 1х2, 1х3, 2х1, 2х2, 3х1, но не 2х3 или 4х1.
   

Надо замостить площадку плитками так, чтобы выполнялись следующие требования:

1. все N плиток должны поместиться на площадке
   
2. на площадке не должно остаться незакрытых мест
   
3. размеры плиток и их расположение должны быть случайным
   

Желательно:

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

 

В общем, должно получиться что-то такое (расцветил для наглядности):

-------------------------------------------------------------------------------

 

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

 

Пока меня хватило только на это:

1) проверить, решаема ли задача вообще (помещаются ли N плиток на площадку): Smin * N <= X*Y

 

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

[*]все N плиток должны поместиться на площадке

[*]размеры плиток и их расположение должны быть случайным(это уже попахивает случайным перебором из хрен его знает скольких возможных вариантов)

[*]распределение плиток должно быть равномерным(это уж точно не из области программинга или математики - совершенно не определенное понятие)

[*]задача должна решаться, если часть плиток (M) уже имеет заданные размеры и находится в определенных местах площадки.(а это противоречит предыдущим проблемным пунктам)

[Rumlin]

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

[SamSa]

Оффтопик:

windows 8 делаете? :)

[SlavaD]

Подозреваю, что надо делать поиск по фразе "Алгоритм раскроя". Однозначного решения тут не будет, скорее всего, что-то похожее на решение перебором, с дальнейшими попытками оптимизации, слишком большое количество вариантов.

[Инквизитор]

SamSa, ага, нечто похожее =)

распределение плиток должно быть равномерным(это уж точно не из области программинга или математики - совершенно не определенное понятие)

эм... я как раз думал,что "равномерное распределение" - это как раз сугубо математическое понятие. А имею в виду вот что:

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

размеры плиток и их расположение должны быть случайным(это уже попахивает случайным перебором из хрен его знает скольких возможных вариантов)

Почему-то мне кажется, что как раз перебор вариантов и не потребуется.

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

Хм... не вижу противоречия.

Имею такую мысль:

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

здесь все очень не просто

Ну, было бы просто, не писал бы тут =)

[Инквизитор]

SlavaD, алгоритм раскроя плюс перебор вариантов оного раскроя? Возможно... Но есть нюанс: заранее неизвестны размеры "выкроек".

 

Похоже, вырисовалась подзадача математического плана:

Сгенерировать N пар случайных чисел (a,b ), таких, что:

1. Сумма всех произведений a*b = X*Y

2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b

3. Smin <= a*b <= Smax

[Guest feo-gabber]

SlavaD, алгоритм раскроя плюс перебор вариантов оного раскроя? Возможно... Но есть нюанс: заранее неизвестны размеры "выкроек".

 

Похоже, вырисовалась подзадача математического плана:

Сгенерировать N пар случайных чисел (a,b ), таких, что:

1. Сумма всех произведений a*b = X*Y

2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b

3. Smin <= a*b <= Smax

Вы не понимаете разницы между математическими формулами и логики работы программы - это очень печально.... :(

[SlavaD]

Но есть нюанс: заранее неизвестны размеры "выкроек"

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

Что-то чем дольше думаю над ней, тем более чудовищное количество вариантов перебора представляется...

 

1) проверить, решаема ли задача вообще (помещаются ли N плиток на площадку): Smin * N <= X*Y

X=1 Y=12

N=3

Smin=4 Smax=4

a=2 b=2

 

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

[FreeLSD]

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

[SlavaD]

В двумерном - очень сложно, ресурсоемко и все равно наполовину вручную.

А в поставленной выше задаче еще и размеры деталей можно менять, считайте 3-е измерение ;). С одной стороны данная возможность увеличивает шансы, что задача будет решаема, с другой точно так-же увеличивает количество вариантов. Как по мне, решить однозначно данную задачу невозможно, в теории может получиться составить алгоритм который будет работать в некоторых несложных ситуациях.

 

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

[FreeLSD]

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

[Инквизитор]

 

Похоже, вырисовалась подзадача математического плана:

Сгенерировать N пар случайных чисел (a,b ), таких, что:

1. Сумма всех произведений a*b = X*Y

2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b

3. Smin <= a*b <= Smax

 

Вы не понимаете разницы между математическими формулами и логики работы программы - это очень печально.... :(

 

 

?

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

Как бы, с одной стороны, "я не волшебник, а только учусь" =)

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

 

Конкретно по данной подзадаче - для чего она нужна: решив ее, я получу готовый набор плиток; останется выяснить, можно ли ими замостить площадку. Это как бы часть одного пути; другой путь - вначале рандомно разложить по площадке N плиток единичного размера, а потом рандомно менять им размеры и двигать - пока что подвис в воздухе.

[zerg]

мля, программеры х от у ,данная задачарешается методом Кантаровича-Данцига

[Guest feo-gabber]

мля, программеры х от у ,данная задачарешается методом Кантаровича-Данцига

Если бы... такое можно было решить без тупого перебора на одних лишь формулах - не нужно бы было изобретать машину времени(а нахрена она нужна если все можно предвидеть и предрасчетать???)

эта задача так просто не разрешаема - уж поверь.

не приветствую высеры в достаточно нагруженных темах по математике, собственно как и на программерских

Edited July 5, 2012 by feo-gabber

[Eugene]

если бы не это условие

2. число плиток N

то, можно сказать, я нашел решение задачи

но как рандомно расставить заведомо известное кол-во плиток - увы, пока не знаю :(