Algorithmus zur Minimierung der Oberfläche bei gegebenem Volumen

22

Betrachten Sie die folgende algorithmische Aufgabe:

Eingabe: eine positive ganze Zahl zusammen mit ihrer Primfaktorisierung. Finden: positive ganze Zahlen , die minimieren , vorbehaltlich der Einschränkung, dassx , y , z x y + y z + x z x y z = nn
x,y,zxy+yz+xzxyz=n

Wie komplex ist dieses Problem? Gibt es einen Polynom-Zeit-Algorithmus? Ist es NP-schwer?


Grundsätzlich stellt sich das Problem: Von allen rechteckigen Körpern, deren Volumen n und deren Dimensionen alle ganze Zahlen sind, welche hat die geringste Oberfläche?

Dieses Problem wurde von Dan Meyer unter dem Titel Das Mathematikproblem, das 1.000 Mathematiklehrer nicht lösen konnten, gestellt . Bisher hat keiner der Mathematiklehrer, mit denen er zusammengearbeitet hat, einen sinnvollen Algorithmus für dieses Problem gefunden. In seinem Kontext ist die Definition von "vernünftig" etwas ungenau, aber als Informatiker können wir eine genauere Frage zur Komplexität dieses Problems stellen.

Der naheliegende Ansatz besteht darin, alle Möglichkeiten für x,y,z , dies benötigt jedoch exponentielle Zeit. Kommentatoren auf Dan Meyers Blog haben viele effiziente Kandidatenalgorithmen vorgeschlagen, die sich leider alle als falsch erwiesen haben. Martin Strauss schlägt vor, dass dieses Problem vage an 3-Partitionen erinnert , aber ich sehe keine Reduktion.


Lassen Sie mich auch einige Missverständnisse aufklären, die ich in den Kommentaren / Antworten gesehen habe:

  • Sie können die Anzahl der Partitionen von 3 nicht reduzieren, indem Sie einfach jede Zahl q durch ihre Potenz ersetzen 2q, da die Zielfunktionen der beiden Probleme unterschiedlich sind. Die offensichtliche Reduzierung funktioniert einfach nicht.

  • Es ist nicht wahr, dass die optimale Lösung darin besteht, eines von , um der nächste Teiler von zu . Ich sehe mehrere Leute, die davon ausgehen, dass dies der Fall ist, aber tatsächlich ist das nicht richtig. Dies wurde bereits im Dan Meyer-Blogpost widerlegt. Betrachten Sie zum Beispiel ; , und 4 teilt 68, so dass Sie vielleicht denken, dass mindestens eines von 4 sein sollte; das ist jedoch nicht richtig. Die optimale Lösung ist , , . Ein anderes Gegenbeispiel ist , , aber die optimale Lösung istn 3 x,y,zn n=683n3n=68x,y,zx=2y=2z=17n=22236834x,y,zx=2y=2z=17n=222x=3722236x=37 , , . (Es kann sein, dass für alle die optimale Lösung darin besteht, mindestens einen von gleich dem kleinsten Teiler von größer als oder dem größten Teiler vonz = 2y=3z=2x , y , z n 3 nx,y,znn3 n kleiner zu machen als n3 - Ich habe derzeit kein Gegenbeispiel - aber wenn Sie der Meinung sind, dass diese Aussage wahr ist, müsste sie bewiesen werden. Sie können absolut nicht davon ausgehen, dass es wahr ist.)

  • " gleich groß machen" scheint nicht in allen Fällen die optimale Antwort zu liefern; Siehe Dan Meyers Blogpost für Gegenbeispiele. Oder zumindest für einige vernünftige Interpretationen des Ausdrucks "ungefähr gleich groß machen" gibt es Gegenbeispiele, die zeigen, dass diese Strategie tatsächlich nicht optimal ist. Wenn Sie eine Strategie dieser Art ausprobieren möchten, stellen Sie sicher, dass Sie die Behauptung genau angeben, und legen Sie dann einen sorgfältigen mathematischen Beweis vor.x,y,z

  • Eine Laufzeit von ist kein Polynom. Damit dieses Problem in P auftritt, muss die Laufzeit in der Länge der Eingabe ein Polynom sein . Die Länge der Eingabe ist ungefähr lg n , nicht n . Der offensichtliche Brute-Force-Algorithmus kann in O ( n 3 ) oder O ( n 2 ) ausgeführt werden, aber das ist in lg n exponentiell und zählt daher als Exponentialzeit-Algorithmus. Das ist also nicht hilfreich.O(n3)lgnnO(n3)O(n2)lgn

