Cover Problem

FierceOne

Kampfmaschine
Hallo!

Ich habe mal eine Frage an die Informatiker unter Euch bzw. alle Leute mit ausreichend Phantasie. Ich habe hier gerade folgendes Problem:
Gegeben:
- eine beliebige, stetige Funktion die ueberall >= 0 ist.
- eine Natuerliche Zahl N, typischerweise nicht groesser als 10

Gesucht:
- N Rechtecke, deren Gesamtflaeche maximal ist

Bedingungen:
- sie muessen disjunkt sein (nicht ueberlappend)
- jeweils komplett unterhalb der Funktion liegen
- die jeweiligen Kanten muessen parallel zu x und y-Achse sein (vereinfacht die Sache)

Momentan befinde ich mich noch in der Lesephase, d.h. ich schaue was andere bzgl. dessen schon gemacht haben um das Rad nicht neu erfinden zu muessen. Vermutlich (hoffentlich) wird die Loesung am Ende ein Optimierungsproblem der ein oder anderen Art sein. Soweit haenge ich gerade in der Packtheorie. Problem hier ist dass die Rechtecke vorgegeben sind und dann irgendwie flaechenfuellend eingepasst werden muessen. Ich hingegen will die Rechtecke ausrechnen. Dennoch vermute ich einen zielfuehrende Ansatz irgendwo in dem Dunstkreis. Hat da jemand Ideen?!

DANKE
 
Zuletzt bearbeitet:
Wie sollen die Rechtecke denn auf der Kurve (der Funktion) liegen? Komplett unterhalb der Kurve oder darf dies auch geschnitten werden (Stichworte Unter- bzw. Obersumme).

Hilfreich in einem ersten Ansatz ist sicher das Riemannsche Integral.

mousaka
 
Wie sollen die Rechtecke denn auf der Kurve (der Funktion) liegen? Komplett unterhalb der Kurve oder darf dies auch geschnitten werden (Stichworte Unter- bzw. Obersumme).

Hilfreich in einem ersten Ansatz ist sicher das Riemannsche Integral.

mousaka

Auf jeden Fall komplett drunter. Ja, bei Integralen stellt man ja quasi einfach unendliche viele nebeneinander. Ich denke bei nur 2 oder 3 Rechtecken wird man wohl nicht umhinkommen die Teile auch uebereinander zu stapeln.
 
Hallo,
wenn die Rechtecke vorgegeben sind, wird die Sache einfacher,
mittels Backtracking über die Rechtecke. Denn die Anzahl ist ja begrenzt,
du hast nur genau N Stücke.
Wenn du jetzt anfängst über Rechtecke zu gehen, hast du N Rechtecke, die
aber viele verschiedene Breiten und damit Größen annehmen können.

Zu deinem Problem: Vielleicht kannst du da was mit Extremasuche machen
und dementsprechend "große" Rechtecke ans Maximum anpassen und eher
keine Rechtecke ans Minimum.

Wie du dafür ohne probieren eine Lösung finden und wie du das genau
mathematisch darstellen kannst weiß ich allerdings auch nicht.
 
Extremasuche klingt soweit gut und man kommt damit glaube auch gut auf Ergebnisse. (Ich habs mal schnell gehackt um mir ein besseres Bild machen zu koennen). Das Problem ist, dass ich eine formellere Loesung brauche. Wie gesagt, am besten als Optimierungsproblem. Viele aehnliche Probleme lassen sich ja als Optimierungsproblem hinschreiben. Das ist bei mir notwendig, weil dies nur ein Unterproblem ist, also gar nicht Kern der Sache.
Naja, auf die schnelle habe ich das Problem leicht abgewandelt und scheinbar eine brauchbare Loesung gefunden. Wenn man die Moeglichkeit auslaesst die Rechtecke zu stapeln, sondern nur nebeneinander zu arrangieren, wird es wesentlich einfacher. Das habe ich jetzt als beschraenktes Optimierungsproblem eingepasst.
In der Post befindet sich "Approximation Algorithms" von Vazirani. Das werde ich mal in Ruhe studieren und mir solange mit meinem Provisorium helfen.

Danke fuer die Antworten.
 
Das größte Rechteck unter einer stetigen Kurve zu suchen ist ja
nicht so schwer:
max (A)
wobei A = f(a) * x_delta und f(a+x_delta) <= f(a)

Jetzt müsste man ja nur den Definitionsbereich der Funktion in Teilbereich
derart unterteilen, dass die Summe der Flächen der Rechtecke maximal
wird und es gilt x1,1 < x1,2 <=x2,1 < x2,2<=... <xn,2

Dies könnte man wohl auch (zwar etwas ungenauer) iterativ machen:
Erst das größte Recheckt suchen und dann je nach Funktionswert und
Minimum und Maximum entweder Links oder rechts vom Rechteck wieder
das größte noch mögliche Rechteck einpassen,...

Würde mich auf jedenfall interessieren, wie du das dann entgültig gelöst hast.
 
Genau, wie ich schon sagte, ohne Stapelei wirds einfach. Aehnlich wie Du das beschreibst habe ich es jetzt auch erstmal eingetippt. Das funktioniert auch ganz gut, mal abgesehen davon dass das Problem nicht convex ist. Aber ok, damit muss ich wohl leben.
Wie gesagt, ich kuemmere mich jetzt um ein paar andere Sachen in dem Zusammenhang. Sobald ich bzgl. dieses Teilproblems ein wenig gelesen habe oder sonst wie inspiriert bin mache ich an dieser Stelle wieder Meldung.
 
In welcher Form soll die Lösung denn formuliert sein?
- ein Stück Prosa
- eine Formel in mathematischen Ausdrücken
- eine Programmiersprache
- ...
 
In welcher Form soll die Lösung denn formuliert sein?
- ein Stück Prosa
- eine Formel in mathematischen Ausdrücken
- eine Programmiersprache
- ...

Idealerweise als Optimierungsproblem, geeignet fuer gradientenbasierte Verfahren. Auf gar keinen Fall eine Programmiersprache, das mache ich dann selber. Eine _genaue_ Beschreibung des Loesungsalgorithmus in Form von Prosa waere auch super.
Der absolute Burner waeren 1,2 Schlagworte mit denen ich in der Fachliteratur fuendig werde bzw. entsprechende Verweise. Ich bin nahezu 100% sicher das sich irgendwann mal irgendjemand ueber ein derartiges Problem Gedanken gemacht hat. Vielleicht gibt es auch ein paar klevere Gedanken die mir momentan fehlen um dieses Problem in ein Anderes zu ueberfuehren, fuer welches konkrete Loesungsansaetze vorhanden sind.
 
Zurück
Oben