| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Помогите с АЛГОРИТМом
Igor M. © (2008-06-16 15:51:00)Голова кипит)
Пожалуйста, поделитесь мыслями, если у кого имеются.
Есть рейки одинаковой длины, допустим 2 метра.
Собираем рамки, т.е. четырехуголники)
В прогу я вбиваю ширину и высоту нужных рамок и в результате мне прога должна просчитать сколько нужно реек для этого и как оптимально их распилить на куски.
Или по другому если кто не понял):
Есть деревянные заготовки по 2 метра.
Есть массив нужных по длине отрезков.
Необходимо просчитать как оптимально разрезать заготовки.
Любую идею... плиз...
Igor M. (2008-06-17 00:32:00) [21]Игорь Шевченко ©, наконец-то до меня дошло)))
да, кстати почти то же самое...
примерно не можете сказать где это обсуждалось?
если всё таки результат какой-то был..)
Igor M. (2008-06-17 00:25:00) [22]palva ©, во! искусственный интеллект и нейронные сети будут попроще "целевой функции" )))
что ж, почитаю про алгоритмы с эвристическим и метаэвристическим методом решения.
в крайнем случаи хоть буду знать что это такое)
спасибо!
хотя хотелось бы чуть-чуть попроще что-нибудь, хрен уже с теми пару рейками если не такой уж точный будет расчет...
palva (2008-06-17 00:16:00) [23]
> И думаю понятно, что "оптимальным образом" - это значит
> использовать наименьшее колличество реек.
Тогда это старинная задача о волке, козе и капусте. И надо сначала почитать, что на эту тему уже понаписано:
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:08:00) [24]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-16 23:40:00) [25]А почему минимизация отходов, да и что это такое: общая длина обрезков или их количество? Вообще-то в [0] шла речь о количестве потребовавшихся реек. А может быть, нужно минимизировать количество разрезов или нужна какая-то взвешенная сумма всего упомянутого. Автор ведь не говорит, что такое "оптимальным образом", и, если говорить строго, вообще не имеет четко поставленной задачи.
Anatoly Podgoretsky (2008-06-16 20:12:00) [26]> Игорь Шевченко (16.06.2008 19:28:12) [12]
Что бы без дырок и каждый байт был занят.
Игорь Шевченко (2008-06-16 19:28:00) [27]Эх, народ.
А раньше писали алгоритмы оптимального заполнения дискеты файлами...
clickmaker (2008-06-16 18:01:00) [28]сортируем по убыванию длин отрезков
начинаем "резать" рейки с наибольшего Dec(StripLen[i], SegmentLen[j])
дошли до момента, когда рейки не хватает - перебираем оставшиеся отрезки, пока остаток рейки не будет минимальным (в идеале - ноль)
ну и т.д.
как-то так
Igor M. (2008-06-16 17:22:00) [29]Внимательно прочитал про "симплекс-метод", вообщем это по моему мнению не то.
я даже не представляю как можно составить систему уравнений не говоря уже о целевой функции для данного случая.
по идее мне нужно искать минимумы остатка до 2 метров, но "симплекс-метод" для данного случая мне кажется не применим..
Igor M. (2008-06-16 17:00:00) [30]"не исключено, что меня забанят"
фигасе до чего дошел прогресс)
раньше уж иногда помогали, вначале посоревновавшись в усмешках,
а тут уже банить даже стали..
спасибо за "симплекс-метод", бум искать..
но если у кого будут другие мысли или небольшой пример "целевой функции" буду очень благодарен..
Igor M. (2008-06-16 16:45:00) [31]я так понимаю что вы имеете ввиду под линейными фунциями типа l1= h1*2 + w1*2 ?
в таком случаи кусок из одной рамки может быть использован в разных заготовках, где оптимально его взять.
l1 - периметр рамки, нам ничего не даст.
а вот "целевую функцию (минимизация отходов)" это вообще не понятно)
Milk (2008-06-16 16:45:00) [32]> Igor M. (16.06.08 16:39) [6]
Поиском "симплекс-метод", думаю примеров будет много.
Иначе, не исключено, что меня забанят...
Igor M. (2008-06-16 16:39:00) [33]Эх...)))
Milk, а можно на моем примере исходных данных составить систему линейных уравнений и целефую функцию (:
стыдно, но я если и знал то точно забыл)
хоть примерно как это выглядит...
Igor M. (2008-06-16 16:39:00) [34]Эх...)))
Milk, а можно на моем примере исходных данных составить систему линейных уравнений и целефую функцию (:
стыдно, но я если и знал то точно забыл)
хоть примерно как это выгядит...
Milk (2008-06-16 16:32:00) [35]Обычная задача линейного программирования. Для конкретных данных (сколько каких рамок необходимо) составляешь систему линейных уравнений, целевую функцию (минимизация отходов) и решаешь известными методами.
> Пожалуйста, поделитесь мыслями, если у кого имеются.
Других мыслей здесь быть не может
Igor M. (2008-06-16 16:23:00) [36]у меня мысль искать наибольшую приближенность к 2 метрам путем пробы сумм разных отрезков.
потом их отбрасываем и повторяем для оставшихся
Igor M. (2008-06-16 16:10:00) [37]немножко не понял )
вы имеете ввиду поделить заготовку на 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
но это образно, в реалии будет много исходных разных данных...
андр. (2008-06-16 15:59:00) [38]
> 2 метра.
> Есть массив нужных по длине отрезков.
> Необходимо просчитать как оптимально разрезать заготовки.
>
2:4 ?
| |
Страницы: 