DW
quelle
1
Interessant. Mein naiver Ansatz wäre "mache ungefähr gleich groß" und verallgemeinere die Idee, dass der Würfel der rechteckige Körper mit der kleinsten Oberfläche für ein bestimmtes Volumen ist. Funktioniert das? Und wenn ja: Ich verstehe nicht, wie man das effizient macht, aber gibt es eine Reduzierung, die vielleicht einfacher zu erreichen ist? x,y,z
G. Bach
2
Eine Reduktion ist ein Albtraum, da Sie eine Möglichkeit benötigen, geeignete Primzahlen zu generieren. Das Beste, auf das Sie hoffen können, ist eine zufällige Reduktion, bei der mit Dirichlets Theorem geeignete Primzahlen erzeugt werden, aber selbst das scheint unwahrscheinlich.
Tom van der Zanden
1
@ G. Bach, ich denke, dass der Blog-Artikel eine Reihe von Heuristiken dieser Ader berücksichtigt (zB beginne mit jedem von , um die nächste ganze Zahl zu 3 √ zu sein)x,y,z und passen Sie sie dann ein wenig an) und zeigt jeweils explizite Gegenbeispiele. Aber vielleicht haben Sie einen Algorithmus, den sie nicht berücksichtigt haben? n3
DW
3
oeis.org/A075777 scheint einen Algorithmus zu beanspruchen, aber er scheint inkorrekt zu sein (n = 1332 erzeugt 9,4,37 anstelle von 6,6,37 zum Beispiel)
Scott Farrar
1
Hier ist eine Bemerkung, die nützlich sein kann. Mit erfüllen die optimalen y , z tatsächlich den "naiven Traum": Sie müssen das Faktorpaar von n / x sein , das √ am nächsten kommtxy,zn/x . (Dies ist leicht zu beweisen.) Bei einer optimalen Lösungx,y,zmuss diese Bedingung für alle drei Variablen gleichzeitig gelten:x,ysind das Paar, daszentsprichtusw. Eine Implikation: gegebenzgibt es nur ein mögliches Paarx,y,mit dem es optimal sein kann. Leider (1)identifiziertdiese Bedingungdas optimale Tripelnichteindeutig; (2) Ich verstehe nicht, wie ich das entsprechende Paar schnell finden kann. n/xx,y,zx,yzzx,y
Usul

Antworten:

1

Hier ist eine modifizierte Version eines "Choose Divisor Near Cube Root" -Algorithmus. Es muss immer noch viele Fälle brutal erzwingen, daher bin ich mir nicht sicher, wie viel eine echte Verbesserung in Bezug auf die Aufzählung aller Fälle ist. Ich habe es jedoch als Korrektur für den Algorithmus in OEIS eingereicht (der falsche Ergebnisse generiert hat), da ich der Meinung bin, dass er zumindest korrekt sein sollte.

Hier ist der Algorithmus zum Finden (s1, s2, s3) und der Oberfläche eines rechteckigen Prismas bei gegebenem Volumen n:

  1. Finden Sie mit n die Kubikwurzel.
  2. Setzen Sie eine Anfangswert-Ganzzahl s1 an die Decke dieser Kubikwurzel.
  3. Testen Sie, ob s1 ein Teiler von n ist, und reduzieren Sie s1 andernfalls um 1.
  4. Wenn ein Divisor s1 gefunden wird, setzen Sie einen Anfangsbuchstaben s2 als die Obergrenze der Quadratwurzel von (n / s1).
  5. Dann testen Sie, ob s2 ein Teiler von n / s1 ist, und wenn nicht, reduzieren Sie s2 um 1.
  6. Wenn ein Divisor s2 gefunden wird, wird s3 auf n / (s1 * s2) gesetzt.
  7. Die aktuelle Oberfläche wird mit 2 * (s1 * s2 + s1 * s3 + s2 * s3) berechnet.
  8. Die aktuelle SA wird mit dem aktuellen Minimum verglichen. Wenn es die erste berechnete Oberfläche ist, wird es als minSA gespeichert. Nach dem ersten Test wird geprüft, ob die aktuelle SA kleiner als minSA ist, und in diesem Fall in minSA gespeichert.

