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

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




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




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




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


Теорема 3 [13].


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




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