---

Hallo,

ich stelle die Frage mal hier rein, weil es sozusagen mein "Heimatforum" ist.
Mir fällt auch kein wesentlich besserer Platz für dieses Problem ein.

Nehmen wir mal folgende Situation an:
Man hat eine bestimmte Anzahl an Büchern. Jedes Buch hat eine bestimmte Höhe und eine bestimmte Dicke. Nun sollen die Bücher in ein Bücherregal eingeräumt werden, dessen Regalböden in einem bestimmten Raster höhenverstellbar sind (kennt sicher jeder).
Nebenregeln:
In ein Regalfach dürfen max. 8 Bücher gestellt werden.
Überschreitet die Dicke eines Buches ein bestimmtes Maß, so kann auf seinen "Nachbarplätzen" kein Buch abgestellt werden.
Die Bücher-Stellplätze ganz links und ganz rechts in einem Regalfach haben nur einen Nachbarplatz, alle anderen Stellplätze haben zwei Nachbarplätze.

Frage: Wie muß ich die Regalböden in der Höhe aufteilen, damit am wenigsten Platz verschenkt wird?

Fällt jemandem vielleicht dazu ein guter Optimierungsalgorythmus ein?
Oder eine Try&Error-Methode?
Vielleicht ist das ja auch längst mathematisch gelöst, und jemand kennt einen guten Link.

PS: Natürlich geht es nicht wirklich um Bücher, ich suche nur nach einem Lösungsansatz.

Gruß, Torsten

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Nirgends in deinem Aufgabentext wird die Höhe der Bücher oder des Regals erwähnt. Nur in der anschließenden Fragestellung kommst du auf die Höhenstaffelung der Regalböden. Und diese ist ja von den Bücherhöhen und nicht Dicken abhängig.

Die Frage sollte wohl lauten wie verteile ich die Bücher in den Ragalen - oder gibt es ein bestimmtes Verhältnis von Breite zu Höhe?

Allgemein kann man sagen das man die dicken "Bücher" wohl am liebsten am Rand platziert, da sie dann nur einen Nachbarplatz sperren.

Und die Höhenstaffelung ist doch allgemein klar ... die 8 höchsten bücher in eine Reihe, die 8 kleinsten .... usw.

Es fehlt hat das Wissen um die Kombination aus der Höhe zu der Breite.
------------------
Dirk

[Diese Nachricht wurde von Dirk Wollborn am 06. Nov. 2009 editiert.]

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Hallo Dirk,

also eigentlich erwähne ich in den ersten drei Zeilen der Beschreibung sowohl die Höhe der Bücher als auch die höhenverstellbaren Regalböden.
Die Regalseiten seien unendlich hoch, und ich habe unbegrenzt viele Regalböden zur Verfügung.
Die Forderung nach möglichst geringem Platzverbrauch hieße also, daß die Oberkante des höchsten Buches im obersten Regalfach möglichst tief liegen sollte.
Mit den dicken Büchern an den Seiten hast Du natürlich recht.
Aber würdest Du auch zwansläufig versuchen, möglichst viele der höchsten Bücher in dasselbe Regalfach zu stellen, selbst wenn genau diese Bücher auch Nebenplätze belegen? Oder muß die Priorität sein: "Dicke Bücher nach außen!"

Gruß, Torsten

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

BTW: Mir ist natürlich klar, daß es auf die Zusammensetzung der Bücher ankommt.
Aber ließen sich Regeln aufstellen, die unabhängig von Anzahl, Breite, und Höhe des Bücherhaufens gelten?

Gruß, Torsten

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Hallo Torsten,

Ohne da über Gebühr lange drüber nachgedacht zu haben glaube ich, dass das Folgende ein ganz guter Algorithmus für das Problem ist:

- Bücher der Größe nach sortieren
- Größtes unten rein , Brett drüber
- Bücher nach absteigender Größe hinzufügen
- Hinzufügen immer in das unterste Fach, in dem noch Platz ist.
- Kann ein Buch trotz Platz in einem Fach nicht hinzugefügt werden wird es im nächsten darüberliegenden Fach probiert.
- Muss dazu ein neues Fach aufgemacht werden -> Buch rein, Brett drüber
- Das ganze so lange bis alle Bücher weg sind.

Das Ganze gibt sicher nicht das globale Optimum aber wahrscheinlich ein ziemlich gutes lokales. Die Höhenverteilung der Regalböden ist am Ende optimal. Es könnte nur sein, dass man mit einem Boden weniger auskommt, wenn man anfängt die Buchbreiten differenzierter in die Optimierung einzubeziehen.

Ein nettes Problem. 'Operations Research' ist das Stichwort wenn Du nach ausgefeilteren Lösungen suchen willst.

Viel Erfolg.

Jan

------------------
Ingenieurbüro Jan Böttcher
www.ib-boettcher.de

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Also nur nach der Höhe würd ich nicht sortieren, denn dadd stell ich mir wömöglich mit nur 4 Büchern einen ganzen Regalboden voll.

Torsten da steht nur die Bücher haben eine bestimmte Höhe, das es ganz so abstrakt sein soll hatte ich nicht angenommen.
------------------
Dirk

[Diese Nachricht wurde von Dirk Wollborn am 06. Nov. 2009 editiert.]

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Zitat:

---

Also nur nach der Höhe würd ich nicht sortieren, denn dadd stell ich mir wömöglich mit nur 4 Büchern einen ganzen Regalboden voll.

---

Was ja per se erst mal nicht schlimm ist, wenn die Gesamtlösung gut ist. In diesem Zusammenhang @ Torsten: Dürfen sich 2 dicke Bücher den freien Platz zwischen ihnen teilen oder braucht jedes einzelne den Freiraum?

Aber ist schon richtig: Ob ein Lösungsalgorithmus wirklich gut ist, hängt in diesem Fall vermutlich stark von der tatsächlichen Zusammensetzung der Bücher ab. Wenn hier die Varianz groß ist und der zu erwartende Vorteil den Aufwand rechtfertigt, dann muss man wahrscheinlich wirklich die große Optimierungskeule herausholen oder den Holzhammer Try-And-Error.

Gruß

Jan

------------------
Ingenieurbüro Jan Böttcher
www.ib-boettcher.de

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Bin wieder dran.

Erstmal vielen Dank an Euch für's Mitdenken.

@Jan: Deine Lösung finde ich schonmal sehr gut. Das ist m.E. diejenige, welche man rein "gefühlsmäßig" als erstes probieren würde. Ich stimme Dir zu, daß das für eine "normale" Verteilung der Bücherhöhe und -dicke schon relativ nah am Optimum liegen sollte.
Außerdem hast Du Recht: Ich hätte sagen müssen, daß sich zwei dicke Bücher immer den Platz zwischen sich teilen können. Kein Buch ist so dick, daß nicht zwei Plätze weiter wieder ein dickes Buch stehen kann.
Ohne diese Information ist die Aufgabenstellung tatsächlich unvollständig.

Ich hatte auf der Heimfahrt über eine "simple" Iteration sämtlicher möglicher Reihenfolgen nachgedacht. Aber erstens handelt es sich im konkreten Fall um 109 "Bücher" und somit um 109! mögliche Reihenfolgen, was ja doch etwas dauern könnte, zweitens könnte ich auch dafür nicht ohne weiteres einen brauchbaren Programmablauf aus dem Ärmel schütteln.

Gruß, Torsten

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP