ПОИСК Статьи Чертежи Таблицы Алгоритм решения задачи об упаковке многомерных объектов из "Объективные модели и субъективные решения " Рассмотрим поставленную выше задачу без условия (2), т. е. предположим, что имеется множество равноценных объектов, подлежащих упаковке в заданные контейнеры, причем требуется максимизировать количество упакованных объектов. [c.70] Идея алгоритма АО может быть использована для упаковки многомерных объектов. Пусть рассматриваются объекты с двумя физическими параметрами (объем и вес) и соответствующими контейнерами. [c.71] Построим список объектов со специальным чередованием [6] на первом месте поставим объект с самым большим весом, на втором — с самым большим объемом из оставшихся, на третьем — с самым большим весом из оставшихся и т. д. К организованному таким образе м списку применим алгоритм АО для нахождения приближенного минимального числа контейнеров, в которое можно упаковать все объекты. Если это число превышает заданное, будем последовательно отбрасывать объекты из начала списка и применять к оставшимся алгоритм ПП до тех пор, пока не удастся упаковать все оставшиеся объекты в заданное число контейнеров. Полученный алгоритм назовем АОЧ (алгоритм с отбрасыванием при чередовании). [c.71] Оценка алгоритма АОЧ проводилась [6] методом Монте-Карло [7]. Схема статистических испытаний состояла из следующих этапов генерация оптимального варианта упаковки применение алгоритма АОЧ к сгенерированному множеству объектов. [c.71] Отметим также, что в вычислительном отношении алгоритм АОЧ прост для реализации. Он может быть аналогичным образом использован и при большем количестве физических параметров объектов. [c.72] Вернуться к основной статье