4551
правка
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 20:39, 21 января 2024
, 21 январь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
Теорема 1 [22]. | '''<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) – варианты этих алгоритмов, в которых входной список сначала сортируется по размеру в порядке невозрастания, а затем применяется соответствующее правило упаковки. Для этих алгоритмов получены следующие результаты. | ||
'''<math>Теорема 2 [12]. R^{\infty}_{NF} = 2.</math>''' | |||
Теорема 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>''' | |||
