Может алгоритмы дефрагментации и посмотреть?| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм по оптимизации |
| Автор: Cyberholic 1.8.2011, 00:15 |
| Доброго времени суток! У меня стоит задача составить алгоритм, решающий описанные ниже задачи. К сожалению, я очень мало об этом знаю и пока в самом начале пути и подумала может знающие люди смогут подсказать направление. СПАСИБО ОГРОМНОЕ заранее! Итак задача: Получить наибольшее непрерывное количество свободного пространства в ряду на полках с минимальным количетсвом шагов (перестановок книг на полке или с полки на полку), показать вариант (как выглядит полка, какие книги где) с мин количеством шагов, с кол шагов min-1, min-2 и т.д. Данные: Шкаф с полками и книгами на одном ряду. Надо максимизировать количество свободного пространства в РЯДУ (несколько полок). Есть несколько типов книг: роман, детектив и приключения. Роман нельзя перемещать, они должны остаться на своих местах. Все остальные можно свободно перемещать. Расстояние на полках и размер книг измеряем в миллиметрах. Опция: отдавать предпочтение перемещению книг одного и того же автора, что бы они стояли рядом... Вот так вот... Спасибо за помощь! |
| Автор: afiskon 1.8.2011, 04:37 |
| Условия совершенно невнятные, но похоже на вариацию задачи оптимизации (линейного или целочисленного программирования - повторюсь, условия невнятные). Алгоритмы решения таких задач давно расписаны, можно, например, их в вики найти. |
| Автор: Lipetsk 1.8.2011, 08:03 |
| По-моему все просто: смотрим сколько всего есть свободных мест, ищем на полках место под это количество, чтобы там было побольше свободного места и с этого места книги убираем с учетом предпочтения |
| Автор: _Y_ 4.8.2011, 22:29 |
| Что-то мне напоминает дефрагментацию жесткого диска. Даже системные файлы романы имеются Может алгоритмы дефрагментации и посмотреть? |
| Автор: Cyberholic 16.8.2011, 23:02 | ||
| Soglasna! Pohozhe na defragemntaciyu diska, s odnoi raznicei--mne nuzhno minimalnoe kolichestvo shagov. Zdes nuzhna funkciya kakaya-nibud? Ya iskala slovesnie algortimi defragmentacii diska, no nochego ne nashla v internete. Ne podskazhete gde mozhno poiskat? SPASIBO! Ochen ochen nuzho! Добавлено через 3 минуты и 3 секунды
Skazhite pozhaluista, kakie imeeno uslaviya neponyatni, ya poprobuyu obyasnit po drugomu... Ya, esli chestno, absolyutno v etom novichek, smotrela v wikipedia, no ne nashla reshenie podobnih zadach. Esli vi imeete vvidu chto-to konkretnoe, daite ssilku pozhaluista... SPASIBO! |
| Автор: _Y_ 18.8.2011, 20:42 |
| Cyberholic, к сожалению, конкретно алгоритмами дефрагментации я не занимался. Ничего определенного подсказать не могу. Просто высказал идею. Но дефрагментаторы точно бывают быстрые и медленные и при разработке это их свойство, судя по всему, учитывается как-то. Зы: Руглишь читать сложно. Слева-внизу есть галочка. Помогает если у Вас нет русской клавиатуры. |
| Автор: Cyberholic 22.8.2011, 23:00 |
| С оптимизацией я более менее разобралась. Вот никак не соображу следующее: Если есть начальный вид полки с книгами и конечный вид полки с оптимизированным пространством как найти минимальное количество перестановок книг за которое можно получить данный конечный результат??? |
| Автор: Lipetsk 23.8.2011, 08:15 |
| Cyberholic, а вам именно количество или алгоритм нужен? если алгоритм, то тут все просто: 1. переставляете только книги, которые не на своих местах, а их новые места свободны 2. когда такие кончаются, т.е. остаются книги не на своих местах, но новые места для них заняты, то переставляете одну из таких книг на свободное место (желательно на то, которое будет свободно и в конечной расстановке) и переходите к пункту 1 |
| Автор: _Y_ 23.8.2011, 23:34 | ||
А нельзя ли нарисовть эту систему перестановок в виде графа и искать кратчайший путь в графе? |