Dieser Algorithmus zählt einige der Tripel auf (s1, s2, s3), muss aber nur die Divisoren unter der Kubikwurzel testen. (Da nicht alle drei Teiler über der Kubikwurzel liegen können). In ähnlicher Weise muss s2 nur die Teiler von n / s1 unter der Quadratwurzel von n / s1 testen, da nicht beide Teiler über der Quadratwurzel liegen dürfen.

Ein Hinweis zu Schritt 3: Wenn die Kubikwurzel ein Divisor ist, dann ist n ein Kubik und wir können dort mit minimaler Oberfläche 6 * s1 ^ 2 aus der Box (s1, s1, s1) anhalten.

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA
Scott Farrar
quelle
Ihr Algorithmus benötigt exponentielle Zeit. Jede Schleife untersucht ungefähr mögliche Kandidaten, also ist die LaufzeitO( 3 n3, die exponentiell ist, nicht Polynomzeit. Somit beantwortet dieser Algorithmus die Frage nicht. (Ich habe in der Frage bereits einen Exponential-Zeit-Algorithmus erwähnt.)O(n32)=O(n2/3)
DW
Hmm, y ist nicht unter der Kubikwurzel von n eingeschlossen, zum Beispiel n = 1332, wir werden schließlich s1 = 2 testen, was bedeutet, dass s2 unter der Quadratwurzel von 1332/2 ~ = 26 liegt. 37) wird mit y und z über der Kubikwurzel getestet.
Scott Farrar
@ ScottFarrar, ja, ich weiß. Ich habe nicht alle wichtigen Details der Komplexitätsanalyse berücksichtigt. In einem einzigen Kommentar war kein Platz. Wenn Sie die blutigen Details angeben, werden Sie wahrscheinlich feststellen, dass Sie die von mir angegebene Laufzeit erhalten. Sie können mir entweder vertrauen :-) oder unsere Referenzfrage lesen , um mehr über diese blutigen Details zu erfahren. Auf jeden Fall, auch wenn Sie die innere Schleife entfernt, hat die äußere Schleife noch Iterationen, so dass die Laufzeit des Algorithmus ist mindestens Ω ( n 1 / 3 ) - das heißt, es ist sicherlich exponentiell. Θ(n1/3)Ω(n1/3)
DW
0

Das Problem würde natürlich mit der Faktorisierung der Komplexität zusammenhängen, wenn keine Primzerlegungen angegeben würden. Angesichts der Faktoren und der Protokollierung aller Primfaktoren scheint dieses Problem in etwa so zu sein, als würde man die Abweichung von Teilungssummen vom Mittelwert minimieren (Übung, vielleicht analytisch oder experimentell, um herauszufinden, wie genau diese intuitive Annäherung an die Problem hält).k

Hier ist dies der 3-Wege-Fall (Partitionssummen sind ). Der 2-Wege - Fall wird umfangreich untersucht worden und ist schwer NP (1 st ref). (Dieser 2-Wege - Fall ist nicht ganz dasselbe wie das bekannte NP-vollständig 2-Wege - Partition Problem , wo Partition Summen gleich sind. Hinweis gleich Partition Summen impliziert 0 Abweichung in Teilungs Summen und umgekehrt. ) Die 2 nd ref Studien 3- Art und Weise und n -Wege - Partitionierung, teilweise empirisch, wo es nicht so viel Studie als 2-Wege - Fall ist.log(x),log(y),log(z)n

