Monotonie in Knuth Optimierung

Question

Ich bin in der Mitte des Lernens, was ist Knuth Optimierung.

Die relevanten Informationen können im Wesentlichen durch here

zugegriffen werden, da zwei Annahme in Knuth Optimierung ist.

One ist Quadrangle Inequality und das andere ist Monotonie

Ich kann total verstehen, was ist Quadrangle Inequality. Allerdings gibt es keine Beispiele, die über Monotonici erklären, ich kann es nicht bekommen.

Monotonie: C [b] [c] < C [a] [d] (a, b, c, d)

Soviel ich weiß, die Monotonie ist ein etwas lineares Merkmal und wenn zwei verschiedene Elemente (b, c) zwischen den Elementen (a, d) außerhalb von ihnen sind, sind die Kosten im Bereich b bis c kleiner als die Kosten im Bereich a bis d.

Warum ist das nicht möglich in Chained Matrix Problem?

Angenommen, es eine Reihe von Matrix {x1, x2, ..., xn}

Offensichtlich sind die Kosten der Multiplikation im Bereich b zu c kleiner ist als die Kosten für die Multiplikation im Bereich A bis D Denn es gibt mehr Elemente im Bereich von a bis d als von b bis c.

Kann jemand das erklären?

Answer 1

Relative Monotonie kann auch in höheren Dimensionen auftreten. Stellen Sie sich eine 2D-Ebene vor, in der Sie den Converter rechts unten halten und ihn so anheben, dass wir A[i-1][j] <= A[i][j] <= A[i][j+1] erhalten.

Wenn solche Monotonie gilt dann sagen wir, dass der Problemraum mit Knut Optinimzaton optimiert werden kann. dh F[i][j] = min{F[i][k]+F[k+1][j]}+C[i][j] for k=i to j-1, dann kann es optimiert werden, indem nur from k=P[i-1][j] to P[i][j+1] ist der Punkt, wo A[i][j] Minimum ist.

ursprüngliches Problem benötigen O (n^3), während aufgrund der oben Monotonie nun in O gelöst werden kann (n^2)

(Anmerkung: Hier gibt es keine absolute Monotonie zwischen irgendwelchen zwei Elementen, das ist warum ich es als relative Monotonie bezeichnet habe, wenn zwei Elemente so sind, dass eines südöstlich von einem anderen ist, dann ist das südöstliche Element größer als oder gleich dem anderen, eine solche Beziehung ist gut genug für Knuth Optimization)