LINUX.ORG.RU
ФорумTalks

Нужен алгоритм


0

0

Есть прямоугольное поле и произвольное количество объектов (не более 10 обычно). Площадь каждого объекта известна, форму можно менять (но она должна оставаться прямоугольной). Нужна фигня которая бы расчитала оптимальное расположение объектов на поле.

★★★

хорошо бы ввести определение оптимальности для данного случая.

qnikst ★★★★★
()
Ответ на: комментарий от dimon555

>целочисленное программирование?

Вполне возможно :-) Ткните мордочкой в ссылку, если не сложно, бо я даже не знаю что искать.

PS: я журналист по образованию. Мне это надо для расчета расположения статей и рекламных модулей на полосе ))

gnunixon ★★★
() автор топика

Генерируешь случайно раз 100-1000 свое поле, высчитываешь по алгоритму оптимальность, и выбираешь самый оптимальный из вариантов

xorik ★★★★★
()
Ответ на: комментарий от xorik

>Генерируешь случайно раз 100-1000 свое поле

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

gnunixon ★★★
() автор топика
Ответ на: комментарий от gnunixon

Значит площадь всех объектов в сумме должна быть равна прощади поля.
Если по условию прощади объектов можно менять , оптимально на мой взгляд в данном случае будет следующее расположение:
Пусть s1 , s2 , s3 , ... , sn - площади объектов (они даны)
X - ширина поля
Y - длина поля (причем X <= Y в случае равенства мы имеем дело с квадратным полем )
Проще и оптимальнее всего (ИМХО) сделать форму объектов такой , чтобы
одна из сторон каждого объекта равнялась ширине поля (то есть X)
Тогда остальные стороны будут соответственно равны :
s1/X , s2/X , s3/X , ... , sn/X.

Реализуется все в виде простого цикла.
Все это имеет место при условии если я правильно понял условие задачи

ssk85
()
Ответ на: комментарий от gnunixon

> Мне это надо для расчета расположения статей и рекламных модулей на полосе ))

не стоит это автоматизировать.

ananas ★★★★★
()
Ответ на: комментарий от gnunixon

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

xorik ★★★★★
()
Ответ на: комментарий от ssk85

>Если по условию площади объектов можно менять
Если по условию задачи форму можно менять fixed

одна из сторон каждого объекта равнялась ширине поля (то есть X)

То же самое справедливо для Y

ssk85
()
Ответ на: комментарий от ssk85

>Проще и оптимальнее всего (ИМХО) сделать форму объектов такой , чтобы одна из сторон каждого объекта равнялась ширине поля

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

gnunixon ★★★
() автор топика
Ответ на: комментарий от xorik

форму же можно менять . А при таком условии все вообще легко (как у меня)

ssk85
()
Ответ на: комментарий от ananas

>не стоит это автоматизировать.

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

gnunixon ★★★
() автор топика
Ответ на: комментарий от gnunixon

значит формализуйте задачу )
И если оптимальность это чтобы красиво было , тогда вообще все субъективно

ssk85
()
Ответ на: комментарий от gnunixon

Может этот же рандом оптимизировать с помощью ГА?

Yareg ★★★
()
Ответ на: комментарий от gnunixon

А если так , то все дело в отступах.
Я думаю если их учесть, то задача немного усложниться , но не совсем)

ssk85
()
Ответ на: комментарий от gnunixon

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

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

ananas ★★★★★
()

Ищи в google «алгоритм оптимального раскроя», «packing problem»(наверное, то, что надо тебе конкртено из этого раздела — это «tiling problem»). Задачки нетривиальные.

Zubok ★★★★★
()

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

Спасибо, товарищи :-)

gnunixon ★★★
() автор топика
Ответ на: комментарий от gnunixon

Значит оптимальность здесь можно посчитать как -<пустая площадь>-n*<число блоков шириной 5 или высотой более 6>?

Yareg ★★★
()

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

HighwayStar ★★★★★
()

будем отвечать так же чётко, как и поставлен вопрос :)

сравнить сумму площадей объектов и поля на всякий случай

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

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

оптимальность очевидна ибо критериев нету :)

dimon555 ★★★★★
()

См. «исследование операций», «динамическое программирование» и т.п.

FeiWongReed
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.