Hallo und Programmieraufgabe

Moderator: Optimierungsalgorithmen

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

Hallo allerseits,

zunächst einmal möchte ich Sie auch hier im Forum noch einmal herzlich begrüßen!

Zur Programmieraufgabe, die ich heute in der Vorlesung kurz vorgestellt hatte:

-> Sie können mit den nichtalgorithmischen Anteilen - also der Visualisierung und dem Zufallsgenerator - natürlich sofort loslegen. Fragen dazu stellen Sie am Besten im Forum hier, dann kann jeder Ihre Frage und meine Antwort darauf lesen.

-> Sobald einer der zu implementierenden Algorithmen in der Vorlesung behandelt wurde, haben Sie alles notwendige Wissen, um ihn zu implementieren.

Wichtig ist, dass Sie die Algorithmen nicht zurechtgeschnitten auf die algorithmische Problemstellung "Rechtecke packen" implementieren, sondern so generisch wie in der Vorlesung, so dass die konkrete algorithmische Problemstellung in Ihrer Implementation des Algorithmus jederzeit austauschbar ist. Wie in der Vorlesung gesagt, sind meines Erachtens bspw. Interfaces in Java eine sehr gute Möglichkeit dafür, Generics eher weniger. Die passende Abstraktion ist das Framework gemäß http://de.wikipedia.org/wiki/Framework, ideal wäre ein Black-Box-Framework.

KW

kaisler
Neuling
Neuling
Beiträge: 2
Registriert: 24. Okt 2012 21:20

Re: Hallo und Programmieraufgabe

Beitrag von kaisler »

Hallo Professor Weihe,

wird es einen Übungsblatt geben und wo kann man das Skript herunterladen?

Zu Programmieraufgabe:
Soll es eine 2D oder 3D Anwendung werden?

Zu Algorithmus:
Die Aufgabe des Algorithmuses soll ja sein, dass er beliebige Objekte so dicht zusammenpacken
soll, damit sich die kleinst mögliche Bounding-Box ergibt. Dabei soll der Algorithmus aber nicht
wissen, um welche Objekte es sich handelt. Dem entsprechend sollen erst die Objekte selbst dem
Algorithmus mitteilen, wie sie zu handhaben sind ( deren Fläche bzw. Volumen, Abmessungen und
weitere Infos mitteilen).

Habe ich richtig die Aufgabenstellung verstanden?

Mit freundlichen Grüßen

Alexander Kaisler

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

kaisler hat geschrieben: wird es einen Übungsblatt geben und wo kann man das Skript herunterladen?
Die Übungsaufgabe steht im Folienskript auf den Folien 4 und 5. Das Skript ist verfügbar auf der Seite zur LV: https://www.algo.informatik.tu-darmstad ... gorithmen/.

kaisler hat geschrieben: Soll es eine 2D oder 3D Anwendung werden?
2D

kaisler hat geschrieben: Die Aufgabe des Algorithmuses soll ja sein, dass er beliebige Objekte so dicht zusammenpacken
soll, damit sich die kleinst mögliche Bounding-Box ergibt. Dabei soll der Algorithmus aber nicht
wissen, um welche Objekte es sich handelt. Dem entsprechend sollen erst die Objekte selbst dem
Algorithmus mitteilen, wie sie zu handhaben sind ( deren Fläche bzw. Volumen, Abmessungen und
weitere Infos mitteilen).
Damit wäre im Algorithmus ja immer noch sichtbar, dass es um Rechtecke geht. Das ist also noch nicht abstrakt genug. 8)

Ich nehme an, Sie beziehen sich auf die lokale Suche von heute in der Vorlesung? Was der Algorithmus in einer Iteration sieht, ist (1) eine anonyme Lösung \(s^*\), (2) eine Möglichkeit, auf die ebenfalls anonymen benachbarten Lösungen \(s\) zuzugreifen sowie (3) eine Black Box, die eine solche anonyme Lösung bekommt und ihren Zielfunktionswert zurückliefert.

