Hallo Ingo,
IngoAlthoefer hat geschrieben:
Du machst also eine Art "Branch and Bound".
Jein. Von
Branch-and-Bound spricht man laut Wikipedia offenbar bei Problemen, bei denen sich eine beliebige Lösung recht schnell ergibt, aber eigentlich die beste Lösung gesucht wird. Ich würde das Verfahren viel Banaler als "
Trial and Error" bezeichnen oder (um im IT-Jargon zu bleiben) "
Brute-Force".
IngoAlthoefer hat geschrieben:In welcher Reihenfolge füllst Du die Felder beim Durchprobieren auf?
Wie von Dir richtig vermutet, teste ich von links nach rechts und danach von oben nach unten.
IngoAlthoefer hat geschrieben:Etwas bessere Abschneideraten dürfte man aber bekommen, wenn man folgende Reihung nutzt: (Diagonal)
Keine gute Idee.
Es fängt mal damit an, daß ich mein Programm so gestaltet habe, daß sich anhand der vorgegebenen Farben automatisch die Größe des Spielbretts ergibt. Um das nächste Feld zu finden, gibt es drei einefach Regeln:
1.) Gehe ein Feld nach rechts.
2.) Wenn dabei der rechte Spielfeldrand überschritten wird, gehe eine Zeile runter und auf Spalte "1".
3.) Wenn auch der untere Spielfeldrand überschritten wird, wurden logischerweise alle Teile verbaut. Demnach wurde eine Lösung gefunden.
Für Deinen Diagonalen Ansatz müßte man vermutlich die Reihenfolge der Felder vorberechnen, denn dieses komplizierte Muster läßt sich nicht sinnvoll "in Echtzeit" berechnen. Hätte ich tatsächlich die Muße, das 2-Farben-Programm entsprechend umzubauen, würde ich die Reihenfolge manuell vorgeben, denn einen Algorithmus zu definieren, der dieses Muster auf einem 4x4-Brett erzeugt, würde wesentlich länger dauern, als die 16 Koordinaten von Hand zusammen zu tippen.
IngoAlthoefer hat geschrieben:wie schnell die beiden Reihungen im Vergleich arbeiten.
Die Frage ist leicht zu beantworten, auch ohne daß ich es empirisch teste:
Dein Ansatz ist ungefähr gleich schnell bis deutlich langsamer(!). Es sei denn... - aber dazu später.
Nehmen wir an, ich ich würde lediglich mein Verfahren (links nach rechts) durch Dein Verfahren (diagonal) ersetzen, dann dürfte sich an der Laufzeit nicht viel ändern - vielleicht wäre das Programm sogar im Promille-Bereich schneller, aber das würde kaum ins Gewicht fallen.
Nun ist aber Deine Argumentation, daß man durch die Diagonalen Rechenschritte einsparen könnte: Das stimmt so leider nicht, denn ein Puzzel-Teil paßt immer dann auf's freie Feld, wenn oben und links entweder die Farben überein stimmen oder aber das angrenzende Feld leer ist. Insofern würde sich daraus keine einzige Einsparung ergeben, weil ich ja doch immer beide Bedingungen prüfen muß.
Man könnte jetzt auf die Idee kommen, noch eine Fallunterscheidung einzubauen, bei welchen Feldern man überhaupt welche Nachbarn prüfen muß, aber von den 16 Feldern haben nur die oberen und linken Seiten jeweils einen Nachbarn (unten und rechts braucht nicht geprüft zu werden, denn diese Felder sind ja jeweils noch leer). Das würde aber bedeuten, daß man bei 7 von 16 Feldern (=44%) minimal Rechenzeit sparen könnte, aber dafür bei 100% aller Fälle zusätzliche Prüfungen durchführen müssen. Unterm Strich würde sich eine massive Verschlechterung ergeben.
Wie oben erwähnt, könnte Deine Idee unter gewissen Rahmenbedingungen etwas bringen: Es gibt Programmiersprachen (wie z.B. "C"), in denen man den Anfangspunkt einer Programmfunktion in einer Variable hinterlegen kann, so daß man quasi im Vorfeld für alle 16 Felder vordefinieren kann, welche Tests ausgeführt werden sollen. Man könnte also bei 44% der Tests jeweils vielleicht 5-10% Zeit sparen - im Optimalfall also rund 5%. Aus dem Bauch heraus glaube ich aber nicht, daß es sich tatsächlich so stark bemerkbar macht, denn Du möchtest ja die "einfachen" Tests am Anfang machen. Tatsächlich ist es aber so, daß Anfang der Suche jeder Baustein vergleichsweise selten gewechselt wird. Je weiter man nach hinten kommt, desto öfter müssen die Tests ausgeführt werden. Es ist also eher vorteilhaft, auch am Ende noch ein paar dieser "einfachen" Tests übrig zu haben - und das trifft eher auf meine lineare Methode zu.
Unterm Strich müßte man viel Arbeit für einen vergleichsweise geringen Nutzen investieren. Viel effektiver wäre es wohl, wenn ich eine andere Sprache verwenden würde, denn ich bin Fan von
PERL, das sich wesentlich besser für kaufmännische Anwendungen eignet und nur bedingt für mathematische Spielereien. Auch eine modernere Hardware anstelle meiner Antiquität würde wohl einiges bringen.
Gruß
Thomas
PS:
3 Farben: Bislang über 9500 gefundene Lösungen nach 9.8 Mrd. Zügen
4 Farben: Nach über 22 Mrd. Zügen noch immer keine Lösung in Sicht. Die Suche dümpelt nach wie vor bei rund 200 verbauten Teilen vor sich hin.
\\//_ Build long and ℘rosper!
