4551
правка
Задача об упаковке в контейнеры: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры | Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры работает весьма эффективно. Это алгоритм Кармаркара-Карпа 1982 года [15], который далее будет обозначаться как KK. Он использует метод эллипсоидов, аппроксимационные алгоритмы для задачи о рюкзаке и хитроумную схему округления для получения следующих гарантий: | ||
'''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа c такая, что для всех списков L выполняется соотношение''' | '''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа <math>c</math> такая, что для всех списков L выполняется соотношение''' | ||
<math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math> | <math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math> | ||