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

Перейти к навигации Перейти к поиску

Задача об упаковке в контейнеры (посмотреть исходный код)

Версия от 20:35, 21 января 2024

123 байта добавлено ,  21 январь
→‎Основные результаты
Строка 15: Строка 15:


'''Поведение в наихудшем случае'''
'''Поведение в наихудшем случае'''


'''Асимптотические отношения в наихудшем случае'''
'''Асимптотические отношения в наихудшем случае'''


Для большинства задач минимизации стандартной метрикой наихудшего случая для аппроксимационного алгоритма 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>. Оно определяется в два этапа следующим образом.


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


<math>R^n_A = max \{ A(L)/OPT(L): L</math> – список с <math>OPT(L) = n\}</math>


RnA = max fA(L)/OPT(L): L – список с OPT(L) = ng R1A = lim sup RA
<math>R_A^{\infty} = lim_{n \to \infty} sup \; R^n_A</math>




Первым алгоритмом, поведение которого было проанализировано в этих терминах, был First Fit (FF). Этот алгоритм представляет себе бесконечную последовательность пустых контейнеров B1;B2; и, начиная с первого элемента входного списка L, помещает каждый предмет по очереди в первый контейнер, в котором для него еще есть место. В техническом отчете 1971 года, ставшем одной из первых работ, в которой изучались коэффициенты эффективности в наихудшем случае, Уллман [22] доказал следующее:
Первым алгоритмом, поведение которого было проанализировано в этих терминах, был ''First Fit'' (FF). Этот алгоритм представляет себе бесконечную последовательность пустых контейнеров <math>B_1, B_2, ...</math> и, начиная с первого элемента входного списка L, помещает каждый предмет по очереди в первый контейнер, в котором для него еще есть место. В техническом отчете 1971 года, ставшем одной из первых работ, в которой изучались коэффициенты эффективности в наихудшем случае, Уллман [22] доказал следующее:




Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/15333

Навигация