Симферопольский Форум: Математико-программерская задача - Симферопольский Форум

Перейти к содержимому

Внимание! Для всех новых пользователей введена премодерация сообщений и тем.
Страница 1 из 1
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

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

#1 Пользователь офлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 18 149
  • Регистрация: 20 сентября 10
  • Страна:  

Отправлено 04 июля 2012 - 20:14

Привет всем!

Имеется задача по программированию:
-------------------------------------------------------------------------------
Дано (все величины - целочисленные):
  • площадка X*Y
  • число плиток N
  • плитки прямоугольной формы.
  • соотношение длин сторон плитки от 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.
  • Максимальная и минимальная площади плитки - Smax и Smin. То есть, имеется ограничение плитки по размеру. Например, если Smax = 4 и Smin = 1, то возможны плитки размеров 1х1, 1х2, 1х3, 2х1, 2х2, 3х1, но не 2х3 или 4х1.

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

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


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

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

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

"Конец России хотели бы увидеть многие, но пока его удается только подержать за щекой…!" (с)

Изображение

#2 Гость_feo-gabber_*

  • Группа: Гости

Отправлено 04 июля 2012 - 21:33

Просмотр сообщенияИнквизитор (04 июля 2012 - 20:14) писал:

Привет всем!

Имеется задача по программированию:
-------------------------------------------------------------------------------
Дано (все величины - целочисленные):
  • площадка X*Y
  • число плиток N
  • плитки прямоугольной формы.
  • соотношение длин сторон плитки от 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.
  • Максимальная и минимальная площади плитки - Smax и Smin. То есть, имеется ограничение плитки по размеру. Например, если Smax = 4 и Smin = 1, то возможны плитки размеров 1х1, 1х2, 1х3, 2х1, 2х2, 3х1, но не 2х3 или 4х1.

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

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


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

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

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


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


#3 Пользователь офлайн   Rumlin 

  • Добрый волшебник
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 42 159
  • Регистрация: 16 сентября 10
  • ГородHavana
  • Страна:  

Отправлено 04 июля 2012 - 21:36

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


Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов
Ничего не делается к лучшему © Борис Раушенбах
Люди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский

#4 Пользователь офлайн   SamSa 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 702
  • Регистрация: 15 сентября 10

Отправлено 04 июля 2012 - 22:27


Оффтопик:


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


Поблагодарили: 1

#5 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 372
  • Регистрация: 16 сентября 10
  • Страна:  

Отправлено 04 июля 2012 - 22:52

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


#6 Пользователь офлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 18 149
  • Регистрация: 20 сентября 10
  • Страна:  

Отправлено 04 июля 2012 - 22:53

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

Просмотр сообщенияfeo-gabber сказал:

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

Просмотр сообщенияfeo-gabber сказал:

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

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

Просмотр сообщенияfeo-gabber сказал:

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

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

Просмотр сообщенияfeo-gabber сказал:

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

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

"Конец России хотели бы увидеть многие, но пока его удается только подержать за щекой…!" (с)

Изображение

#7 Пользователь офлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 18 149
  • Регистрация: 20 сентября 10
  • Страна:  

Отправлено 04 июля 2012 - 23:06

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

Похоже, вырисовалась подзадача математического плана:
Сгенерировать N пар случайных чисел (a,b ), таких, что:
1. Сумма всех произведений a*b = X*Y
2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b
3. Smin <= a*b <= Smax

"Конец России хотели бы увидеть многие, но пока его удается только подержать за щекой…!" (с)

Изображение

#8 Гость_feo-gabber_*

  • Группа: Гости

Отправлено 05 июля 2012 - 00:08

Просмотр сообщенияИнквизитор (04 июля 2012 - 23:06) писал:

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

Похоже, вырисовалась подзадача математического плана:
Сгенерировать N пар случайных чисел (a,b ), таких, что:
1. Сумма всех произведений a*b = X*Y
2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b
3. Smin <= a*b <= Smax

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


#9 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 372
  • Регистрация: 16 сентября 10
  • Страна:  

Отправлено 05 июля 2012 - 00:20

Просмотр сообщенияИнквизитор сказал:

Но есть нюанс: заранее неизвестны размеры "выкроек"
Понял, сразу не до конца уловил суть задачи.
Что-то чем дольше думаю над ней, тем более чудовищное количество вариантов перебора представляется...

Просмотр сообщенияИнквизитор сказал:

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

X=1 Y=12
N=3
Smin=4 Smax=4
a=2 b=2

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


#10 Пользователь офлайн   FreeLSD 

  • Живу здесь
  • PipPipPipPipPip
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 12 498
  • Регистрация: 16 сентября 10
  • Страна:  

Отправлено 05 июля 2012 - 08:21

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

Или что-то случилось, или одно из двух.

#11 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 372
  • Регистрация: 16 сентября 10
  • Страна:  

Отправлено 05 июля 2012 - 11:59

Просмотр сообщенияFreeLSD сказал:

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

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


#12 Пользователь офлайн   FreeLSD 

  • Живу здесь
  • PipPipPipPipPip
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 12 498
  • Регистрация: 16 сентября 10
  • Страна:  

Отправлено 05 июля 2012 - 12:09

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

Или что-то случилось, или одно из двух.

#13 Пользователь офлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 18 149
  • Регистрация: 20 сентября 10
  • Страна:  

Отправлено 05 июля 2012 - 12:21

Просмотр сообщенияfeo-gabber сказал:


Похоже, вырисовалась подзадача математического плана:
Сгенерировать N пар случайных чисел (a,b ), таких, что:
1. Сумма всех произведений a*b = X*Y
2. 1/k <= a/b <= k, где k - заданное максимальное соотношение a/b
3. Smin <= a*b <= Smax

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



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

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

"Конец России хотели бы увидеть многие, но пока его удается только подержать за щекой…!" (с)

Изображение

#14 Пользователь офлайн   zerg 

  • Пользователь
  • PipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Пoльзователь
  • Сообщений: 17
  • Регистрация: 07 июня 12
  • ГородSimfer

Отправлено 05 июля 2012 - 21:57

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


#15 Гость_feo-gabber_*

  • Группа: Гости

Отправлено 05 июля 2012 - 22:28

Просмотр сообщенияzerg (05 июля 2012 - 21:57) писал:

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

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

Сообщение отредактировал feo-gabber: 05 июля 2012 - 22:30


#16 Пользователь офлайн   Eugene 

  • Юджин
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 1 653
  • Регистрация: 16 сентября 10
  • ГородСимферополь

Отправлено 05 июля 2012 - 22:32

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

Просмотр сообщенияИнквизитор сказал:

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

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

Жизнь - вечная борьба: до обеда с голодом, после обеда со сном.

Поделиться темой:


Страница 1 из 1
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей