spitzwegerich
Senior Dabei seit: 13.06.2005 Mitteilungen: 1327
Beitrag No.1, eingetragen 2008-03-21
Magma
A := Matrix(Integers(),4,4,[
32428,-39179,40876,14163,
1753,13135,40190,57864,
-32968,9937,-31399,47004,
10517,56634,52793,-8562
]);
L := Lattice(A);
ClosestVectors(L,Vector(Integers(),[100000,100000,100000,100000]));
liefert die Ausgabe
[
(101138 101787 99669 99990)
]
4598074
Wenn ich mich also nicht vertippt habe und die Algorithmen in Magma korrekt arbeiten, so ist der gesuchte Vektor
v = (101138;101787;99669;99990).
Es gilt: v - w = (1138 ; 1787 ; -331 ; -10) und damit norm(v-w) = sqrt( 1138^2 + 1787^2 + 331^2 + 10^2 ) = sqrt(4598074) was mit der Magma\-Ausgabe übereinstimmt.
Rechnet man noch etwas weiter, so kriegt man noch den Koordinatenvektor (z_1 ;z_2 ;z_3 ;z_4) = ( 189760;-204791;220450;140093) raus.
[ Nachricht wurde editiert von spitzwegerich am 21.03.2008 12:54:01 ]
[ Nachricht wurde editiert von spitzwegerich am 22.03.2008 14:47:35 ]
[ Nachricht wurde editiert von spitzwegerich am 26.03.2008 00:42:18 ]
Also ich wäre da folgendermaßen an die Aufgabe herangegangen:
Man ignoriere ersteinmal die Ganzheitsbedingung von z1 bis z4, und berechne die Linearkombinations-Koeffizienten exakt. Dann kennt man genau die Koordinaten des Punktes w im von den Vektoren b1 bis b4 aufgespannten "schiefwinkligen Koordinatensystem" (bzw. dem von diesen Vektoren erzeugten Gitter).
Durch alle Kombinationen von Auf- und Abrunden der 4 z-Koordinaten erhält man die 16 Eckpunkte der "Gitter-Zelle", in welcher der Punkt w liegt. Einer davon ist dann der gesuchte. (Wenn ich es mir recht überlege, dürfte dies dann die "normale" Rundung sein.)
Beitrag No.5, vom Themenstarter, eingetragen 2008-03-22
2008-03-22 13:51 - cyrix schreibt:
Durch alle Kombinationen von Auf- und Abrunden der 4 z-Koordinaten erhält man die 16 Eckpunkte der "Gitter-Zelle", in welcher der Punkt w liegt. Einer davon ist dann der gesuchte.
Eine interessante Idee. Funktioniert sie denn auch?
spitzwegerich
Senior Dabei seit: 13.06.2005 Mitteilungen: 1327
Beitrag No.6, eingetragen 2008-03-22
2008-03-22 12:31 - akz1on schreibt:
Die Antwort ist irgendwie nicht ganz richtig. =) bzw. die 2te Komponente von z stimmt nicht und führt beim nachrechnen zu Fehlern.
Ich habe nochmal nachgerechnet und kann keinen Fehler erkennen.
Wo ist denn das Problem?
aceman
Aktiv Dabei seit: 10.10.2002 Mitteilungen: 31
Beitrag No.7, eingetragen 2008-03-22
2008-03-22 13:57 - Kay_S schreibt:
Eine interessante Idee. Funktioniert sie denn auch? :-)
\ Das tut sie offenbar i.A. nicht: Wären z.B. b1=(30;0) und b2=(10;2), so liegt etwa w=(20;1) in der durch die Punkte (0,0), (30,0), (40,2) und (10,2) begrenzten Zelle; näher ist aber der Gitterpunkt (20,4), d.h. mit z1=0 und z2=2.
Vielleicht lässt sich die (Hyper-)Kugel, welche im Bildraum alle Punkte mit gleichem Abstand von der exakten Lösung beschreibt zurück-abbilden auf eine andere Form (Hyperellipsoid eventuell? Über die Eigenvektoren/-werte der Umkehrabbildung vielleicht?) mit der sich die Aufgabe dann systematisch lösen lässt.
spitzwegerich
Senior Dabei seit: 13.06.2005 Mitteilungen: 1327
Beitrag No.8, eingetragen 2008-03-22
2008-03-22 13:57 - Kay_S schreibt:
2008-03-22 13:51 - cyrix schreibt:
Durch alle Kombinationen von Auf- und Abrunden der 4 z-Koordinaten erhält man die 16 Eckpunkte der "Gitter-Zelle", in welcher der Punkt w liegt. Einer davon ist dann der gesuchte.
Eine interessante Idee. Funktioniert sie denn auch? :-)
Ueli
Senior Dabei seit: 29.11.2003 Mitteilungen: 1484
Herkunft: Schweiz
Beitrag No.9, eingetragen 2008-03-25
Hallo zusammen,
Ich habe auch mal die "exakte" Lösung genommen und auf alle Möglichkeiten gerundet:
Der Abstand vom Vektor
Z=(186390, -201154, 216535, 137605)
liefert das kleinste Resultat: a=5646.
Ist dies sicher die beste Lösung?
Nein, meiner Meinung nach müsste man noch Lösungen ausserhalb des Parallelepipeds suchen, in dem sich der Punkt (1,1,1,1) befindet.
Das wollte ich dem Taschenrechner und meinem Tipfinger aber nicht mehr zumuten.
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.10, eingetragen 2008-03-25
Hier nochmal eine Skizze um die Bemerkungen, die darauf hinwiesen, daß der optimale Gitterpunkt nicht in derselben Gitterzelle liegen muß, zu verdeutlichen. Im Prinzip ist es kein Problem, eine Aufgabe zu konstruieren, in der der optimale Gitterpunkt beliebig viele Gitterzellen entfernt ist. Und ich traue den Aufgabenstellern jede Gemeinheit zu!
[ Nachricht wurde editiert von Realshaggy am 25.03.2008 15:28:51 ]
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.12, eingetragen 2008-03-25
Nehmen wir mal an, die von spitzwegerich gefundene Lösung stimmt, dann finde ich unseren Lösungsweg irgendwie sehr unbefriedigend. Geht das nur mir so?
Ueli
Senior Dabei seit: 29.11.2003 Mitteilungen: 1484
Herkunft: Schweiz
Beitrag No.17, eingetragen 2008-03-26
Die Boshaftigkeit der Autoren kann man testen, indem man den Zielvektor etwas variert. Z.b. (100100, 100000, 100000, 100000).
Löst man nun die Gleichung exakt, dann sieht man dass Realshaggy richtig vermutet hat. Eine kleine Änderung am Zielvektor erzeugt eine grosse Abweichung in z.
Etwa so wie mit dem Flügelschlag des Schmetterlings und dem Wirbelsturm.
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.18, eingetragen 2008-03-26
Naja dieses Bild ist vielleicht etwas überdramatisiert, schließlich geht es nur um die Lösung eines linearen Gleichungssystems im IR^4. So fies ist das Beispiel nun auch wieder nicht gewählt, die Winkel zwischen den Basisvektoren liegen allesamt zwischen 65 und 120 Grad.
Ueli
Senior Dabei seit: 29.11.2003 Mitteilungen: 1484
Herkunft: Schweiz
Beitrag No.19, eingetragen 2008-03-26
Na ja, mein Taschenrechner-Tipfinger schmerzt aber immer noch.
Um das Problem zu lösen könnte man ja auch die Ausgangslage verbessern. An Stelle des grossen schiefen Parallelepipeds ein kleines handliches, etwa rechtwinkliges machen und mit diesen neuen Basisvektoren das Gleichungssystem lösen.
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.20, eingetragen 2008-03-26
Hm, die Idee verstehe ich nicht. Wenn du das ganze Problem auf eine neue Basis transformierst, hat doch w' in der neuen Basis dieselben Koordinaten wie w in der alten? In der Standardbasis stimmt es dann zwar, daß man von der Lösung des kontinuierlichen Problems einfach zur nächstliegenden Ecke im selben Quader gehen kann, um das diskrete Problem zu lösen, aber wenn du das ganze dann zurücktransformierst bleiben ja wieder die Koordinaten, das heißt du landest im selben "Eckpunkt", und das ist ja genau der falsche.
Edit: Irgendwie so könnte es aber gehen. Wenn ich nochmal das Bild von oben poste:
Ich will in dem Bild nur die Basisvektoren transformieren, und nicht den Punkt um den es dann geht. Das ganze mache ich derart, daß ich den waagerechten Basisvektor so belasse, und den "schrägen" so ändere, das er senkrecht mit derselben Orientierung wie bisher auf dem anderen steht, aber noch dieselbe Länge hat. Wenn ich dann das stetige Problem löse, und zur nächstliegenden Ecke gehe, ist das die "richtige".
Aber wie ich das ganze mit beliebigen Basisvektoren im IR^4 anstelle, davon habe ich keine Ahnung. Es muß auf jeden Fall eine Transformation auf eine Orthogonalbasis eine Rolle spielen, deren Vektoren dieselbe Länge haben wie die der Ausgangsbasis, und in der der Vektor (100000,100000,100000,100000) eine Koordinatendarstellung hat, die sich auf unsere gefundene Lösung rundet. Das ganze muß dann aber auch noch irgendwie gehen, ohne daß man vorher die Lösung schon kennt.
[ Nachricht wurde editiert von Realshaggy am 26.03.2008 11:31:34 ]
spitzwegerich
Senior Dabei seit: 13.06.2005 Mitteilungen: 1327
Beitrag No.21, eingetragen 2008-03-26
Das klingt im Wesentlichen nach dem LLL-Algorithmus. Er findet Gitterbasen aus "kurzen" Vektoren und dürfte wohl auch im Inneren des oben benutzten Magma-Algorithmus ablaufen.
Der in Magma implementierte LLL-Algorithmus liefert
Die Gitterbasisvektoren sind immer noch nicht sonderlich kurz. In Anbetracht des Ergebnisses war aber von vornherein klar, dass sie das auch nicht werden können.
[ Nachricht wurde editiert von spitzwegerich am 26.03.2008 11:59:09 ]
[ Nachricht wurde editiert von spitzwegerich am 28.03.2008 12:44:38 ]
Delastelle
Senior Dabei seit: 17.11.2006 Mitteilungen: 1626
Beitrag No.22, eingetragen 2008-03-27
Hallo Leute!
Ich habe zu der Aufgabe auch einiges gerechnet.
Dabei kam ich auch auf das Ergebnis von spitzwegerich.
Mein Algorithmus (eine Heuristik)
(a) x_0 = (0,0,0,0) oder
(b) x_0 = (186390, -201154, 216535, 137605) // nichtganzzahlige Lösung des Problems
Plankalkül :-)
x_opt = x_0
for i = 1,1000000
x = x_opt + 4x Zufallszahl aus [-5000,5000] für alle 4 Komponenten des Vektors
lokale Suche mit Nachbarschaft -1,+1 für alle 4 Komponenten des Vektors
aktualisiere x_opt falls besseres Optimum gefunden
end for
Der Startwert (a) konvergiert häufig gegen eine Lösung 2469,... (siehe unten) ,
der Startwert (b) konvergiert meist gegen 2144,... (siehe unten).
Was im Verhältnis zu anderen Problemen der diskreten Optimierung auffällt, ist der Zugewinn an Information nach einer gewissen Rechenzeit. (Bei allgemeinen Problemen der diskreten Optimierung ist die ungefähre Lage des Lösungsvektors völlig unklar.)
Weiterhin ist mir aufgefallen, dass Lösungen mit gutem Zielfunktionswert ein bestimmtes Verhältnis in x besitzen und zwar 1.000 : -1.079 : 1.162 : 0.738
\ Bsp: ff \-> Zielfunktionswert Prod \-> Vektor, der mit 100000 verglichen wird x \-> Lösung x(relativ) \-> Verhältnis der Komponenten von x
Auf einen Nachteil dieses Heuristischen Ansatzes möchte ich noch hinweisen: bei dieser Aufgabe weiß man nie, ob man das Optimum gefunden hat - man sieht nur, dass der Zielfunktionswert nicht mehr fällt.
Ueli
Senior Dabei seit: 29.11.2003 Mitteilungen: 1484
Herkunft: Schweiz
Beitrag No.23, eingetragen 2008-03-28
Hat schon jemand versucht die vier Vektoren einzeln oder einige miteinander zu ersetzen durch diagonale Vektoren im Parallelepiped?
Dann könnte man die rationale Lösung finden und runden (wie cyrix es anfangs vorgeschlagen hat).
Das 2-d Beispiel von Realshaggy kann man auch so lösen.
Man hat dann zwar einige, aber eine genaue Zahl von Kombinationsmöglichkeiten, welche man abklappern muss.
spitzwegerich
Senior Dabei seit: 13.06.2005 Mitteilungen: 1327
Beitrag No.24, eingetragen 2008-03-28
2008-03-28 08:22 - Ueli schreibt:
Hat schon jemand versucht die vier Vektoren einzeln oder einige miteinander zu ersetzen durch diagonale Vektoren im Parallelepiped?
Delastelle
Senior Dabei seit: 17.11.2006 Mitteilungen: 1626
Beitrag No.26, eingetragen 2008-03-28
Mittlerweile kann ich mit lokaler Suche bei Startwert x = (0,0,0,0) die Lösung 2144,... in weniger als 1 Sekunde finden.
Fortran
for j =1:4
minx(j)=0end for
minfehler =1000000
for i =1:1000000if(minfehler > 100000)
for j =1:4
x(j)= minx(j)+ Zufallszahl aus [-7500,7500]end for
else
x(1)= minx(1)+ Zufallszahl aus [-7500,7500]
x(2)=floor(fak(2)*x(1))
x(3)=floor(fak(3)*x(1))
x(4)=floor(fak(4)*x(4))endif
lokale Suche mit Nachbarschaft +/-1 für alle 4 Komponenten des Vektors x
aktualisiere minx, minfehler falls neues Optimum gefunden
end for
*****
fak(i):= x(i)/ x(1) falls abs(x(1)) > 0
fak(i):=1 falls x(1)=0
Falls der beste Funktionswert schlechter als 100000 ist (zu Beginn der Optimierung; die Grenze 100000 ist willkürlich gewählt) werden 4 Zufallszahlen gebildet und zu x addiert.
Falls der beste Funktionswert besser/gleich 100000 ist, wird die 1.Komponente von x zufällig gewählt und die Komponenten 2 bis 4 so ermittelt, dass das Verhältnis in x wie in der besten gefundenen Lösung (minx) ist.
[ Nachricht wurde editiert von Delastelle am 29.03.2008 16:22:43 ]
Beitrag No.27, vom Themenstarter, eingetragen 2008-03-29
Lösung
Die Spalten der Matrix A=(32428,1753,-32968,10517;-39179,13135,9937,56634;40876,40190,-31399,52793;14163,57864,47004,-8562) sind eine Basis des Gitters. Sie ist sehr schlecht konditioniert, der Wert abs(\det(A))/(norm(a_1)*norm(a_2)*norm(a_3)*norm(a_4)) beträgt 0.00000500. Der Übergang zu einer anderen Basis mit einer unimodularen Transformation (ganzzahlig und Determinante \pm 1) ändert nichts am Problem, eine geeignete unimodulare Transformation findet man, indem man elementare Spaltentransformationen ausführt, die die Kondition verbessern. Nach einigen Schritten kommt man zu der Darstellung A=N*T mit N=(-494,436,3321,-12;3661,599,-181,557;246,3101,-7,351;-573,-132,333,3282) und T=(-13,-1,2,13;14,11,-12,16;6,-1,-8,3;2,18,15,0), wobei die Matrix N die Kondition 0.93 hat. Nun soll man einen ganzzahligen Vektor g finden, sodass die Länge von N g - w mit w=(100000;100000;100000;100000) möglichst klein wird. Lässt man die Ganzzahligkeit unbeachtet, dann erhält man den Lösungsvektor (19.47;27.15;29.56;31.96). Durch geeignetes Runden der Einträge erhält man unter Verwendung der reduzierten Basismatrix Gitterpunkte, die in der Nähe von w liegen. Als besten Vektor erhält man g=(20;27;30;32) mit dem Abstand norm(N g-w)=sqrt(4598074), schließlich erhält man mit Hilfe der inversen Transformationsmatrix T^(-1)=(921,-1830,5769,1490;-994,1975,-6226,-1608;1070,-2126,6702,1731;680,-1351,4259,1100) den Lösungsvektor z=T^(-1) (20;27;30;32)=(189760;-204791;220450;140093) für die ursprüngliche Aufgabe, der gesuchte Gitterpunkt lautet (101138;101787;99669;99990).
Anmerkung: Es gibt keine Garantie dafür, dass die obige Rundungsmethode den nächsten Gitterpunkt liefert. Das Problem, den nächsten Gitterpunkt zu bestimmen, wurde 1981 von van Emde Boas als NP\-vollständig nachgewiesen.
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2008-03-19
Notiz
Profil
Quote
Link