vzn
quelle
Diese Antwort ist nicht hilfreich und beantwortet die Frage nicht. 1. Ich suche Beweise oder Beweise, keine Spekulationen. Es gibt keine Hinweise darauf, dass die Minimierung der Abweichung eine optimale Lösung ergibt. Selbst wenn das wahr wäre, würde es die Frage nicht beantworten: Es würde uns nicht sagen, wie komplex es ist, die Abweichung zu minimieren. 2. Die erste Referenz handelt von 2 Partitionen. Es ist nicht hilfreich, mich auf einen Verweis auf 2-Partitionen zu verweisen. Ich habe bereits in der Frage erklärt, warum mein Problem nicht nur 3-Partition (oder 2-Partition) ist. Ein Artikel über eine Variante eines Problems, nach dem ich nicht gefragt habe, ist nicht hilfreich.
DW
Gegenbeispiel zur Behauptung, Sie sollten die absolute Abweichung vom Mittelwert minimieren: . Dann ergibt 1 , 4 , 17 eine absolute Abweichung von 2,85342 , was die niedrigstmögliche absolute Abweichung ist. Allerdings 2 , 2 , 17 ist die korrekte (optimal) Lösung, und hat geringere Oberfläche. [Mit absoluter Abweichung vom Mittelwert meine ich konkret | log ( x ) - μ | + | log ( y ) - μ | + |n=681,4,172.853422,2,17(wobei μ = ( log ( x ) + log ( y ) + log ( z ) ) / 3 ).]|Log(x)-μ|+|Log(y)-μ|+|Log(z)-μ|μ=(Log(x)+Log(y)+Log(z))/3
DW
okay! Es gab keine Behauptung, dass dieser Algorithmus korrekt sei. Er basierte auf der Überprüfung einiger Beispiele und anderer Vorschläge in Kommentaren. Dies ist nur ein einziges Gegenbeispiel (Sie haben angegeben, dass die Methode zur Minimierung der Abweichung im überarbeiteten Beitrag fehlerhaft ist ). Die Frage, "wie oft" dieser Algorithmus eine korrekte Lösung liefert, ist interessant, da sie Hinweise auf eine korrekte Optimierungsmetrik geben könnte. Vermutung dieser Algorithmus "oft" gibt die richtige Antwort. Der 2-Wege-Verweis soll eine Abweichungsversion des Problems
anzeigen,
siehe auch Lakatos Beweise und Widerlegungen
vzn
0

Bearbeiten

Hier ist ein informelles Argument dafür, warum es wahrscheinlich keinen schnellen Algorithmus gibt. Dieser Satz hat sich nicht geändert, aber ich habe herausgenommen, was früher hier war, weil er zu sehr wie der formale Beweis im nächsten Abschnitt aufgebaut war und die Diskussion auf ihre Fehler ablenkte, von denen ich einige selbst und einen bemerkte wovon DW mich freundlich darauf hingewiesen hat. Lassen Sie mich stattdessen versuchen, die Intuition dahinter auszudrücken.

N

Was passiert, wenn wir dieselben Schritte in eine andere Algebra übersetzen, z. B. Addition und Subtraktion statt Multiplikation und Division? Wir wissen (siehe Lemma unten), dass unser Algorithmus eine 3-Partition findet, deren Produkte gleich sind, falls eine existiert, oder dass keine solche 3-Partition existiert. Wenn wir also die gleichen Techniken in die additive Gruppe übersetzen könnten, könnten wir eine 3-Partition finden, deren Summen gleich sind, oder feststellen, dass keine solche Partition existiert. Mit anderen Worten, wir könnten 3-Partitionen in Polynomzeit lösen. Das ist nicht sehr plausibel.

Warum funktioniert ein solcher Algorithmus für die Multiplikation und kann nicht addiert werden? Ein möglicher Grund ist, dass jede Ganzzahl unter Multiplikation eine eindeutige Primfaktorisierung aufweist, unter Addition jedoch zyklisch ist. Eine andere ist, dass Multiplikation einen Ring mit Addition bildet, sodass Sie eine andere Menge von Operationen haben, die Sie verwenden können. Ein weiterer Grund ist, dass Sie den Algorithmus verallgemeinern müssen, um für Nicht-Primzahlen zu arbeiten. Dies hängt möglicherweise von deren Primalität ab. Der eine DW wies darauf hin, dass die spezifische Übersetzungsmethode die Größe Ihrer Eingaben exponentiell erhöhen könnte. Und vielleicht doch P = NP.

