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