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

Перейти к навигации Перейти к поиску
Строка 55: Строка 55:
'''Онлайновые алгоритмы'''
'''Онлайновые алгоритмы'''


Три из вышеупомянутых алгоритмов (FF, BF и NF) являются ''онлайновыми'', поскольку они упаковывают предметы в заданном порядке, не принимая во внимание размеры или количество последующих предметов. Как было замечено впоследствии во многих контекстах, ограничение онлайновыми ситуациями может серьезно ограничить способность алгоритма производить хорошие решения. Возможно, первым доказанным ограничением такого типа была теорема Яо [ ] о том, что ни один онлайновый алгоритм A для упаковки в контейнеры не может иметь <math>R^{\infty}_{A} < 1,5</math>. С тех пор это ограничение было улучшено до следующего:


Три из вышеупомянутых алгоритмов (FF, BF и NF) являются онлайновыми, поскольку они упаковывают предметы в заданном порядке, не принимая во внимание размеры или количество последующих предметов. Как было замечено впоследствии во многих контекстах, ограничение онлайновыми ситуациями может серьезно ограничить способность алгоритма производить хорошие решения. Возможно, первым доказанным ограничением такого типа была теорема Яо [ ] о том, что ни один онлайновый алгоритм A для упаковки в контейнеры не может иметь R1A < 1:5. С тех пор это ограничение было улучшено до следующего:


'''Теорема 6 [23]. Если A – онлайновый алгоритм для упаковки контейнеров, то <math>R^{\infty}_{A} \ge 1,540...</math>


Теорема 6 [23]. Если A – онлайновый алгоритм для упаковки контейнеров, тоRf > 1:540:::


В данном случае точное значение нижней границы является решением сложной линейной программы.


В данном случае точное значение нижней границы является решением сложной линейной программы.


В работе Яо также был представлен онлайн-алгоритм ''Revised First Fit'' (RFF), который имел <math>R^{\infty}_{RFF} = 5/3 = 1,666...</math>  и, следовательно, был ближе к этой нижней границе, чем FF и BF. Этот алгоритм работал путем разделения предметов на четыре класса по критерию размера и индекса, а затем использования различных правил упаковки (и самих упаковок) для каждого класса. Последующие алгоритмы улучшали его за счет введения все большего количества классов. В настоящее время самым эффективным является онлайновый алгоритм ''Harmonic++'' (H++) из работы [21]:


В работе Яо также был представлен онлайн-алгоритм Revised First Fit (RFF), который имел RRFF1 = 5/3 = 1:666  и, следовательно, был ближе к этой нижней границе, чем FF и BF. Этот алгоритм работал путем разделения предметов на четыре класса по критерию размера и индекса, а затем использования различных правил упаковки (и самих упаковок) для каждого класса. Последующие алгоритмы улучшали его за счет введения все большего количества классов. В настоящее время самым эффективным является онлайновый алгоритм Harmonic++ (H++) из работы [21]:


Теорема 7 [21].
'''Теорема 7 [21]. <math>R^{\infty}_{H++} \le 1,58889.</math>




'''Алгоритмы с ограниченным количеством контейнеров'''
'''Алгоритмы с ограниченным количеством контейнеров'''


Алгоритм NF, помимо того, что он работает в режиме онлайн, обладает еще одним свойством, которое стоит отметить: в любой момент времени для приема дополнительных предметов остается открытым не более чем постоянное число частично заполненных контейнеров. В случае NF эта константа равна 1 – поместить дополнительные предметы можно только в последний частично заполненный контейнер. Ограничение количества открытых контейнеров может быть необходимо в некоторых приложениях, например, при загрузке грузовиков на погрузочных платформах. Однако это обстоятельство накладывает дополнительные ограничения на поведение алгоритма.
Алгоритм NF, помимо того, что он работает в режиме онлайн, обладает еще одним свойством, которое стоит отметить: в любой момент времени для приема дополнительных предметов остается открытым не более чем постоянное число частично заполненных контейнеров. В случае NF эта константа равна 1 – поместить дополнительные предметы можно только в последний частично заполненный контейнер. Ограничение количества открытых контейнеров может быть необходимо в некоторых приложениях, например, при загрузке грузовиков на погрузочных платформах. Однако это обстоятельство накладывает дополнительные ограничения на поведение алгоритма.
Источник — http://pco.iis.nsk.su/wega/index.php/Задача_об_упаковке_в_контейнеры