Задача об упаковке в контейнеры

Задача об упаковке в контейнеры

В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.

Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т.п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т.д.

Так как задача является NP-трудной зачастую используют алгоритмы с эвристическим и метаэвристическим методом решения для получения оптимальных результатов. Также активно используются методы искусственного интеллекта, как, например, нейронные сети.

Стратегии Best Fit Decreasing и First Fit Decreasing используют не более \frac{11}{9}N + 1 контейнеров (где N - число контейнеров при наилучшем решении задачи). Однако, существуют алгоритмы приближения, которые могут решить задачу об упаковке с любым наперёд заданным процентом наилучшего решения для больших массивов исходных данных (они называются асимптотической схемой приближения полиномиального времени). Всё это выделяет задачу среди большинства других основных NP-трудных задач, некоторые из которых не могут быть приближены вообще.

Примечания

См. также

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Задача об упаковке в контейнеры" в других словарях:

  • Задача о рюкзаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача о рюказаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача трехмерной упаковки в объем — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… …   Википедия

  • Операций исследование — Исследование операций (ИО) (англ. Operations Research (OR)) дисциплина, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе математического моделирования, статистического моделирования и различных эвристических …   Википедия

  • Исследование операций — Эту страницу предлагается объединить с Наука управления. Пояснение причин и обсуждение на странице Википедия:К объединению/18 декабря 2012 …   Википедия

  • Числа Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух… …   Википедия

  • Последовательность Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия

  • Ряд Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия

  • Фибоначчи числа — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия

  • Числа Фиббоначчи — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»