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

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




'''<math>Теорема 1 [22]. R^{\infty}_{FF} = 17/10.</math>'''
'''Теорема 1 [22]. <math>R^{\infty}_{FF} = 17/10.</math>'''




Строка 35: Строка 35:




'''<math>Теорема 2 [12]. R^{\infty}_{NF} = 2.</math>'''
'''Теорема 2 [12]. <math>R^{\infty}_{NF} = 2.</math>'''


'''Теорема 3 [13]. <math>R^{\infty}_{BF} = 17/10.</math>'''


'''<math>Теорема 3 [13]. R^{\infty}_{BF} = 17/10.</math>'''
'''Теорема 4 [12, 13]. <math>R^{\infty}_{FFD} = R^{\infty}_{BFD} = 11/9 = 1,222...</math>'''




'''<math>Теорема 4 [12, 13]. R^{\infty}_{FFD} = R^{\infty}_{BFD} = 11/9 = 1,222...</math>'''
Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры действительно очень хорош. Это алгоритм Кармаркара-Карпа 1982 года [15], который далее будет обозначаться как KK. Он использует метод эллипсоидов, аппроксимационные алгоритмы для задачи о рюкзаке и хитроумную схему округления для получения следующих гарантий:




Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры действительно очень хорош. Это алгоритм Кармаркара-Карпа 1982 года [15], который далее будет обозначаться как KK. Он использует метод эллипсоидов, аппроксимационные алгоритмы для задачи о рюкзаке и хитроумную схему округления для получения следующих гарантий:
'''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа c такая, что для всех списков L выполняется соотношение
 


Теорема 5 [15]. R1KK = 1 и существует константа c такая, что для всех списков L,
<math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math>
KK(L) < OPT(L) + c log2 (OPT(L)) :




К сожалению, время работы KK оказывается больше O(n8), и BFD и FFD остаются гораздо более практичными альтернативами.
К сожалению, время работы KK оказывается больше <math>O(n^8)</math>, так что BFD и FFD остаются гораздо более практичными альтернативами.




Источник — http://pco.iis.nsk.su/wega/index.php/Задача_об_упаковке_в_контейнеры