Hilft das weiter?

KW

kaisler
Neuling
Neuling
Beiträge: 2
Registriert: 24. Okt 2012 21:20

Re: Hallo und Programmieraufgabe

Beitrag von kaisler »

Danke für die schnelle Antwort und die Infos!

Was noch unverständlich ist, ist die anonyme Lösung s*,
und vor allem wie diese implementiert werden soll.

Ich habe vor OpenGL und C++ zu verwenden und dachte Polymorphismus
würde ausreichen, wenn der Algorithmus zu Compilezeit nicht weiß, welche
Objekte er sortieren soll.

Wenn ich Sie richtig verstanden habe, soll der Algorithmus nicht mal wissen,
dass er sortieren soll und erst zur Laufzeit soll ihm mitgeteilt werden, wie
die Aufgabe gelöst werden soll!

Hoffentlich werde ich eine Lösung finden, wenn ich mich mit der Aufgabe
beschäftigt, Skript mehrmals gelesen und kommende Vorlesungen besucht
habe. :!: :)

Mit freundlichen Grüßen
Alexander Kaisler

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

kaisler hat geschrieben: Ich habe vor OpenGL und C++ zu verwenden und dachte Polymorphismus
würde ausreichen, wenn der Algorithmus zu Compilezeit nicht weiß, welche
Objekte er sortieren soll.
Local Search ist bspw. auf das Steiner-Baum-Problem anwendbar, wo gar nichts sortiert wird. Das soll Ihre Implementation von Local Search auch. Das geht in C++ mit Polymorphie basierend auf Vererbung sehr gut. 8)

kaisler hat geschrieben: Wenn ich Sie richtig verstanden habe, soll der Algorithmus nicht mal wissen,
dass er sortieren soll und erst zur Laufzeit soll ihm mitgeteilt werden, wie
die Aufgabe gelöst werden soll!
Ja, was in C++ heißt: Im Algorithmus gibt es eine Referenz (oder meinetwegen auch ein Pointer) auf eine Basisklasse, und beim Aufruf des Algorithmus lässt man diese auf ein Objekt einer davon abgeleiteten Klasse verweisen.

Meist reicht in der Praxis sogar statische Polymorphie, also Temples: formaler vs. tatsächlicher Typ (mit Traits) statt Basisklasse vs. abgeleitete Klasse. Beides ist möglich, dynamische Polymorphie mit Vererbung aber wahrscheinlich einfacher zu implementieren.

KW

trinity
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 29. Sep 2009 12:57

Re: Hallo und Programmieraufgabe

Beitrag von trinity »

Hallo,

ich hätte noch einige grundsätzliche Fragen zur Implementierung.

1. Übergibt der Benutzer dem Programm eine Menge von Rechtecken (definiert über Breite und Höhe) oder eine Zahl der zu zeichnenden Rechtecke (aus der das Programm dann entsprechend viele zufällig große Rechtecke erzeugt) oder gar nichts (und das Programm erzeugt eine zufällige Anzahl zufällig großer Rechtecke)?

2. Wie groß sollen die Rechtecke maximal sein bzw. wie viele sollen maximal möglich sein? Sollen wir bei entsprechend großen/vielen Rechtecken die Anzeige so skalieren, dass die Bounding Box immer gerade so auf den Bildschirm passt, auch wenn die Rechtecke dann kaum noch zu erkennen sind? Oder sollen wir eine Möglichkeit zum zoomen einbauen?

Viele Grüße,
trinity

The One and Only Markus
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 169
Registriert: 10. Nov 2005 19:28
Wohnort: Darmstadt

Re: Hallo und Programmieraufgabe

Beitrag von The One and Only Markus »

Hier würde noch noch gerne eine 3. Frage ergänzen:

3. Sollen die Rechtecke ganzzahlige Längen/Höhen haben oder sollen das Fließkommazahlen sein?

Viele Grüße,
Markus

Benutzeravatar
Chase
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 5. Apr 2008 11:14

