Box-Stacking-Problem und Varianten

Question

Du bist gegeben $n$Kisten und möchten sie stapeln, um einen möglichst hohen Turm zu erhalten. Sie können eine Kiste jedoch nur übereinander stapeln, wenn die Basis in beiden Dimensionen kleiner ist. Dies ist ein klassisches Problem der dynamischen Programmierung, und dennoch kann ich online keine einfachen Antworten auf natürliche Fragen finden:

1. Wenn die Boxen nicht gedreht werden können, wie komplex ist dieses Problem? Ein standardmäßiger dynamischer Programmieralgorithmus gibt$O(n^2)$. Kannst du tun$O(n \log n)$? Irgendwelche bedingten Untergrenzen?
2. Wenn die Boxen gedreht werden können, wie komplex ist sie dann? Beachten Sie, dass ich nicht habe$n$ Arten von Boxen und unendliche Instanzen von jedem Typ habe ich $n$ Boxen.
3. Was ist die Komplexität in höheren Dimensionen?
4. Was ist die Komplexität, wenn die Dimensionen Ganzzahlen sind? $1$ zu $k$?

Answer 1

Wenn Sie eine Box als Punkt modellieren $(b_1,b_2, \ldots, b_d)$und Sie definieren die Dominanzbeziehung $p \prec q$ $\iff$ $p_i < q_i$, für alle $i$, dann suchen Sie die längste Kette in dieser Teilreihenfolge. Im$d$ Dimensionen, in denen dieses Problem gelöst werden kann $O(n \log^{d} n)$ Mal glaube ich.

Ich würde eine etwas minderwertige Lösung skizzieren, weil es spät ist.

Betrachten Sie den zweidimensionalen Fall, um zu sehen, wie es geht. Für einen Punkt$p$, Lassen $||p||_1 = |x(p)| + |y(p)|$. Betrachten Sie die Eingabepunkte,$p_1, \ldots, p_n$und beobachte das $p_i \prec p_j$ nur wenn $||p_i||_1 < ||p_j||_1$. Sortieren Sie daher die Punkte nach ihren$L_1$ Norm, in aufsteigender Reihenfolge, und lassen $p_1,\ldots, p_i$ seien Sie die Punkte, die bisher behandelt wurden, wo für jeden $p_j$, $j=1,\ldots, i$haben wir berechnet $\ell(p_j)$ - die Länge des längsten Pfades in der Beziehung, die bei endet $p_j$. Wir fügen die zusätzliche Dimension hinzu$\ell(p_j)$ auf den Punkt $p_j$, so dass dies nun seine dritte Koordinate ist.

Nun ein neuer Punkt gegeben $p_{i+1}$müssen wir den höchsten Punkt (in der dritten Dimension) berechnen, den er dominiert (in den ersten beiden Dimensionen) - dies ist eine Frage des offenen Quadranten und kann in gelöst werden $O( \log^{O(1)} n)$Zeit unter Verwendung orthogonaler Bereichssuchtechniken. Angenommen, Sie verstehen den Punkt$p_k$ wie von der Abfrage zurückgegeben - das haben wir $\ell_{i+1} = \ell(p_{i+1}) = \ell(p_k)+1$. Wir müssen diesen neuen Punkt einfügen$(p_{i+1}, \ell_{i+1})$ im orthogonalen Bereich Suchdatenstruktur.

Somit können Sie jeden Punkt in behandeln $O(\log^{O(1)} n)$ Zeit, die leicht impliziert, dass Sie die längste Kette in berechnen können $O( n\log^{O(1)} n)$Zeit. Wenn Sie die Details genauer betrachten, kann die Laufzeit auf verbessert werden$O(n \log n)$ in zwei Dimensionen.

Ich habe hier ein Papier zu einem verwandten Problem:

https://arxiv.org/abs/1910.07586

Ich denke, eine Lösung für Ihr Problem sollte leicht durch einige frühere Arbeiten impliziert werden.

Mehr vielleicht später ...