Aber wenn dies die Schlupflöcher sind, die einen schnellen Algorithmus funktionieren lassen, ist es meines Erachtens immer noch nützlich zu wissen, da dies vorschlägt, wo wir unsere Anstrengungen konzentrieren sollten. Wir sollten nach etwas suchen, das kaputt geht, wenn wir versuchen, es auf ein NP-vollständiges Problem anzuwenden. Ein Ansatz, der sich auf andere Algebren verallgemeinern würde, ist wahrscheinlich, den falschen Baum zu bellen. Ich vermute jedoch, dass die Multiplikation nicht wirklich unterschiedlich genug ist, um zu funktionieren, aber das ist nur eine Vermutung.

Lemma

m=N3(einm,bm,meinb)einb(ab+1a+1b)m2 and is minimized when a=b=1.

Proof: We see immediately from the restriction xyz=N that any arbitrary solution has this form.

Its weight is (am)(bm)+(am)(mab)+(bm)(mab)=abm2+m2b+m2a=(ab+1a+1b)m2.

Let f(a,b)=ab+1a+1b. To minimize this function, we take the partial derivatives δfδa=b1a2 and δfδb=a1b2. The critical point where these partial derivatives are zero comes where a=b2,b=a2, and therefore, since a and b must be real numbers greater than 0, a=b=1. We see from the matrix of second-order partial derivatives that this is a global minimum.

My immediate motivation to prove this was to fill in a hand wave in my proof above that, if a perfect-cube solution exists, it is optimal. However, this formula could be useful for pruning the search tree.

Assorted Thoughts

I don’t see any obvious symmetry except the interchangeability of x, y and z, which only gives us at best a constant factor of 6. We do have some speedups for the 2-partition that basically say we’d want both terms to be as close to each other as possible, but I don’t immediately see an application to this problem.

Off the top of my head, simply taking the log of all the numbers immediately reduces this to a classic 3-partition problem using addition, or equivalently, taking some number to the power of the numbers in any 3-partition addition problem turns it into a multiplication problem such as this. That implies this problem should not be any easier. We do have here the prime factorization, whereas that factorization would not be prime, but does that help us?

Graphically, the surface xyz = 0 would look like the union of the xy-, yz- and xz-planes, and for any positive n, the equation would look like y = n/xz, so each slice along a coordinate plane would be a hyperbola. We can generally say that the quantity we’re trying to minimize is lowest at the origin and grows most rapidly along the line where x = y = z. If we can search only along this manifold, we might be able to reduce to a two-dimensional problem.

Davislor
quelle
If x+y+z=n, 2^n=2^(x+y+z)=2^x*2^y*2^z, which is an instance of this problem minus the restriction that the inputs are a prime decomposition of the product. They would instead all be powers of two.
Davislor
Es ist wahr, dass das zu minimierende Gewicht unterschiedlich sein wird, aber wenn x = y = z im ursprünglichen Problem ist, wird x'y '+ x'z' + y'z 'im entsprechenden Problem, in dem jedes w ist, nicht minimiert ersetzt durch w '= 2 ^ w, was bedeutet, dass wenn eine Lösung für das ursprüngliche Problem existiert, die Reduktion es finden würde? Wir erhalten möglicherweise eine falsche Lösung für das transformierte Problem, aber wir können dies in linearer Zeit beim Zurückkonvertieren feststellen, indem wir die Summen überprüfen.
Davislor
as above comment by GBach suggests, maximizing xy+yz+xz subject to xyz=n likely happens when x,y,z are "close together" or have low deviation (from average). this is not necessarily the same as "close to n3". the numerical examples given by Meyer on his page appear to fit this pattern.
VZN
@vzn: We’re trying to minimize surface area, not maximize it. If the 3-partition problem has a solution, that translates into a modified box-dimension problem where the solution is a perfect cube. A hypothetical poly-time algorithm would find the factors of the sides of that cube, and we could then translate it back into the original domain, while checking for spurious solutions, in linear time. That suggests an algorithm for a slightly-relaxed problem could serve as an oracle for a hard problem, making it unlikely a better-than-exponential algorithm exists.
Davislor
? am not disagreeing with you. arent we saying the same thing? plz drop by Computer Science Chat to untangle/ sort this out further. also cant follow @D.W.s claim that the logarithmic transformation doesnt work, can you? am using some of your (seemingly on-target) analysis as basis for my own answer.
vzn