Re: Hallo und Programmieraufgabe

Beitrag von Chase »

Noch eine Frage:

Ist die Eingabe
a. nur eine Menge an Dimensionen von Rechtecken {(width, height)} und wir sollen "from scratch" eine Anordnung finden?
oder
b. eine Menge an Rechtecken mit Positionen {(x, y, width, height)} und wir sollen diese Anordnung sequentiell manipulieren? -> Das würde die Aufgabe durch einen "Schiebepuzzle-Effekt" deutlich schwerer machen.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

trinity hat geschrieben: 1. Übergibt der Benutzer dem Programm eine Menge von Rechtecken (definiert über Breite und Höhe) oder eine Zahl der zu zeichnenden Rechtecke (aus der das Programm dann entsprechend viele zufällig große Rechtecke erzeugt) oder gar nichts (und das Programm erzeugt eine zufällige Anzahl zufällig großer Rechtecke)?
Die zweite Option, der Benutzer gibt die Anzahl der Rechtecke an.

trinity hat geschrieben: 2. Wie groß sollen die Rechtecke maximal sein bzw. wie viele sollen maximal möglich sein?
So viele, wie auf einem Bildschirm noch sinnvoll darstellbar sind, also schon eine vierstellige Anzahl.

trinity hat geschrieben: Sollen wir bei entsprechend großen/vielen Rechtecken die Anzeige so skalieren, dass die Bounding Box immer gerade so auf den Bildschirm passt, auch wenn die Rechtecke dann kaum noch zu erkennen sind?
Ist wahrscheinlich das Sinnvollste.

trinity hat geschrieben: Oder sollen wir eine Möglichkeit zum zoomen einbauen?
Würde ich nicht verlangen wollen.

Beste Grüße,

KW

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

The One and Only Markus hat geschrieben: 3. Sollen die Rechtecke ganzzahlige Längen/Höhen haben oder sollen das Fließkommazahlen sein?
Ich empfehle Fließkommazahlen, die sollten sich leichter auf Pixel umrechnen lassen.

Beste Grüße,

KW

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

Chase hat geschrieben: Ist die Eingabe
a. nur eine Menge an Dimensionen von Rechtecken {(width, height)} und wir sollen "from scratch" eine Anordnung finden?
oder
b. eine Menge an Rechtecken mit Positionen {(x, y, width, height)} und wir sollen diese Anordnung sequentiell manipulieren? -> Das würde die Aufgabe durch einen "Schiebepuzzle-Effekt" deutlich schwerer machen.
a.

Beste Grüße,

KW

The One and Only Markus
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 169
Registriert: 10. Nov 2005 19:28
Wohnort: Darmstadt

Re: Hallo und Programmieraufgabe

Beitrag von The One and Only Markus »

Hallo zusammen,

ich bin mir nicht so ganz sicher wie ich eine sinnvolle Nachbarschaft meiner Rechteck-Anordnungen definieren kann.

Beispiel local search:
Die local search terminiert ja erst dann, wenn es keinen gültigen Nachbarn mit einer geringeren objective function zu meiner aktuellen Lösung gibt. Das heißt spätestens beim letzten Schritt muss ich mir alle Nachbarn einer Lösung ansehen, um sicher zu gehen, dass kein Nachbar eine Verbesserung darstellt. Also ist die Größe der Nachbarschaft der Lösungen sehr wichtig.

Wenn ich jetzt eine simple Nachbarschaft definiere, in dem ich genau ein Rechteck beliebig verschieben darf (so dass die Anordnung danach immer noch eine gültige Lösung ist) bekomme ich theoretisch schon eine unendliche Anzahl an Nachbarn für jede Anordnung, da ich ein Rechteck "beliebig weit draußen" positionieren kann. Schränkt man die maximale Größe des Zeichenfelds ein hat man zwar nur noch endlich viele, aber immer noch eine riesige Menge an Nachbarn, die man auf keinen Fall alle in Betracht ziehen kann. Es ist auch keine Option nur einen Teil dieser Verschiebungen als Nachbarschaft zu definieren. Da würde sich sofort die Frage stellen welche Verschiebunden in die Nachbarschaft reinkommen und welche nicht. Da die Nachbarschaft ja unabhängig von dem eigentlichen Optimierungsalgorithmus definiert wird wäre es schwer hier etwas brauchbares zu finden. Ist für die local search eine Nachbarschaft ausreichend, in der ich nur die äußersten Rechtecke verschieben darf muss das für andere Algorithmen nicht mehr gelten.

