Задача об упаковке в контейнеры: различия между версиями

Для большинства задач минимизации стандартной метрикой наихудшего случая для аппроксимационного алгоритма A является максимальное для всех экземпляров I отношение A(I)/OPT(I), где A(I) – величина решения, генерируемого A, а OPT(I) – величина оптимального решения. Однако в случае упаковки контейнеров имеются ограничения на эту метрику «абсолютно наихудшего отношения». Задача определения того, является ли OPT(I) = 2, уже является NP-трудной – и, следовательно, ни один аппроксимационный алгоритм с полиномиальным временем выполнения не может иметь абсолютное наихудшее отношение лучше 1,5, если не выполняется P = NP. Чтобы лучше понимать поведение алгоритмов упаковки в контейнеры в типичной ситуации, когда заданный список L требует большого количества контейнеров, исследователи используют более тонкую метрику упаковки – ''асимптотическое отношение в наихудшем случае'', <math>R_A^{\infty}</math>. Оно определяется в два этапа следующим образом.

В дополнение к FF, еще пять простых эвристик были изучены в самом начале и послужили вдохновением для более поздних исследований. ''Best Fit'' (BF) – это вариант задачи FF, в котором каждый предмет помещается в контейнер, в который он может поместиться с наименьшим остатком свободного места; при наличии нескольких подходящих вариантов выбирается самый ранний из таких контейнеров. И FF, и BF могут быть реализованы за время O(n log n) [12]. ''Next Fit'' (NF) – еще более простой алгоритм с линейным временем выполнения, в котором первый предмет помещается в первый контейнер, а каждый следующий предмет помещается в последний непустой контейнер, если он в него помещается, в противном случае открывается новый контейнер. ''First Fit Decreasing'' (FFD) и ''Best Fit Decreasing'' (BFD) – варианты этих алгоритмов, в которых входной список сначала сортируется по размеру в порядке невозрастания, а затем применяется соответствующее правило упаковки. Для этих алгоритмов получены следующие результаты.