Mengenbeschränkungen vereinfachen
-
Hi, ich habe folgendes Problem und komme schon seit geraumer Zeit auf keine vernünftige Lösung. Ich habe eine Menge von Tupeln:
\{(a,b) \ | \ a\in[7-x,8-x] \ \wedge \ b\in[7-x-y,9-x-y]
\ \ \ \ \wedge \ x\in [7-y,8-y] \ \wedge \ y\in [3,5] \}Jetzt würde ich gerne irgendwie das y komplett los werden. Dafür kann der Ausdruck gerne auch komplexer werden. Die auftauchenden Zahlen (3,5,7,8) sind zufällig und könnten auch komplett anders aussehen.
Vielleicht hat jemand von euch eine Idee wie man dieselbe Menge ohne y darstellen könnte?Gruß, Dirk
-
aus
y\epsilon[3,5] und x\epsilon[7-y,8-y]lässt sich leicht
x\epsilon[7-3,8-3] = [4,5] und x\epsilon[7-5,8-5] = [2,3]machen womit sich dann
x\epsilon[2,5]
ergibt.Wenn ich mich nicht täusche
-
Das war auch mein erster Gedanke, leider ist es aber wohl nicht so einfach.
Das Problem ist, dass y noch in dem Term b\in[7-x-y,9-x-y] gebunden vorkommt. Bei folgenden Beispiel wird das vielleicht deutlicher:\{ (a,b)\ | \ a\in [10-x,12-x] \wedge b\in [5-x,9-x] \wedge x\in [0,4] \}
Würde man x jetzt einfach auflösen würde man folgendes erhalten:
\{ (a,b)\ | \ a\in [6,12] \wedge b\in [1,9] \}
Dann wäre das Paar (a=6,b=9) in der Menge. Das ist aber nicht in der ursprünglichen Menge, weil dann x gleichzeitig 4 und 0 sein müsste.
-
ich hätte gerne ein bildchen, was die menge auf der ebene zeigt.
-
Mal Dir doch ein 4D-Bildchen mit (a,b,x,y). Das gesucht Bild ist dann die Projektion auf die ersten beiden Koordinaten. :p
-
Das Bild für die zweite Menge ist ein geschlossenes Polygon, dass entstehen würde, wenn man ein Rechteck an einer Geraden verschieben würde.
Hier mal schematisch:http://img144.imageshack.us/img144/3738/bildsb9.png
-
Eine einfachere Beschreibung kann ich Dir jetzt nicht einfach so bieten. Aber schau Dir mal lineare Optimierung/Programmierung an. Wenn Du Deine Invervalle mal als >= untere Schranke und <= obere Schranke ausschreibst kommst Du recht schnell auf die Standardform (ohne Optimierung halt). Dann kannst Du zumindest die Ecken ausrechnen.
MfG Jester
-
ich hab 6 kanten und jede macht eine bedingung.
(hab die zahklen nicht berechnet, sondern geraten)
unten: b>=2
rechtsunten: b=>a-5
rechts: a<=10
oben: b<=10
linksoben: b<=a+5
links: a>=2
damit haste schonmal die sachen ganz ohne x und y. vielleicht noch grenzen zu intervallen zusammenfassen.
a€[2,10]
und
b€[2,10]
und
b=>a-5
und
b<=a+5
die ersten beiden bedingungen erlauben das große schwarze rechteck und die beiden letzten schnippeln jeweils eine ecke ab.
-
Wie gesagt, allgemein machen kann man's mit Basismatrizen und dann damit die Eckpunkte berechnen. Wenn man die hat muß man sie nur noch im Urzeigersinn anordnen und kann dann die begrenzenden Geraden hinschreiben. Das dürfte algorithmisch sogar noch ganz gut gehen, wenn es auch nicht sonderlich effizient ist.
-
Danke für die Antworten! Ich denke, die Implementierung sollte ich jetzt hinbekommen. Lineare Programmierung brauche ich sowieso auch noch für einen anderen Teil.
Gruß, Dirk
