Помогите с АЛГОРИТМом

← →
Igor M. (2008-06-16 15:51) [0]

Голова кипит)
Пожалуйста, поделитесь мыслями, если у кого имеются.

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

Или по другому если кто не понял):
Есть деревянные заготовки по 2 метра.
Есть массив нужных по длине отрезков.
Необходимо просчитать как оптимально разрезать заготовки.

Любую идею... плиз...

← →
андр. (2008-06-16 15:59) [1]

> 2 метра.
> Есть массив нужных по длине отрезков.
> Необходимо просчитать как оптимально разрезать заготовки.
>

2:4 ?

← →
Igor M. (2008-06-16 16:10) [2]

немножко не понял )
вы имеете ввиду поделить заготовку на 4 части рамки?

нет.

допустим исходные данные:

1. рамка 200x100 мм.
2. рамка 200x300 мм.
3. рамка 300x400 мм.
4. рамка 500x200 мм.

получаем необходимо:
1. два отрезка по 200 два по 100
2. два отрезка по 200 два по 300
3. два отрезка по 300 два по 400
4. два отрезка по 500 два по 200

или 6 отрезков по 200 два по 300 по одному 100, 400, 500

у нас есть заготовки по 2 метра.
вот теперь надо прогаммно просчитать как оптимально разрезать заготовки.

в данном случаи например можно:

одна заготовка - 5*200 + 2*300 + 400 = 2 метра
ну и на второй заготовке: 200 + 100 + 500

но это образно, в реалии будет много исходных разных данных...

← →
Igor M. (2008-06-16 16:23) [3]

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

← →
Milk (2008-06-16 16:32) [4]

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

> Пожалуйста, поделитесь мыслями, если у кого имеются.

Других мыслей здесь быть не может

← →
Igor M. (2008-06-16 16:39) [5]

Эх...)))

Milk, а можно на моем примере исходных данных составить систему линейных уравнений и целефую функцию (:

стыдно, но я если и знал то точно забыл)

хоть примерно как это выгядит...

← →
Igor M. (2008-06-16 16:39) [6]

Эх...)))

Milk, а можно на моем примере исходных данных составить систему линейных уравнений и целефую функцию (:

стыдно, но я если и знал то точно забыл)

хоть примерно как это выглядит...

← →
Milk (2008-06-16 16:45) [7]

> Igor M. (16.06.08 16:39) [6]

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

← →
Igor M. (2008-06-16 16:45) [8]

я так понимаю что вы имеете ввиду под линейными фунциями типа l1= h1*2 + w1*2 ?

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

а вот "целевую функцию (минимизация отходов)" это вообще не понятно)

← →
Igor M. (2008-06-16 17:00) [9]

"не исключено, что меня забанят"

фигасе до чего дошел прогресс)
раньше уж иногда помогали, вначале посоревновавшись в усмешках,
а тут уже банить даже стали..

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

← →
Igor M. (2008-06-16 17:22) [10]

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

← →
clickmaker © (2008-06-16 18:01) [11]

сортируем по убыванию длин отрезков
начинаем "резать" рейки с наибольшего Dec(StripLen[i], SegmentLen[j])
дошли до момента, когда рейки не хватает - перебираем оставшиеся отрезки, пока остаток рейки не будет минимальным (в идеале - ноль)
ну и т.д.
как-то так

← →
Игорь Шевченко © (2008-06-16 19:28) [12]

Эх, народ.
А раньше писали алгоритмы оптимального заполнения дискеты файлами...

← →
Anatoly Podgoretsky © (2008-06-16 20:12) [13]

> Игорь Шевченко (16.06.2008 19:28:12) [12]

Что бы без дырок и каждый байт был занят.

← →
palva © (2008-06-16 23:40) [14]

А почему минимизация отходов, да и что это такое: общая длина обрезков или их количество? Вообще-то в [0] шла речь о количестве потребовавшихся реек. А может быть, нужно минимизировать количество разрезов или нужна какая-то взвешенная сумма всего упомянутого. Автор ведь не говорит, что такое "оптимальным образом", и, если говорить строго, вообще не имеет четко поставленной задачи.

← →
Igor M. (2008-06-17 00:08) [15]

palva ©, Всё я имею, для себя же пишу прогу)
И думаю понятно, что "оптимальным образом" - это значит использовать наименьшее колличество реек.

clickmaker ©, спасибо большое за идею.
но если рассматривать мой приведенный мелкий пример, то имеем:

необходимо:
1. два отрезка по 200 два по 100
2. два отрезка по 200 два по 300
3. два отрезка по 300 два по 400
4. два отрезка по 500 два по 200

отрезаем:
500+500+400+400+100 = 1.9 (10 сантиметров отходы)

поэтому желательно как и написал:
первая заготовка - 5*200 + 2*300 + 400 = 2 метра

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

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

Игорь Шевченко ©, пиши хоть 1 байт все равно сектор займет...

← →
palva © (2008-06-17 00:16) [16]

> И думаю понятно, что "оптимальным образом" - это значит
> использовать наименьшее колличество реек.

Тогда это старинная задача о волке, козе и капусте. И надо сначала почитать, что на эту тему уже понаписано:
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B5_%D0%B2_%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D1%8B

