|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 07 Oct 2001 10:36:40
To : Rick Hustle
Subject : Re: Распределение файлов по CD
--------------------------------------------------------------------------------
Rick Hustle wrote:
> ...
> AT> Правильно я понимаю условие?
> Всё правильно за исключеним:
> H=Vf/(Vm - 10) может оказаться не верхней границей кол-ва CD.
> Пример: Размер CD 700 Мб. И есть 3 файла по 400Мб. Распихаются только на 3
> CD, а Vf/(Vm - 10)=1.73 Округляем вверх получаем 2.
> ...
Ок, я почему-то решил, что требование забить диск так, чтобы осталось не
более 10Mb свободного семта является обязательным.
Еще одна деталь. В исходном условии задачи есть такая фраза:
"Под оптимумом подразумевается что-бы как можно большее кол-во болванок
было забито с свободным местом <=10Mb."
Я сначала понял эту фразу так, что надо забить как можно _больше_
болванок. И при этом соблюсти условие, что свободного места на болванке
должно быть не более 10 Мб. Теперь я сомневаюсь в том, что я понял
условие правильно. Теперь я склоняюсь к мысли, что ты имел в виду
несколько иное: надо заполнить болванки как можно более плотно (т.е.
использовать как можно _меньше_ болванок), а фраза про 10Мб приведена
просто для иллюстации того, что болванки надо заполнить плотно.
Если задача состоит именно в _минимизации_ количества использованных
болванок (кстати, тогда эта величина 10Мб вообще к формальному условию
задачи не относится), то получается обыкновенная задача одномерного
раскроя (one dimensional cutting-stock problem) на минимизацию
количества израсходованного материала. Эта задача является NP-полной,
что означает, что существование эффективного алгоритма для ее точного
решения весьма маловероятно.
Если тебе нужно именно точное решение, то придется организовывать
перебор. Он совсем не обязательно должен быть, как ты говоришь, "тупым".
Я думаю, метод ветвей и границ тут может неплохо сработать.
Из непереборных решений можно предложить эвристики. Решение будет,
разумеется, приближенным, т.е. оптимальность размещения файлов не
гарантируется. Первым вспоминается такой эвристический алгоритм (его
упоминает Igor Krassikov в соседнем письме):
"Выбрать самый большой файл, который может поместиться на данную
болванку. Затем выбрать самый большой из оставшихся файлов, который
может поместиться на оставшееся место и т.д. пока на эту болванку еще
можно что-то поместить. Затем "начать" следующую болванку и т.д., пока
все файлы не будут размещены." (1)
Можно применить и такой алогритм:
"Отсортировать файлы в порядке _возрастания_ их размеров и помещать их
на текущую болкванку начиная с самого маленького, до тех пор пока
болванка не заполнится. Затем "начать" следующую болванку и т.д., пока
все файлы не будут размещены." (2)
Hасколько я помню из университетского курса, алгоритмы (1) и (2) в общем
случае дают одинаково качественное решение, хоть это и не очевидно. Т.е.
есть такие наборы входных данных, на которых лучше работает алгоритм
(1), а есть такие, на которых лучше работает алгоритм (2). Стандартным
приемом является прогон на входном наборе обоих алгоритмов с последующим
выбором лучшего из двух решений.
Помню, что есть еще и третий эвристический алгоритм, связанный, кажется,
с хитрым предварительным разбиением файлов на пары. Причем это алгоритм
по качеству решения превосходит первые два. Hо не могу сейчас вспомнить
деталей. Попробую найти конспект...
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
