Umsetzungsproblem

[uthred]

Servus,

Ich habe gerade ein kleines Verständnissproblem für die Umsetzung von meinen geplanten Programm.

Also ich habe einen Ausgangszustand A von dieser hat 12 Zugmöglichkeiten, jeder dieser Züge hat 11 Zug Möglichkeiten und jeder dieser Züge hat ebenfalls 11 Zug Möglichkeiten, maximal gibt es 20 Züge.

Die Zugmöglichkeiten lauten zug(int(1-6), Boolean(true/false)).

Außerdem soll die Möglichkeit bestehen, einen Zug rückgängig zu machen und von dort dann einen anderen Zug zu machen), dafür müssen alle 20 Züge gespeichert werden...

Ich werde auch noch weitere Einschränkungen finden, aber erstmal stellt sich mir die Frage, wie setze ich das überhaupt um?

Mein bisheriger Ansatz und die Frage, wie bekomme ich das effektiver hin:

             int zugzaehler=0;

		Boolean solved=false;

		Boolean clockwise=true;

		while(solved==false){

			int seite=1;

		           clockwise=true;

			while(zugzaehler<20)

			{

				while(seite<=6){

                                                    zug(seite,clockwise);

                                                    solved=is_solved();

				        if(solved==true)

				       {

					break;

                                                    }

                                                    seite=+1;

                                                    zugzaehler=+1;

                                             }

                                             clockwise=false;

                                   }

                      }

[ricardo1885]

Ich würde an deiner Stelle mit einem einfachen Array-Arbeiten, der 20 Stellen (für die Züge) enthält. Jeder Zug bekommt dann an seiner Stelle seine entsprechende Nummer... 1-12 oder 1-11.

[lilith2k3]

Ich verstehe nur Bahnhof.

Du solltest vielleicht über einene Baumstruktur zur Abbildung des Problems nachdenken.

[Gast runtimeterror]

Irgendwie habe ich bei deinen Posts immer das Gefühl, dass du gerne in Rätseln sprichst. Ich habe den Beitrag mehrfach lesen müssen um zu erahnen, was du vorhast.

Ich rate einfach mal, dass du dich an einer Brute-Force-Lösung für den Rubiks Zauberwürfel versuchst.

Denke daran, dass du so 12×11^19 Kombinationen durchprobierst. Ohne es nachgerechnet du haben ist das eine Zahl mit der du nicht glücklich wirst.

Dein Algorithmus erlaubt nicht die Drehung einer Seite um 180°; ist das Absicht?

Die Zeile "seite=+1" wird nicht das tun, was du dir erhoffst

Der generelle Ansatz für deinen Algorithmus ist das Backtracking-Verfahren, welches am Einfachsten als Rekursion implementiert wird.

Die oben erwähnte Variante mit dem Array würde ich als Optimierung implementieren, sobald der Rest funktioniert.

Ich hoffe, das hilft dir weiter.

[uthred]

Dankeschön, ja das hilft schon mal weiter. Zumindest weiß ich jetzt worum es geht. Denn unser Lehrer hat uns nur die einzelnen Drehmethoden genannt und das Ziel wie es aussehen soll, ohne dabei den Zauberwürfel zu erwähnen, anscheinend sollten wir nicht einfach fertige Algorithmen übernehmen.

Wisst ihr wie man die Mathematik der Linearenoptimierung auf dieses Problem projiziert. Die Lineare Optimierung soll das Ziel sein. Die Mathematik dahinter glaube ich zu verstehen, aber ich weiß nicht wie ich die lineare Optimierung darauf anwende.

Bearbeitet 20. Februar 2013 von uthred

[flashpixx]

Wisst ihr wie man die Mathematik der Linearenoptimierung auf dieses Problem projiziert. Die Lineare Optimierung soll das Ziel sein. Die Mathematik dahinter glaube ich zu verstehen, aber ich weiß nicht wie ich die lineare Optimierung darauf anwende.

Simplex-Verfahren wäre mit das bekannteste Verfahren aus der linearen Optimierung, aber das wird Dir hier nicht helfen, weil Du hier kein Optimierungsproblem hast. Die Lösungsstrategie lässt sich als gruppentheoretischer Algoritmus beschreiben, wobei ich dazu auch Java für eine völlig falsche Sprache, solche Probleme löst man GAP (Software)

[uthred]

Naja, ein 3 Dimensionales Koordinatensystem kann den Würfel mit x Ebenen darstellen und die Lösung für jeden Würfel(3x3x3) ist <20

Jede einzelne Bewegung ist vorgegeben, ich sehe da rein von der Logik her schon das Optimierungsproblem.

[flashpixx]

Jede einzelne Bewegung ist vorgegeben, ich sehe da rein von der Logik her schon das Optimierungsproblem.

Ah ja und wo sind bei dieser Problemstellung die lineare Funktionen?

[uthred]

Die müsste ich noch finden, aber ich habe das irgendwo gelesen...

[Klotzkopp]

ich sehe da rein von der Logik her schon das Optimierungsproblem.

Was willst du denn überhaupt optimieren?

[uthred]

Ich will den kürzesten Weg finden einen Zauberwürfel zu lösen, also den "optimalen Weg", dafür muss ich den kompletten Algorithmus auf eine eindimensionale Array aufbauen (54 Werte). Ich weiß (bzw es wurde vorgegeben das dieser Würfel in 20 Zügen zu lösen sei. Die Bewegungsmethoden (12 Stück Für jede Seite 2 (clockwise, counterclockwise) sind vorgegeben.

Ich muss diesen Code auch erklären können.

Ein Zug ist definiert durch die Bewegung einer Seite (egal ob 1x(clockwise), 2x, 3x(counter-clockwise))

[flashpixx]

Ich will den kürzesten Weg finden einen Zauberwürfel zu lösen, also den "optimalen Weg", dafür muss ich den kompletten Algorithmus auf eine eindimensionale Array aufbauen (54 Werte).

Dieses Problem ist aber nicht linear. Du willst aus eine Menge an Lösungen die Lösung mit einer bestimmten Bedingung finden und das ist so erst mal NP-vollständig, denn ohne Randbedingungen musst Du Dir jede Lösung anschauen und prüfen, ob sie eben "optimal" ist.

Ich weiß (bzw es wurde vorgegeben das dieser Würfel in 20 Zügen zu lösen sei. Die Bewegungsmethoden (12 Stück Für jede Seite 2 (clockwise, counterclockwise) sind vorgegeben.

Zauberwürfel

Gottes Algorithmus

Der Algorithmus setzt letztendlich die algebraische Gruppe entsprechend um, d.h. Du solltest damit beginnen, zu verstehen, was Gruppen und Graphen in der Algebra sind, denn das benötigst Du, um daraus passenden Code zu schreiben

[uthred]

naja hab ja noch einen Monat Zeit, um von Wissensstand Null bis zur Lösung zu kommen

[flashpixx]

naja hab ja noch einen Monat Zeit, um von Wissensstand Null bis zur Lösung zu kommen

ich glaube Dir ist nicht klar, welche Komplexität das Problem hat

[uthred]

Nach Bruteforce-methode ca.4 Billionen Züge, ein Jahrelang entwickelten Algorithmus innerhalb von vier Wochen verstehen und Umsetzen, mathematische Methoden die man sonst eher bei Studenten sieht(die ganzen Speedcuber wurden meist von Studenten entwickelt) und zuletzt Programmiertechniche Methoden, die ich erst lernen muss (Ausbildung).

Ich glaube schon das ich die Komplexität begriffen habe, aber Aufgeben kommt nicht in Frage und verzweifeln hilft auch nicht.