Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Moderator: Optimierungsalgorithmen

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Mathematics » 11. Nov 2014 15:09

Hallo zusammen,
wie genau verwaltet ihr die Nachbarschaft der einzelnen Rechtecksanordnungen (zunächst insbesondere bezogen auf die geometriebasierte Nachbarschaft)? Führt ihr eine Liste möglicher (kanonischer) Einfügungspunkte für Rechtecke, anhand derer ihr Nachbarlösungen konstruiert? Oder erzeugt ihr zunächst nicht-kanonische Anordnungen auf andere Weise und macht sie in einem zweiten Schritt dann kanonisch? Oder wie geht ihr sonst noch vor? Für einen neuen Denkanstoß wäre ich sehr dankbar, da mir mein bisheriger Ansatz nicht so recht gefällt.

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 20. Nov 2014 16:12

So, wie Sie Ihre Anfrage formuliert haben, fühle ich mich nicht angesprochen. 8)

Andere aber offenbar auch nicht. :(

KW

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Mathematics » 21. Nov 2014 08:06

Gut, dann formuliere ich es nochmal an Sie gerichtet um:

Wie finde ich garantiert alle zulässigen kanonischen Einfügungspunkte (d.h. Platzierungsorte für die oberen linken Ecken weiterer Rechtecke), ohne welche zu vergessen oder falsche zuzulassen? Konkreter: Platziere ich (z.B. im ZG oder im Rahmen der permutationsbasierten Lösungen) nacheinander Rechtecke, so ist nach Einfügen des ersten Rechtecks (Breite x1, Höhe y1) an der einzig zulässigen Position (0,0) ganz oben links die Situation noch klar. Für das zweite Rechteck stehen die Punkte (x1,0) und (0,y1) zur Verfügung, also letztlich gerade immer obere rechte und untere linke Ecke des vorherigen Rechtecks, um kanonisch zu bleiben. Allerdings wird das ganze schon problematischer, sobald "Vorsprünge" entstehen, weil das nächste eingefügte Rechteck breiter oder höher ist als das bisherige Gebilde. Will man nun weitere Einfügungspunkte ermitteln, kann man nicht einfach wieder obere rechte und linke untere Ecke des eingefügten Rechtecks zulassen, sondern muss die genannten Punkte eventuell noch senkrecht oder waagrecht weiterschieben, bis sie ein anderes Rechteck treffen. Zum Auffinden der verschobenen Einfügungspunkt habe ich mir ebenfalls Vorgehensweisen überlegt, kann allerdings immer noch Beispiele finden, die zu Problemen führen. Meine Frage ist nun eigentlich, ob dieser Weg zum Erfolg führt oder ich vielleicht ganz anders ansetzen sollte. In beiden Fällen wäre ein Hinweis hilfreich.

Bereits im Voraus im vielen Dank.

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 21. Nov 2014 08:14

Mathematics hat geschrieben:Gut, dann formuliere ich es nochmal an Sie gerichtet um:
Vielleicht fühlen sich erst einmal andere angesprochen? 8)

Ich bitte die Mitleser um Beiträge!

KW

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Mathematics » 25. Nov 2014 11:56

Bisher scheint niemand weiterhelfen zu können/wollen. Könnten Sie das also bitte tun?

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 25. Nov 2014 13:04

Mathematics hat geschrieben: Wie finde ich garantiert alle zulässigen kanonischen Einfügungspunkte (d.h. Platzierungsorte für die oberen linken Ecken weiterer Rechtecke), ohne welche zu vergessen oder falsche zuzulassen?
Muss die Frage nicht eher lauten: Wie muss ich eine Lösung aus einer gegebenen Reihenfolge der Rechtecke konstruieren, dass jede kanonische Lösung prinzipiell konstruierbar ist :?:

Mehr muss ja nicht sein. 8)

Eine kanonische Lösung, die mit einer gegebenen Reihenfolge der Rechtecke nicht machbar ist, kann ja vielleicht durch eine andere Reihenfolge machbar sein.

KW

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Mathematics » 2. Dez 2014 08:09

Ich strukturiere noch einmal meine Gedanken:

1) Gesucht ist ein gleichbleibendes Verfahren, nach dem Rechtecke aus einer Liste (unter Einbeziehung der Reihenfolge in der Liste) so platziert werden, dass eine kanonische Lösung entsteht.
2) Um dabei keine Lösungen zu verlieren, halte ich es für sinnvoll, sich beim Nacheinander-Einfügen der Rechtecke stets strikt an die Reihenfolge in der Liste zu halten.
3) Insbesondere wenn recht große und recht kleine Rechtecke wild durcheinander in der Liste stehen, stoße ich bei standardisierten Platzierungsverfahren (z.B. zeilenweise) auf Probleme (kanonisch bleiben trotz "zackigem" Rand des bisher platzierten Gebildes?).

