| dbpprop:abstract
|
- In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used. There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media. Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time, where n is the number of elements to be packed. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.
- Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl <math>k \in \mathbb{N}</math> von „Behältern“ der Größe <math>b \in \mathbb{N}</math> und eine Anzahl <math>n \in \mathbb{N}</math> „Objekte“ mit den Größen <math> a_1,a_2,.. ,a_n\ \leq\ b </math>. Frage: Können die <math>n</math> „Objekte“ so auf die <math>k</math> „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft? Formal: <math> \exists\ f : \{1,.. ,n\} \to \{1,.. ,k\}\ \mbox{, so dass }\forall\ j := 1,.. ,k \quad \sum_{f(i)=j} a_i \leq b \mbox{ gilt ?}</math> Das oben beschriebene Entscheidungsproblem ist NP-vollständig; das zugehörige Optimierungsproblem – das Finden einer Zuordnung, bei der die Anzahl an Behältern minimiert wird – ist NP-schwer. Die hier gegebene Formulierung des Bin-Packing-Problems ist nur die Motivation beziehungsweise Basis für eine Vielzahl weiterer Packing-Problems, die unter anderem in der Verpackungsindustrie eine große Rolle spielen. Eine etwas allgemeiner formale Definition beschreibt das Bin-Packing-Problem als die Bestimmung einer Partition und Zuordnung einer Menge von Objekten, so dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird.
- Le problème de bin packing relève de la recherche opérationnelle et de l'optimisation combinatoire. Il s'agit de trouver le rangement le plus économique possible pour un ensemble d'articles dans des boîtes. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux ou trois dimensions.
- ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。 様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。
- В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими. Существует множество разновидностей этой задачи, которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д. Так как задача является NP-трудной зачастую используют алгоритмы с эвристическим и метаэвристическим методом решения для получения оптимальных результатов. Также активно используются методы искусственного интеллекта, как, например, нейронные сети. Стратегии Best Fit Decreasing и First Fit Decreasing используют не более <math>\frac{11}{9}N + 1</math> контейнеров (где <math>N</math> - число контейнеров при наилучшем решении задачи). Однако, существуют алгоритмы приближения, которые могут решить задачу об упаковке с любым наперёд заданным процентом наилучшего решения для больших массивов исходных данных (они называются асимптотической схемой приближения полиномиального времени). Всё это выделяет задачу среди большинства других основных NP-трудных задач, некоторые из которых не могут быть приближены вообще.
|
| rdfs:comment
|
- In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used. There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on.
- Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl <math>k \in \mathbb{N}</math> von „Behältern“ der Größe <math>b \in \mathbb{N}</math> und eine Anzahl <math>n \in \mathbb{N}</math> „Objekte“ mit den Größen <math> a_1,a_2,.. ,a_n\ \leq\ b </math>.
- Le problème de bin packing relève de la recherche opérationnelle et de l'optimisation combinatoire. Il s'agit de trouver le rangement le plus économique possible pour un ensemble d'articles dans des boîtes. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux ou trois dimensions.
- В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача.
|
![[RDF Data]](/statics/sw-cube.png)