← →
Igor M. (2008-06-17 00:25) [17]

palva ©, во! искусственный интеллект и нейронные сети будут попроще "целевой функции" )))

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

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

← →
Igor M. (2008-06-17 00:32) [18]

Игорь Шевченко ©, наконец-то до меня дошло)))
да, кстати почти то же самое...
примерно не можете сказать где это обсуждалось?
если всё таки результат какой-то был..)

← →
Igor M. (2008-06-17 00:59) [19]

я что-то и свой вариант не могу реализовать)

помогите, как найти сумму наиболее приближенную?

тоесть по-другому условие такое:

есть массив значений 0...n-1
необходимо найти элементы, сумма которых наиболее приближена к некоему значению X

з.ы.
старость не радость.. что-то вообще голова не варит...

← →
palva © (2008-06-17 01:00) [20]

Эвристика - это правдоподобные рассуждения, основанные на здравом смысле. В ветке их много.

← →
palva © (2008-06-17 01:03) [21]

> Igor M. (17.06.08 00:59) [19]

А все числа неотрицательные?

← →
palva © (2008-06-17 01:12) [22]

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

← →
Igor M. (2008-06-17 01:14) [23]

palva ©, подсказал бы лучше если знаешь)

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

← →
Германн © (2008-06-17 01:15) [24]

> Игорь Шевченко © (16.06.08 19:28) [12]

Дык и сейчас пишут. Riply так вообще пошла дальше. Фиг поймёшь чего она пишет! :)

> Igor M. (17.06.08 00:59) [19]

>
> з.ы.
> старость не радость.. что-то вообще голова не варит...
>

Сочувствую. Сам такой. Старость действительно не радость. Глаза, руки, ноги подводят постоянно. Особенно глаза.
Но голова вроде в порядке. :)

← →
Igor M. (2008-06-17 01:19) [25]

palva © , вот и я об том же!

только непонял насчет " Если полный перебор вариантов невозможен"
нам всё возможно! было бы желание)

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

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

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

← →
palva © (2008-06-17 01:46) [26]

> только непонял насчет " Если полный перебор вариантов невозможен"
> нам всё возможно! было бы желание)

Тогда какие проблемы? Перебирайте все суммы (их 2^n) и выбирайте ту из них, которая ближе всего к x.

← →
Igor M. (2008-06-17 01:54) [27]

я вот подумал, вероятно данный метод то же не годиться.

например, есть рейки по 1 метру.
необходимо иметь кускиЖ
- 10 штук по 100 см
- 10 штук по 600
- 10 штук по 300

поиском приближенных сумм я сразу выйду на разрез первой рейки на 10 отрезков по 100 см. ну и потом 10 реек потрачу на 600+300, из которых по 100 см. будет отходов. Отсюда явно видно, что лучший вариант - затрата 10 реек по 600+300+100.

Мда.. видать и правда простая на вид задача оборачивается совсем не простым алгоритмом..
Теперь меня терзают сомнения, - возможно ли вообще это реализовать..)))

ч
> разрез первой рейки на 10 отрезков по 100 см.

А сколько по-вашему в метре сантиметров, если из метровой рейки вы получаете 10 отрезков по 100 см?

← →
Igor M. (2008-06-17 02:16) [29]

palva © будем считать что забыл нолик дописать в размере одной рейки ))))

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

осталось придумать алгоритм перебора всех вариантов разбивки\разрезки реек..)

> осталось придумать алгоритм перебора всех вариантов разбивки\разрезки
> реек..)

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

> palva (17.06.2008 1:59:28) [28]

В метре все в порядке, если иметь особые метровые линейки.

← →
Igor M. (2008-06-17 09:28) [32]

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

← →
Igor M. (2008-06-17 15:00) [33]

а если использовать алгоритм примерно такой:

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

как средний вариант пойдет?

я так понял математиков тута нету)

> [33] Igor M. (17.06.08 15:00)

а чем это отличается от [11]?

← →
Igor M. (2008-06-17 15:28) [35]

ну я был написал чем вначале не понраивлся данный метод.

"
необходимо:
1. два отрезка по 200 два по 100
2. два отрезка по 200 два по 300
3. два отрезка по 300 два по 400
4. два отрезка по 500 два по 200

отрезаем:
500+500+400+400+100 = 1.9 (10 сантиметров отходы)

поэтому желательно как и написал:
первая заготовка - 5*200 + 2*300 + 400 = 2 метра

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

думал что есть что-то более точно..., но в результате clickmaker © огромное спасибо!, кажется лучше не придумаешь...

> 500+500+400+400+100 = 1.9 (10 сантиметров отходы)

500+500+400+400+300 - не влезло, берем след. по убыванию после 300
500+500+400+400+200 - влезло

← →
Igor M. (2008-06-17 16:15) [37]

я ещё и с математикой не дружу)
а собрался блин прогу писать...

вообщем СПАСИБО clickmaker ©, единственный дельное подсказал, тока я баран поздно понял..

тему можно закрывать..
начинаю писать прогу)

← →
наблюдатель (2008-06-17 20:05) [38]

http://alglib.sources.ru/combinatorial/backpack.php

http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=60

http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=59

Помогите с АЛГОРИТМом Найти похожие ветки