Bis wohin sind die Überlegungen zielführend? Wie sollte ich weiterdenken?

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 2. Dez 2014 09:33

Mathematics hat geschrieben: 1) Gesucht ist ein gleichbleibendes Verfahren, nach dem Rechtecke aus einer Liste (unter Einbeziehung der Reihenfolge in der Liste) so platziert werden, dass eine kanonische Lösung entsteht.
Ja.

Ich nehme an, mit "gleichbleibend" meinen Sie ein deterministisches Verfahren, das jede Reihenfolge der Rechtecke nach demselben Schema behandelt?

Mathematics hat geschrieben: 2) Um dabei keine Lösungen zu verlieren, halte ich es für sinnvoll, sich beim Nacheinander-Einfügen der Rechtecke stets strikt an die Reihenfolge in der Liste zu halten.
Ja.

Mathematics hat geschrieben: 3) Insbesondere wenn recht große und recht kleine Rechtecke wild durcheinander in der Liste stehen, stoße ich bei standardisierten Platzierungsverfahren (z.B. zeilenweise) auf Probleme (kanonisch bleiben trotz "zackigem" Rand des bisher platzierten Gebildes?).
Ja. Aber genau das ist die Aufgabe der lokalen Suche: zu Reihenfolgen zu gelangen, die möglichst wenig Probleme macht.

KW

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Mathematics » 2. Dez 2014 10:11

Prof. Karsten Weihe hat geschrieben: Ja. Aber genau das ist die Aufgabe der lokalen Suche: zu Reihenfolgen zu gelangen, die möglichst wenig Probleme macht.
Trotzdem möchte die Aufgabenstellung, dass bereits alle schlechten Lösungen auf dem Weg zum lokalen Optimum alle kanonisch sind. Hierin liegt mein Problem. Denn es muss ja mit dem deterministischen Platzierungsverfahren auch aus einer unangenehmen Reihenfolge der Rechtecke eine kanonische Lösung erzeugt werden. Genau das gelingt mir momentan nicht.

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 2. Dez 2014 10:35

Mathematics hat geschrieben: Trotzdem möchte die Aufgabenstellung, dass bereits alle schlechten Lösungen auf dem Weg zum lokalen Optimum alle kanonisch sind. Hierin liegt mein Problem. Denn es muss ja mit dem deterministischen Platzierungsverfahren auch aus einer unangenehmen Reihenfolge der Rechtecke eine kanonische Lösung erzeugt werden. Genau das gelingt mir momentan nicht.
Ach so, jetzt verstehe ich, worauf Sie hinauswollen, sorry!

Ich habe den Begriff "kanonisch" und seine Definition speziell für diese Aufgabe definiert. Die genaue Definition ist also nicht "in Stein gemeißelt". Vielleicht sollte sie aufgrund Ihrer Erfahrung erweitert werden. Haben Sie einen Vorschlag?

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von aileen » 7. Jan 2015 17:10

Prof. Karsten Weihe hat geschrieben:
Mathematics hat geschrieben: Wie finde ich garantiert alle zulässigen kanonischen Einfügungspunkte (d.h. Platzierungsorte für die oberen linken Ecken weiterer Rechtecke), ohne welche zu vergessen oder falsche zuzulassen?
Muss die Frage nicht eher lauten: Wie muss ich eine Lösung aus einer gegebenen Reihenfolge der Rechtecke konstruieren, dass jede kanonische Lösung prinzipiell konstruierbar ist :?:
KW
Hallo,
hierzu habe ich eine Frage: Ist es wirklich nötig, jede kanonische Lösung prinzipiell konstruieren zu können? Oder ist damit eher gemeint, dass jede kanonische Lösung in der Nachbarschaft konstruiert werden kann?

Wenn ich mich zum Beispiel mit der geometriebasierten Nachbarschaft beschäftige & insbesondere mit dem Verschieben eines Rechtecks, muss ich dann wirklich jede mögliche Einfügungsposition für die Ecke des Rechtecks überprüfen? Wenn ich meine Nachbarschaft (jetzt nur in Bezug auf das Verschieben) so definieren würde, dass "Verschieben" nur bedeutet, das Rechteck entweder ganz oben rechts oder unten links neu zu platzieren, kann ich zwar nicht alle möglichen kanonischen Lösungen erhalten, aber alle kanonischen Lösungen innerhalb meiner Nachbarschaft schon.

Diese Nachbarschaft würde zwar wahrscheinlich zu einem nicht so guten Ergebnis führen, aber korrekt wäre das dann so trotzdem oder?

