Problem mit der maximalen Stapelhöhe

8

Wurde das folgende Problem bereits untersucht? Wenn ja, welche Ansätze / Algorithmen wurden entwickelt, um das Problem zu lösen?

Problem ("Problem mit der maximalen Stapelhöhe")

Gegeben Polygonen, finden ihre stabile, nicht-überlappenden Anordnung , die ihre Stapelhöhe maximiert , auf einem festen Boden unter dem Einfluss der Schwerkraft.n


Beispiel

Drei Polygone:

Geben Sie hier die Bildbeschreibung ein

und drei ihrer unendlich vielen stabilen, nicht überlappenden Anordnungen mit unterschiedlichen Stapelhöhen:

Geben Sie hier die Bildbeschreibung ein


Klarstellungen

  • Alle Polygone haben eine gleichmäßige Masse und gleiche Dichte
  • Die Reibung ist Null
  • Die Schwerkraft wirkt auf jeden Punkt nach unten (dh die Kraftvektoren sind alle parallel).
  • Eine Konfiguration wird nicht als stabil angesehen, wenn sie auf einem instabilen Gleichgewichtspunkt ruht (z. B. kann das grüne Dreieck in den Bildern auf keinem seiner Scheitelpunkte ausgeglichen werden, selbst wenn die Masse links und rechts vom Gleichgewichtspunkt gleich ist).
  • Um den obigen Punkt weiter zu verdeutlichen: Ein Polygon gilt als instabil ("Umkippen"), es sei denn, es ruht auf mindestens einem Punkt genau links und mindestens einem Punkt genau rechts von seinem Schwerpunkt (diese Definition vereinfacht die Simulation erheblich und) Insbesondere ist eine Positionsintegration usw. nicht erforderlich, um zu bewerten, ob eine Anordnung stabil ist oder nicht.
  • Das Problem in seiner "physischen" Form ist ein kontinuierliches Problem, das in den meisten Fällen nur annähernd gelöst werden kann. Um ein diskretes Problem zu erhalten, das algorithmisch angegangen werden kann, beschränken Sie sowohl die Polygonscheitelpunkte als auch ihre Platzierung in der Anordnung auf geeignete Gitter.


Anmerkungen

  • Brute-Force-Ansätze jeglicher Art sind eindeutig nicht realisierbar. Selbst bei strengen Einschränkungen bei der Platzierung von Polygonen innerhalb des Gitters (z. B. Bereitstellung eines begrenzten Bereichs "Gitterraum") explodiert die Komplexität einfach für mehr als einige Polygone.
  • Iterative Algorithmen müssen einige sehr clevere Heuristiken mit sich bringen, da es einfach ist, Anordnungen zu konstruieren, bei denen das Entfernen eines einzelnen Polygons dazu führt, dass die Konfiguration instabil wird, und solche Anordnungen durch Algorithmen nicht erreichbar sind, bei denen jeder Zwischenschritt stabil ist.
  • Da das Problem in der Gesamtzahl der Eckpunkte mindestens NP-, aber wahrscheinlicher EXPTIME-vollständig riecht, wären selbst Heuristiken von erheblichem Interesse. Eine Sache, die Hoffnung gibt, ist die Tatsache, dass die meisten Menschen erkennen werden, dass die dritte Anordnung im Beispiel optimal ist.
algorithms time-complexity optimization computational-geometry heuristics
quelle
Für diese Definition von "instabil" (wenn auch möglicherweise nicht für genauere) kann man das Problem im Prinzip genau durch Quantifizierereliminierung realer geschlossener Felder lösen .
@ RickyDemer: Ich würde das wirklich gerne verstehen, aber leider sehe ich den Zusammenhang nicht, obwohl ich einen Blick über das Papier geworfen und die Hauptpunkte befolgt habe. Könnten Sie mir noch ein paar Hinweise geben? Eine Verbindung zwischen dem Stapelproblem und der Algebra klingt sicherlich faszinierend.
1
Das kann daran liegen, dass ich falsch mit einem Entscheidungsverfahren und nicht mit einem Quantifizierer-Eliminierungsalgorithmus verknüpft habe . Dieses Papier ist eine viel bessere Referenz für das, worüber ich gesprochen habe. Ich habe auch eine Arbeit über einige quadratische Fälle gefunden, die ausreichen könnten, wenn die Scheitelpunktkoordinaten alle rational sind.
:) Ich habe auch mehr Material gefunden, das die Rechengeometrie explizit mit der Quantifizierereliminierung verknüpft. Jetzt verstehe ich, was Sie mit "obwohl möglicherweise nicht für genauere" gemeint haben; In der Tat scheint es unmöglich, solche rein formalen Methoden auf die "reale" Physik auszudehnen, in der komplexe Einschränkungen wie Differentialgleichungen ins Spiel kommen. Trotzdem danke ich Ihnen für den sehr interessanten Anstellwinkel, ich werde einige Zeit damit verbringen, ihn zu studieren.

Antworten:

1

Obwohl ich keine spezifischen Algorithmen für dieses Problem kenne, können Sie dies auf eine ziemlich effiziente Weise angehen, indem Sie es in separate Teile aufteilen.

Ich würde damit beginnen, die Drehung für jede einzelne Form zu finden, die eine maximale Höhe bietet, während eine gültige Ausgleichsausrichtung beibehalten wird (ist: nicht auf einem Punkt wie beim Dreieck). Wenn eine Form mehrere gleiche Höhen hat, würde ich mit der Konfiguration gehen, die die größte Oberfläche darüber gibt. Sobald Sie dies haben, können Sie herausfinden, wie Sie jedes Objekt in einem Herrenhaus am besten stapeln können, das ausgeglichen werden kann.

GEMISIS
quelle
4
Es ist ziemlich einfach, Beispiele zu erstellen, bei denen dieser Ansatz zu einer suboptimalen Lösung führt. Stellen Sie sich zum Beispiel ein Parallelogramm vor, das durch Scheren eines sehr langen Rechtecks ​​(um es nur dann stabil zu machen, wenn es auf seiner langen Seite ruht) und eines Dreiecks erhalten wird, das seinem Scherwinkel entspricht. Individuell müssten Sie bei Ihrer Annäherung das Parallelogramm so drehen, dass es auf seiner langen Seite liegt, aber das Dreieck kann es unterstützen, damit es "aufsteht" (beachten Sie, dass das Problem der Reibung durch Hinzufügen leicht überwunden werden kann eine kleine Ecke zum Parallelogramm, in der sich das Dreieck "einhaken" kann).
Das stimmt, daran hatte ich nicht gedacht. Eine Lösung hierfür könnte darin bestehen, nach Formen zu suchen, die als Unterstützung für das Objekt verwendet werden können, die jedoch möglicherweise nicht immer eine optimale Höhe bieten. Sie können dies dennoch versuchen und anhand mehrerer Gesamtkonfigurationen die beste Höhe ermitteln, da dies immer noch besser sein sollte als eine Brute Force.
GEMISIS
Auch hier stößt man auf erhebliche Probleme, nämlich wenn nicht ein Objekt ein anderes trägt, sondern ein Stapel von Objekten mit genau der richtigen Höhe, um ein sehr großes Objekt im Stehen zu tragen. Die Algorithmen zur Überprüfung aller, die beliebig komplex werden. Abgesehen davon stimme ich zu, dass es möglich sein sollte, mit einigen vernünftigen Eliminierungen eine Laufzeit zu erzielen, die "besser als Brute Force" ist.