Programmieraufgabe

Moderator: Optimierungsalgorithmen

lustiz
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 29. Apr 2009 10:28

Programmieraufgabe

Beitrag von lustiz »

Hallo, nur eine kurze Frage: In der Aufgabe heisst es "the open interiors of any two rectangles do not intersect". Das bedeutet aber, dass sich die Kanten zweier Rechtecke beruehren duerfen. Liege ich da richtig? Sollte am Ende keinen grossen Unterschied machen, aber immerhin soll es ja aufgabengetreu sein.

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

Re: Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

lustiz hat geschrieben:Hallo, nur eine kurze Frage: In der Aufgabe heisst es "the open interiors of any two rectangles do not intersect". Das bedeutet aber, dass sich die Kanten zweier Rechtecke beruehren duerfen.
Korrekt.

KW

snntr
Neuling
Neuling
Beiträge: 10
Registriert: 19. Feb 2013 14:06

Re: Programmieraufgabe

Beitrag von snntr »

Hallo Herr Prof. Weihe,

ich habe auch eine Frage zur Programmieraufgabe und zwar zum Backtracking. Wir hatten in der Vorlesung Backtracking als Algorithmus zur Lösung von Constraint Satisfaction Problems. Das Rechteckproblem ist allerdings ein Optimierungsproblem. Sollen wir also das Problem zu einem CSP umformulieren (Zielfunktionswert < Schranke als Bedingungen und nicht als Optimierungskriterium) oder gibt es eine Möglichkeit Backtracking direkt zum Lösen von Optimierungsproblemen einzusetzen?

Viele Grüße

KKnauf

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

Re: Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

snntr hat geschrieben:gibt es eine Möglichkeit Backtracking direkt zum Lösen von Optimierungsproblemen einzusetzen?
Eine Möglichkeit ist die Folgende: Sie berechnen - zum Beispiel durch einen anderen Algorithmus - zuerst eine gute Lösung. Wann immer Sie mitten im Backtracking feststellen, dass Sie die durch die Platzierung der noch nicht platzierten Rechtecke (garantiert oder wahrscheinlich) keine bessere Lösung erhalten können, können Sie backtracken.

KW

mrzb6
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 4. Okt 2010 21:50
Wohnort: Darmstadt

Re: Programmieraufgabe

Beitrag von mrzb6 »

Hallo,

eine kurze Frage zur gewünschten Funktionsweise der Algorithmen: In den Folien heißt es
Implement a visualization that shows, step by step, how each algorithm places and removes rectangles in the plane.
Ist damit nur gemeint, dass Zwischenergebnisse dargestellt werden sollen, oder, dass mit einem Button ein einzelner Schritt eines Algorithmus' ausgeführt werden kann?
Momentan habe ich ersteres implementiert. Letzteres würde erfordern, dass man die Schleifeninhalte in eine Methode auslagert, was nicht gerade zur Übersichtlichkeit der Algorithmen beitragen würde...

Viele Grüße,
mrzb6

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

Re: Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

mrzb6 hat geschrieben: Ist damit nur gemeint, dass Zwischenergebnisse dargestellt werden sollen, oder, dass mit einem Button ein einzelner Schritt eines Algorithmus' ausgeführt werden kann?
Ersteres reicht.

mrzb6 hat geschrieben: Momentan habe ich ersteres implementiert. Letzteres würde erfordern, dass man die Schleifeninhalte in eine Methode auslagert, was nicht gerade zur Übersichtlichkeit der Algorithmen beitragen würde...
Doch, es ist durchaus gute Praxis, Schleifen "inside-out" zu schreiben, das heißt, die Initialisierung und das Vollziehen einer Iteration sind zwei Methoden, und die Schleife selbst ist im Anwendungscode. Dann kann der Anwender den Algorithmus beliebig mit weiterer Funktionalität anreichern, zum Beispiel schrittweise Visualisierung oder Protokollierung oder auch bidirektionale Kürzeste-Wege-Suche (=zwei "normale" Suchen in einer Schleife).

Abstrakter gesagt: So ließe sich das MVC-Pattern ideal implementieren, denn Control hat damit feingranularen Zugriff auf Model (=Algorithmus).

KW

aloifolia
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 22. Sep 2011 11:37

Re: Programmieraufgabe

Beitrag von aloifolia »

Ich habe eine ähnliche Frage wie die zum Backtracking oben: Sollen wir beim Greedy-Algorithmus einfach nur die erst mögliche Lösung generieren? Das wäre reichlich trivial, oder? Einfach alle Rechtecke nebeneinander zeichnen... dafür muss ich einfach nur die vom Zufallsgenerator vorgegebene Liste von Rechtecken als "Lösung" auswählen. :?

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

Re: Programmieraufgabe

Beitrag von Prof. Karsten Weihe »

aloifolia hat geschrieben:Ich habe eine ähnliche Frage wie die zum Backtracking oben: Sollen wir beim Greedy-Algorithmus einfach nur die erst mögliche Lösung generieren?
Manche Leute haben das tatsächlich so gemacht.

Aus solchen Gründen werde ich im nächsten Semester die Zielfunktion ändern: nicht mehr das flächenkleinste Rechteck, sondern das Quadrat. :twisted:

KW

aloifolia
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 22. Sep 2011 11:37

Re: Programmieraufgabe

Beitrag von aloifolia »

Oha! Na dann habe ich ja noch die freie Wahl. Mal sehen, was sich so machen lässt :)...

Antworten

Zurück zu „Optimierungsalgorithmen“