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

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

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

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

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

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 751
  • Регистрация: 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
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 24 774
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • ГородHavana
  • Страна:  

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

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


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


Какой ты любопытный.

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

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

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


Оффтопик:


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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 751
  • Регистрация: 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 119
  • Регистрация: 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
  • Перейти к галерее
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 7 914
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • Страна:  

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

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

Со временем всё будет хорошо. А вот с нами всякое может случиться...

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

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

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

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

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

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


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

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

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

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

Со временем всё будет хорошо. А вот с нами всякое может случиться...

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

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 751
  • Регистрация: 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 скрытых пользователей