Рис. 12.7
С интуитивной точки зрения этот алгоритм кажется весьма разумным. Он не начинает заполнять новый контейнер, пока среди контейнеров есть хотя бы один, в который можно поместить очередной предмет.
Проанализируем насколько близко к оптимальному решение, полученное алгоритмом «в первый подходящий». Вначале рассмотрим число контейнеров, требующихся для указанного алгоритма, как функцию от параметров задачи. Обозначим эту функцию как FF(r). Имеют место неравенства:
FF(r}> 1
FF(7)<[2 is(Uin i=\
Последнее неравенство следует из того, что в результате работы алгоритма не может получиться более одного контейнера, заполненного более чем на половину. В противном случае первый же предмет, попавший в такой контейнер с наибольшим номером, должен быть помещен алгоритмом «в первый подходящий», т.е. такой же контейнер с тем же номером. То, что указанная граница наилучшая из возможных, следует из рассмотрения индивидуальной задачи V= {С/1, U2, ... Un}, где S(Ui) = Vi + г; \ < i < п. Поскольку никакие два предмета не могут попасть в один ящик, то FF(r) = «, в то время как сумма размеров предметов равна п/2 + пе и если е достаточно малое, то она будет как угодно близка к п/2.
Сделанное замечание позволяет нам также оценить, во сколько раз плохое решение, получаемое алгоритмом «в первый подходящий» может отличаться от оптимального решения задачи. Поскольку ясно, что
ОРГ(/)>[Г5(С/0], / = 1
то отсюда вытекает, что для всех индивидуальных задач I вытекает неравенство FF{I) < 20РТ(1).
В [34] приводится теорема, что для FF(I) имеется лучшая оценка.
Теорема 12.2. Для всех индивидуальных задач / об упаковке имеет место неравенство FF(I) < 17/10 ОРТ(Г) + 2.
Более того, существует индивидуальная задача /, для которой ОРТ(1) сколь угодно велико FF(l) > 17/10 (ОРТ(1) - 1).
Таким образом, теорема 12.2 характеризует асимптотическое поведение в худшем случае алгоритма «в первый подходящий». Величина FF(r) никогда не отличается от оптимума более чем на 70% и в некоторых случаях такое отличие действительно достигается.
Далее перейдем к анализу алгоритмов с лучшей оценкой поведения. Ясно, что алгоритм «в первый подходящий» можно видоизменить, пользуясь, например, следующим более совершенным правилом размещения: каждый следующий предмет Ui помещать в контейнер, содержимое которого ближе всего к величине 1 - Si(U), но не превосходит ее (если имеется несколько таких контейнеров, то выбирается контейнер с наименьшим номером). Этот алгоритм называется «в наилучший из подходящих». Этот алгоритм, как показано в [34], в наихудшем случае имеет те же характеристики, что и алгоритм «в первый подходящий».
Несколько лучший приближенный алгоритм получается, если учесть, что наихудшей для алгоритма «в первый подходящий» (а также для алгоритма «в наилучший из подходящих») оказывается ситуация, когда в упорядочении предметов предметы с наибольшими размерами идут раньше предметов с наименьшими размерами, т.е. S(U\) > S(U2) > ... > S{Uri). Алгоритм применения процедуры «в первый подходящий» к переупорядоченному таким образом списку предметов называется «в первый подходящий в порядке убывания» (соответствующая функция обозначается FFD(I)y Работа этого алгоритма характеризуется следующей теоремой Джонсона.
Теорема 12.3. Для всех индивидуальных задач об упаковке выполняется неравенство FFD(I) < (11/9) ОРТ(1) + 4.
Более того, существуют индивидуальные задачи, для которых 0РТ{1) произвольно велико и FFD(I) > (11/9) OPT(I).
Таким образом, мы имеем гарантию, что алгоритм «в первый подходящий в порядке убывания» даже в худшем случае выдает решение, отличающееся от оптимального не более чем на 22%. Более того, встречаются задачи, для которых эта оценка достигается. Такой же результат
имеет место для аналогичного алгоритма «в наилучший из подходящих в порядке убывания».
Нетрудно понять причину, в силу которой желательно иметь такие оценки погрешностей приближенных алгоритмов. Даже если конкретная оценка погрешности не столь сильна как хотелось бы, тем не менее весьма разумно начать решение задачи с простого алгоритма, имеющего такую оценку погрешности, а затем улучшить ее, пользуясь более совершенными эвристиками и методами оптимизации. Естественно, наибольший интерес для нас представляет, в какой степени наш алгоритм «на практике» будет приближен к оптимальному. В качестве альтернативы к анализу погрешности алгоритмов «в худшем случае» можно было бы попытаться оценить погрешность «в среднем». Изучение поведения алгоритмов «в среднем» чаще всего сводится к формированию типовых индивидуальных задач и апробации нескольких алгоритмов на этих задачах с последующим сравнением результатов.