Ist es so gewollt, dass wirklich alle möglichen Einfügungspunkte überprüft werden? & wenn ja, wie macht ihr das? Ich habe momentan zu jeder Lösung nur die Informationen der linken oberen Ecke, Länge & Breite jedes Rechtecks & weiß nicht, wie ich das dann effizient umsetzen soll.

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 7. Jan 2015 19:06

aileen hat geschrieben: hierzu habe ich eine Frage: Ist es wirklich nötig, jede kanonische Lösung prinzipiell konstruieren zu können? Oder ist damit eher gemeint, dass jede kanonische Lösung in der Nachbarschaft konstruiert werden kann?
Mir ist nicht so recht klar, was Sie mit diesen beiden Optionen meinen bzw. was der Unterschied ist :?:

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von aileen » 7. Jan 2015 21:12

Sei die Nachbarschaftsbeziehung zum Beispiel nur durch Drehen von einzelnen Rechtecken gegeben und eine Instanz besteht aus 2 Rechtecken. Dann kann ich durch diese Nachbarschaftbeziehung zu keiner Lösung gelangen, bei der die Rechtecke zueinander anders angeordnet sind, als in der Startlösung (z.B. vertauschen der Rechtecke). Ich kann also zwar alle kanonischen Lösungen in der Nachbarschaft konstruieren (was immer der Fall ist?), es gibt aber auch kanonische Lösungen des Problems, die ich auf Grund dieser Nachbarschaftbeziehung nicht konstruieren kann.

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

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von Prof. Karsten Weihe » 8. Jan 2015 10:05

aileen hat geschrieben:Sei die Nachbarschaftsbeziehung zum Beispiel nur durch Drehen von einzelnen Rechtecken gegeben und eine Instanz besteht aus 2 Rechtecken. Dann kann ich durch diese Nachbarschaftbeziehung zu keiner Lösung gelangen, bei der die Rechtecke zueinander anders angeordnet sind, als in der Startlösung (z.B. vertauschen der Rechtecke). Ich kann also zwar alle kanonischen Lösungen in der Nachbarschaft konstruieren (was immer der Fall ist?), es gibt aber auch kanonische Lösungen des Problems, die ich auf Grund dieser Nachbarschaftbeziehung nicht konstruieren kann.
Ok, jetzt verstehe ich.

In diesem Fall kann natürlich nicht verlangt werden, dass alle kanonischen Lösungen gefunden werden können.

KW

the D
Erstie
Erstie
Beiträge: 14
Registriert: 27. Nov 2009 12:43

Re: Programmieraufgabe Nachbarschaftsbeziehung WS 14/15

Beitrag von the D » 12. Jan 2015 14:22

Hallo,

Ich habe folgende Frage an sie Prof. Weihe:

Aus der vorangegangenen Diskussion entnehme ich, dass es unter anderem Ziel der Aufgabe ist, einen Algorithmus zu entwickeln, der aus einer gegebenen Permutation von Rechtecken eine kanonische Lösung (nach hier gemachter Definition) erstellt. Dies soll deterministisch erfolgen, jede Permutation soll also bei jedem Mal exakt zur selben kanonischen Lösung führen. Gleichzeitig soll aber jede Kanonische Lösung prinzipiell konstruierbar sein (durch irgendeine bestimmte Permutation).

Falls ich das bereits falsch verstanden habe, korrigieren sie mich bitte :)

Falls nicht, komme ich aber auf einen Widerspruch, der diese beiden Bedingungen unvereinbar macht. Dies lässt sich auch leicht zeigen:

Bei n Rechtecken, gäbe es n! mögliche Permutationen. Es darf also auch nicht mehr mögliche kanonische Lösungen geben, denn sonst wäre bereits ausgeschlossen, dass alle kanonischen Lösungen konstruierbar sind. Nimmt man nun aber zum Beispiel eine Menge von 2 Rechtecken an ( = 2 mögliche Permutationen), dann lässt sich leicht überlegen, dass es mindestens 4 kanonische Lösungen geben muss, da man je eines von beiden Rechtecken zuerst am Koordinatenursprung platzieren kann und danach das zweite jeweils rechts davon oder darunter Platz hat ( = 4 kanonische Platzierungen). Betrachtet man die Vorgabe, dass Rechtecke auch noch rotiert werden dürfen, verdoppelt sich die Menge kanonischer Lösungen sogar grob überschlagen. Man hat dann bereits bei einem einzigen Rechteck ( = 1 mögliche Permutation) zwei Möglichkeiten es zu platzieren. Ein deterministischer Algorithmus würde stets eine davon unterschlagen.

In beiden Fällen ist das ein klarer Widerspruch, sofern ich keinen riesigen Denkfehler gemacht oder etwas falsch verstanden habe.

Können sie hierbei zur Klärung beitragen?

Antworten

Zurück zu „Optimierungsalgorithmen“