Packungsproblem für Behälter
Dieser Online-Rechner löst ein Packungsproblem für Behälter mit verschiedenen heuristischen Algorithmen.
Dieser Rechner bezieht sich auf das Packungsproblem für Behälter.
Anders beschrieben handelt es darum, dass es eine bestimmte Menge an Behältern und ein Satz Objekte in verschiedenen Größen gibt (natürlich ist das Volumen von den einzelnen Elementen kleiner als das Volumen eines Behälters). Es ist nun nötig, die verschiedenen Elemente in die minimale Anzahl von Behältern zu packen.
Es gibt ein Beispiel aus dem Leben – es gibt einen Satz von Dateien (z.B. Filme) in verschiedenen Größen. Nun möchte man diese Dateien auf die minimale Anzahl von DVDs.
Dies ist ein NP-Problem, was bedeutet, dass man eine optimale Lösung finden muss, um eine Liste zu erstellen. Jedoch gibt es heuristische Algorithmen, um die angemessene Lösung zu finden. Wenn man Glück hat, ist es die optimale…
Hier ist der Rechner und der Algorithmus ist weiter unten beschrieben. Und obwohl mit den Standardwerten einige Lösungen gleich sind, sind die Algorithmen immer noch anders, und auch andere Daten erkennbar anders sind.
Packungsproblem für Behälter
Menge von Elementen zum verpacken
| | | ||
|---|---|---|---|
Fangen wir mit dem nächste-Passform Algorithmus an.
Nächste-Passform Algorithmus
In den meisten Fällen ist der Algorithmus langweilig gibt die schlechtesten Ergebnisse allen verfügbaren Algorithmus.
Die Essenz von diesem Algorithmus ist wie folgt:
- Nimm ein neues Element.
- Nimm einen neuen Behälter.
- Das Element in den Behälter stellen.
- Nimm das nächste Element.
- Wenn das Element in den Behälter passt, wieder zu Schritt 3 gehen. Wenn es nicht in den Behälter passt, wieder zu Schritt 2 gehen.
So man packt Elemente einfach in den Container, und wenn es nicht passt, nimmt man einfach den nächsten Behälter.
Es ist möglich, einen anderen besseren Algorithmus zu entwickeln, aber dieser hat einen positiven Effekt – man muss die vorherigen Behälter nicht überprüfen. Daher ist er nützlich, z.B. wenn Behälter auf einem Förderband kommt.
Erste-Passform Algorithmus
Die Essenz von diesem Algorithmus ist wie folgt:
- Nimm ein neues Element.
- Nimm einen neuen Behälter.
- Das Element in den Behälter stellen.
- Nimm das nächste Element.
- Wenn das Element in den Behälter passt, wieder zu Schritt 3 gehen. Wenn es nicht in den Behälter passt, die anderen Behälter in Reihenfolge überprüfen. Wenn ein Behälter noch genug Platz hat, das Element in den Behälter platzieren und dann zu Schritt 4 gehen, oder sonst zu Schritt 2.
Dies bedeutet, man legt ein Element in den Behälter, und falls es nicht mehr passt, versucht man einen passenden Behälter von den teilweise gefüllten zu finden. Wenn man keins findet, nimmt man einen neuen Behälter.
Schlechteste-Passform Algorithmus
Die Essenz von diesem Algorithmus ist wie folgt:
- Nimm ein neues Element.
- Nimm einen neuen Behälter.
- Das Element in den Behälter stellen.
- Nimm das nächste Element.
- Wenn das Element in den Behälter passt, wieder zu Schritt 3 gehen. Wenn es nicht in den Behälter passt, nimmt man den Behälter mit dem meisten freien Platz und legt es dort rein. Falls das Element dort reinpasst, legt man es in diesen Behälter und geht zu Schritt 4, sonst folgt man Schritt 2.
In diesem Verfahren legt man das Element in den Behälter, und wenn es nicht reinpasst, wählt man den Behälter, der den meisten Platz bietet. Sonst wählt man einen neuen Behälter.
Beste-Passform Algorithmus
Die Essenz von diesem Algorithmus ist wie folgt:
- Nimm ein neues Element.
- Nimm einen neuen Behälter.
- Das Element in den Behälter stellen.
- Nimm das nächste Element.
- Wenn das Element in den Behälter passt, wieder zu Schritt 3 gehen. Wenn es nicht in den Behälter passt, nimmt man den Behälter mit dem wenigsten freien Platz und legt es dort rein. Falls das Element dort reinpasst, legt man es in diesen Behälter und geht zu Schritt 4, sonst folgt man Schritt 2.
In diesem Verfahren legt man das Element in den Behälter, und wenn es nicht reinpasst, wählt man den Behälter, der den wenigsten Platz übrighat, aber noch genug Platz für das Element übrighat. . Falls dies nicht funktioniert, wählt man einen neuen Behälter.
Man sollte noch erwähnen, dass es eine Variante mit abnehmender Vorsortierung gibt - Abnehmende Erste-Passform, Abnehmende Beste-Passform, etc. Es ist das gleiche, aber die Elemente werden nach Größe ausgewählt, das Größte zuerst. Es wurden 8 Algorithmen überprüft, aber der Rechner verwendet nur 4. Diese sind vorausgewählt, da sie die besten Ergebnisse vorzeigen.
Kommentare