Eine andere Option wäre die Nachbarschaft durch Verschiebung nur um einen festen Wert zu erlauben. Das heißt man hätte pro Rechteck ca. 5 Bewegungen (hoch, runter, links, rechts, kippen). Dann hätte man nur ca. 5000 Nachbarn für 1000 Rechtecke, aber so eine Nachbarschaft wäre halt schon eine starke Einschränkung und würde glaube ich zu keinen guten Ergebnissen führen.

Also alles in allem mit der gegeben Vorgabe, dass die Nachbarschaft unabhängig vom Algorithmus definiert wird, eine knifflige Aufgabe :D

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

The One and Only Markus hat geschrieben: spätestens beim letzten Schritt muss ich mir alle Nachbarn einer Lösung ansehen, um sicher zu gehen, dass kein Nachbar eine Verbesserung darstellt. Also ist die Größe der Nachbarschaft der Lösungen sehr wichtig.
Yep.

The One and Only Markus hat geschrieben: Wenn ich jetzt eine simple Nachbarschaft definiere, in dem ich genau ein Rechteck beliebig verschieben darf (so dass die Anordnung danach immer noch eine gültige Lösung ist) bekomme ich theoretisch schon eine unendliche Anzahl an Nachbarn
Ja, klingt nicht nach der besten Vorgehensweise. 8)

The One and Only Markus hat geschrieben: Also alles in allem mit der gegeben Vorgabe, dass die Nachbarschaft unabhängig vom Algorithmus definiert wird, eine knifflige Aufgabe :D
Im Gegenteil, Sie haben volle Freiheit bei der Definition der Nachbarschaft. :shock:

Ein kleiner Hinweis aus den Implementationen früherer Teilnehmer: Sie müssen nicht unbedingt zulassen, dass jede beliebige Platzierung der Rechtecke produziert werden kann. Wenn Sie von vornherein nur bestimmte Konfigurationen zulassen - natürlich so, dass immer noch sehr gute Lösungen möglich sind -, dann wird das Thema Nachbarschaft vielleicht auch überschaubar. :idea:

KW

Pflücker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 129
Registriert: 21. Sep 2010 14:27

Re: Hallo und Programmieraufgabe

Beitrag von Pflücker »

Ist es gestattet bei der lokalen Suche Terminierungskriterien zu verwenden?
Hintergrund ist, dass ich mir einen Suchraum gewählt habe der eigentlich nicht finite ist.

Nächste Frage ist, ob es vom Grad der Abstraktheit her ausreicht, wenn die Algorithmen lediglich wissen, dass sie in einem beliebig dimensionalen Raum mit Vektoren aus Double-Werten arbeiten. (ohne zu wissen, was ein Punkt genau darstellt)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hallo und Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

Pflücker hat geschrieben:Ist es gestattet bei der lokalen Suche Terminierungskriterien zu verwenden?
Was meinen Sie mit "Terminierungskriterien"?

Pflücker hat geschrieben: Nächste Frage ist, ob es vom Grad der Abstraktheit her ausreicht, wenn die Algorithmen lediglich wissen, dass sie in einem beliebig dimensionalen Raum mit Vektoren aus Double-Werten arbeiten. (ohne zu wissen, was ein Punkt genau darstellt)
Nein, ich erwarte den Grad von Abstraktheit, auf dem die Algorithmen auf den Folien definiert sind. :shock: :twisted: 8)

KW

Antworten

Zurück zu „Optimierungsalgorithmen“