Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.comp.lang.java > #12917 > unrolled thread

Rekursion bricht nicht ab

Back to article view | Back to de.comp.lang.java

Contents

  Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-08 23:28 +0200
    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-09 16:13 +0200
      Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:41 +0200
        Re: Rekursion bricht nicht ab Peter Büttner <not_for_mail_peb@gmx.net> - 2016-04-10 16:45 +0200
          Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 18:28 +0200
            Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-13 19:25 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 21:56 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 17:31 +0200
                    Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:53 +0200
                      Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:56 +0200
                  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 19:22 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 00:42 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 09:20 +0200
                Re: Rekursion bricht nicht ab Christoph Schneegans <Christoph@Schneegans.de> - 2016-04-14 18:47 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                  Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:07 +0200
                    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 17:38 +0200
                    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 22:36 +0200
                      Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-28 08:26 +0200
        Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-10 22:15 +0200
          Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:46 +0200
            Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:32 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 20:44 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-14 12:07 +0200
                  Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-23 13:35 +0200
                    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 14:57 +0200
                      Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 23:05 +0200
                        Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-26 01:16 +0200
                    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 16:05 +0200
                      Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:48 +0200
    Re: Rekursion bricht nicht ab v_borchert@despammed.com (Volker Borchert) - 2016-04-10 06:07 +0000
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:40 +0200
    Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-11 11:21 +0200
      Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:57 +0200
        Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:28 +0200
          Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 23:36 +0200
            Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 21:42 +0200

Page 2 of 2 — ← Prev page 1 [2]

#12968

In article <nflv4p$vkq$1@newsreader4.netcologne.de>, Patrick Roemer 
(sangamon@netcologne.de) says...

> >   Du mußt Ausnahme nicht werfen, sondern kannst sie auch zurückgeben:
> > 
> > java.lang.Exception toReciprocal()
> > { if( this.getDouble() != 0 ){ this.set( 1 / this.getDouble() ); return null; }
> >   else return new DivisionByZeroException( this.getDouble() ); }
> >        ¯¯¯¯¯¯
> 
> Gibt es eigentlich einen Fachausdruck für sachlich korrekten Unfug? :)

Wenn er funktioniert: Hack.
Wenn er sinnfrei ist: WTF ( Kandidat für: http://thedailywtf.com/ )

Gruß,
-Wanja-


-- 
..Alesi's problem was that the back of the car was jumping up and down 
dangerously - and I can assure you from having been teammate to 
Jean Alesi and knowing what kind of cars that he can pull up with, 
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]

[toc] | [prev] | [next] | [standalone]

#12925

Responding to Christian H. Kuhn:
> Am 09.04.2016 um 16:13 schrieb Patrick Roemer:
[...]
> Also erstmal versucht, das kleinstmögliche Szenario zu finden. Und
> dabei festgestellt, dass der Rekursionsbaum bei sonst gleichbleibenden
> Bedingungen exponentiell mit der Anzahl der leeren Reagenzgläser
> wächst.

Das klingt so, als könntest Du den Suchraum verkleinern, indem Du Dein
Modell so umstellst, dass es Gläser gleichen Inhalts zu einem möglichen
Bearbeitungsschritt zusammenfasst.

Also statt

[[a,b], [a,b], [b,a], [], []]
=> move b to empty
[[b], [a,b], [b,a], [a], []]

sowas wie

{[a,b] -> 2, [b,a] -> 1, [] -> 2}
=> move b to empty
{[a] -> 1, [b] -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

> Ich hatte keine nicht abbrechende Rekursion, ich habe
> lediglich die Rechenzeit massiv unterschätzt. Tage statt Minuten. Ich
> werde also einen anderen Ansatz verwenden müssen, der den Suchbaum
> Stufe für Stufe aufbaut und auf Lösungen überprüft, bevor die nächste
> Stufe berechnet wird.

Das wäre äußerst sinnvoll. :) Breitensuche statt Tiefensuche, und die
erste gefundene Lösung zurückgeben, die ist dann schon kürzestmöglich.

Ggfs. könnte man dann noch Heuristiken anwenden, um auf jeder Stufe die
"erfolgversprechendsten" Spielstände und -züge jeweils zuerst
auszuprobieren.

>> Zumindest wäre es sinnvoll, ein paar funktionierende Testfälle 
>> beizulegen, und einen, der das Problem demonstriert.
> Sind in LSBoard.main().

Hmnaja... Anhand Deiner initialen Beschreibung hätte ich erwartet, dass
die schon in einzelne Unit-Tests gegossen sind.

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12927

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Am 10.04.2016 um 22:15 schrieb Patrick Roemer:

> Also statt
> 
> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
> [b,a], [a], []]
> 
> sowas wie
> 
> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Ich hab inzwischen sowas ähnliches gemacht, aber ganz anders ;-) Ich
habe die Hashcode-Berechnung geändert. (a,b), (b,a), (), () hat jetzt
den gleichen Hashcode wie (), (b,a), (), (a,b). Das hat für die
Testfälle mit zwei Farben und zwei Bewohnern pro Glas die Rechenzeiten
in erträgliche Dimensionen gebracht. Für reelle Berechnungen reicht es
leider noch nicht.

lg
QNo

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJXDPwjAAoJEGVI2lsCpSdTbVQP/0sydSsbSWY5rZEj3reR50us
xFu64oi1yvCDuo1ZT1Hmr4x4v1oG7fnONdf179VcsY+YYS5KpqSrfd9+3cZu9DY1
xDGBZBZXquEIyT7zzrolNfcohgKLymiCuZHAfAxneDwthTZuTx7uhwakRyIHCj+x
kNc+92WPz9bq6hGMLzero5wm4RJY5KLuxcYbTMQgP2jxXI20y1zkymbzBakdWBnF
LaKCnqCHz3eravEbUeBVCNsbi7H4Lzx/Sxu7QSZnMFyZAZNXSSROWonJuNmY8OFD
b+7cABlH9HCXLcoQnSVPqptyyNGQ6tI3BjgkphTJrovWhh0DXIIfbaP1W9ALL5X4
eFHK6+Y1ioYZHQ/VGpqRW8FdeYSa8anDETuMeT+l+dIuUUzCOeYFKsAxqK67yV8T
slkLVDDe81QixJOYYmmUmTqr1VoasldosG2wH4KrQSYn7WR6cOr4Tn6Akuxm/j2Z
XfGkS0QV4FxDkJ+96+HqYBcKNK1P6ZmJs1Q2PVdMPsEMb7rVXmnkU/sBGi6Xsp9m
gWsEio8WDkI2siR9maOSQflTT1ks/xq6aQ9diiCDcHJGgLlaSgmvWc8r4Jw6XUKj
Al7p3zJAqFu7slWCW8d6wuH53YUpxX5rMlc+AQb1qvPcGUGwtU7Jb+ifk7H0DMWG
9kpc0Ke+j/pIxXvixTXT
=idQL
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#12930

Responding to Christian H. Kuhn:
> Am 10.04.2016 um 22:15 schrieb Patrick Roemer:
> 
>> Also statt
> 
>> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
>> [b,a], [a], []]
> 
>> sowas wie
> 
>> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
>> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Das sollte natürlich jeweils "move a to empty" heissen. m(

> Ich hab inzwischen sowas ähnliches gemacht, aber ganz anders ;-) Ich
> habe die Hashcode-Berechnung geändert. (a,b), (b,a), (), () hat jetzt
> den gleichen Hashcode wie (), (b,a), (), (a,b). Das hat für die
> Testfälle mit zwei Farben und zwei Bewohnern pro Glas die Rechenzeiten
> in erträgliche Dimensionen gebracht. Für reelle Berechnungen reicht es
> leider noch nicht.

Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
ausprobieren. :)

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12933

Am 12.04.2016 um 18:32 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
>> Am 10.04.2016 um 22:15 schrieb Patrick Roemer:
>>
>>> Also statt
>>
>>> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
>>> [b,a], [a], []]
>>
>>> sowas wie
>>
>>> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
>>> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

> Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
> nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
> ausprobieren. :)

Hab ich dann auch mal ausprobiert, aber anders.

public final Vector<LSMove> getMoveList() {
        Vector<LSMove> moveList = new Vector<LSMove>();
        HashSet<Integer> startTubes = new HashSet<Integer>();
        for (int i = 0; i < boardSize; i++) {
            if (startTubes.contains(tubes.get(i).hashCode())) {
                continue;
            }
            startTubes.add(tubes.get(i).hashCode());
            HashSet<Integer> targetTubes = new HashSet<Integer>();
            for (int j = 0; j < boardSize; j++) {
                if (targetTubes.contains(tubes.get(j).hashCode())) {
                    continue;
                }
                targetTubes.add(tubes.get(j).hashCode());
                LSMove move = new LSMove(i, j);
                try {
                    isLegalMove(move);
                    moveList.add(move);
                } catch (LSBoardBadSizeParameterException |
LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
                        | LSBoardFullTargetTubeException |
LSBoardDifferentColoursException e) {
                    // illegale Züge werden einfach nicht geaddet, keine
weitere Aktion nötig.
                }
            }
        }
        return moveList;
    }

Mit erstaunlichen Ergebnissen:

    public static void main(final String[] _args) throws Throwable {

        // Ohne Zugreduzierung: 499 ms, mit 864 ms.
        // LSBoard board = new LSBoard(4, 3, 2);
        // Vector<Vector<Character>> positionOneLevelOne = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'c', 'b')),
        // new Vector<Character>(Arrays.asList('a', 'a', 'c', 'c')),
        // new Vector<Character>(Arrays.asList('c', 'a', 'b', 'b'))));

        // Ohne Zugreduzierung: 39 ms, mit 33 ms.
        // LSBoard board = new LSBoard(3, 2, 2);
        // Vector<Vector<Character>> positionOne = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'b'))));

        // Ohne Zugreduzierung: 231 ms, mit 340 ms.
        // LSBoard board = new LSBoard(4, 4, 1);
        // Vector<Vector<Character>> positionTwentyLevelTwo = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a', 'c')),
        // new Vector<Character>(Arrays.asList('c', 'd', 'c', 'd')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'b', 'd')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'c', 'd'))));

        // Ohne Zugreduzierung: 2496251 ms, mit 2270765 ms.
        LSBoard board = new LSBoard(4, 10, 2);
        Vector<Vector<Character>> positionOneLevelFour = new
Vector<Vector<Character>>(
                Arrays.asList(new Vector<Character>(Arrays.asList('a',
'b', 'c', 'd')),
                        new Vector<Character>(Arrays.asList('b', 'c',
'e', 'f')),
                        new Vector<Character>(Arrays.asList('f', 'g',
'e', 'h')),
                        new Vector<Character>(Arrays.asList('h', 'c',
'g', 'e')),
                        new Vector<Character>(Arrays.asList('b', 'h',
'i', 'g')),
                        new Vector<Character>(Arrays.asList('a', 'd',
'd', 'i')),
                        new Vector<Character>(Arrays.asList('f', 'a',
'i', 'j')),
                        new Vector<Character>(Arrays.asList('i', 'j',
'b', 'g')),
                        new Vector<Character>(Arrays.asList('j', 'e',
'a', 'j')),
                        new Vector<Character>(Arrays.asList('h', 'f',
'c', 'd'))));

        board.initializeBoard(positionOneLevelFour);
        long startTime = System.nanoTime();
        LSResult result = board.result();
        long endTime = System.nanoTime();
        long elapsedTime = (endTime - startTime) / 1000000;

        System.out.println("Lösung:");
        for (LSMove move : result.getOneShortestSolution()) {
            System.out.println(move.toString());
        }
        System.out.printf("Zeit: %1$d ms", elapsedTime);
    }

Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
als der größere Baum.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#12937

Responding to Christian H. Kuhn:
> Am 12.04.2016 um 18:32 schrieb Patrick Roemer:
>> Responding to Christian H. Kuhn:
>>> Am 10.04.2016 um 22:15 schrieb Patrick Roemer:
>>>
>>>> Also statt
>>>
>>>> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
>>>> [b,a], [a], []]
>>>
>>>> sowas wie
>>>
>>>> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
>>>> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}
> 
>> Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
>> nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
>> ausprobieren. :)
> 
> Hab ich dann auch mal ausprobiert, aber anders.

Das "anders" ist wahrscheinlich das Problem. ;) s.u.

> public final Vector<LSMove> getMoveList() {
>         Vector<LSMove> moveList = new Vector<LSMove>();
>         HashSet<Integer> startTubes = new HashSet<Integer>();
>         for (int i = 0; i < boardSize; i++) {
>             if (startTubes.contains(tubes.get(i).hashCode())) {
>                 continue;
>             }
>             startTubes.add(tubes.get(i).hashCode());
>             HashSet<Integer> targetTubes = new HashSet<Integer>();
>             for (int j = 0; j < boardSize; j++) {
>                 if (targetTubes.contains(tubes.get(j).hashCode())) {
>                     continue;
>                 }
>                 targetTubes.add(tubes.get(j).hashCode());
>                 LSMove move = new LSMove(i, j);
>                 try {
>                     isLegalMove(move);
>                     moveList.add(move);
>                 } catch (LSBoardBadSizeParameterException |
> LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
>                         | LSBoardFullTargetTubeException |
> LSBoardDifferentColoursException e) {
>                     // illegale Züge werden einfach nicht geaddet, keine
> weitere Aktion nötig.
>                 }
>             }
>         }
>         return moveList;
>     }

Dass die Exceptions hier sowohl semantisch als auch von der Performance
her eher fehl am Platz sind, hast Du ja anderweitig schon festgestellt. :)

if(isLegalMove(move)) {
  moveList.add(move);
}

(Bzw. erst gar keine illegalen Züge generieren.)

Das hashCode-Gewerkel finde ich weiterhin äußerst fishy...

> Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
> als der größere Baum.

Gemeint war auch nicht, in jedem Einzelschritt umzukopieren, sondern
durchgehend auf einem Modell a la Map<List<Character>, Integer> zu arbeiten.

Anyway, solange der Algorithmus an sich suboptimal ist, sind Experimente
auf dieser Ebene eher unangebracht. Bau halt mal auf echte Breitensuche
um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.
Danach kann man immer noch weiter optimieren.

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12947

Am 14.04.2016 um 12:07 schrieb Patrick Roemer:

> Bau halt mal auf echte Breitensuche
> um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.

Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
in die Queue getan. While bricht ab, wenn die Queue leer ist.

In der While-Schleife wird die Stellung und die bisherige Zugliste aus
der Queue entnommen. Wenn die Stellung eine Lösung ist, wird ein
Lösungsobjekt aus der Zugliste gebildet und zurückgegeben.

Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
weitergezählt.

Ansonsten wird bigHashCode() zur Liste der gesehenen Stellungen
zugefügt. Es wird die Liste der möglichen Züge ermittelt. Aus der
aktuellen Position werden die Positionen der nächsten Tiefe und die dazu
führenden Zuglisten erzeugt und in die Queue getan.

Massiver Rückgang der Rechenzeit. Beispiele:

(Jeweils: 1. Levelweise Tiefensuche, Zugerzeugung incl. illegaler Züge,
Prüfung auf legal bei Ausführung. 2. dto, Zugerzeugung erzeugt nur
legale Züge. 3. Breitensuche mit FIFO)

(a, b, a) (a, b, b), zwei leere Gläser. 1. 39 ms, 2. 28 ms, 3. 12 ms.

Erste Stellung Level 1:
(a, b, c, b) (a, a, c, c) (c, a, b, b), zwei leere Gläser. 1. 499 ms, 3.
67 ms.

Stellung 20 Level 2:
(a, b, a, c), (c, d, c, d) (a, b, b, d) (a, b, c, d), ein leeres Glas.
1. 231 ms, 2. 340 ms, 3. 35 ms.

Stellung 1 Level 4:
(a, b, c, d) (b, c, e, f) (f, g, e, h) (h, c, g, e) (b, h, i, g) (a, d,
d, i) (f, a, i, j) (i, j, b, g) (j, e, a, j) (h, f, c, d), zwei leere
Gläser. 1. 2270765 ms, 2. 105984 ms, 3. 4261 ms.

Ich danke an der Stelle nochmals allen, die sich beteiligt haben. Ich
habe durch eure Beiträge viel gelernt. Im nächsten Semester werde ich im
Master wohl „Effiziente Graphenalgorithmen“ hören und die Problematik in
dem Zusammenhang nochmal aufgreifen. Vielleicht wird ein kleiner Artikel
daraus.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#12948

Responding to Christian H. Kuhn:
> Am 14.04.2016 um 12:07 schrieb Patrick Roemer:
> 
>> Bau halt mal auf echte Breitensuche
>> um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.
> 
> Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
> Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
> geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
> in die Queue getan. While bricht ab, wenn die Queue leer ist.

Genau. :)

> Massiver Rückgang der Rechenzeit. Beispiele:
[...]
> Stellung 1 Level 4:
> (a, b, c, d) (b, c, e, f) (f, g, e, h) (h, c, g, e) (b, h, i, g) (a, d,
> d, i) (f, a, i, j) (i, j, b, g) (j, e, a, j) (h, f, c, d), zwei leere
> Gläser. 1. 2270765 ms, 2. 105984 ms, 3. 4261 ms.

Das sieht doch gut aus. Da dürfte immer noch Luft drin sein, aber nicht
mehr in der Größenordnung, die man durch die Algorithmenwahl erreicht.
*Jetzt* wäre der Punkt, wo man mal hprof/visualvm anwerfen könnte und
anhand der so gefundenen Hotspots low-level-Optimierungen ausprobieren
könnte.

Spontan würde mir einfallen:
- Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
Gläser zusammengefasst werden.
- Vector<Character> durch String ersetzen.
- Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.
- Vector durch ArrayList ersetzen.

Keine Ahnung, ob und wieviel das jeweils bringt, da muss man dann
wirklich im Vergleich messen. Zumindest bei den ersten beiden wäre ich
aber zuversichtlich.

Ausserdem würde ich das explizite Gewerkel mit dem Hashcode und das
Cloning auf den Prüfstand stellen. IMHO leidet die Codeverständlichkeit
darunter, es bietet Raum für zusätzliche Fehlerquellen, und vom
Bauchgefühl her würde ich da keinen Gewinn von erwarten - zumindest
keinen signifikanten. Ich würde anstelle des "bigHashCode" die
eigentlichen Objekte mit "normalem" #equals() und #hashCode() verwenden,
und den copy constructor statt des #clone().

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12966

Am 23.04.2016 um 14:57 schrieb Patrick Roemer:
> - Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
> Gläser zusammengefasst werden.

Geht halt nicht unbeschränkt. (a,a,a) () ist zwar ideell dasselbe wie ()
(a,a,a), sieht aber anders aus. Das sind auf dem Screen zwei
verschiedene Stellungen. Wenn ich die einheitlich repräsentiere, brauche
ich nicht nur einen Algorithmus, der die tatsächliche Stellung in die
vereinfachte überführt, sondern auch einen, der sie dann incl. Lösung
zurücküberführt. Selbst Chessbase, bei denen Jahrzehnte an Entwicklung
und viel Geld dahinter stehen, hatten neulich noch einen Bug drin: Eine
Stellung ist durch eigenartiges Spiel mit vertauschten Farben
entstanden, Schwarz am Zug, bei „regulärem“ Verlauf wäre Weiß am Zug.
Chessbase hat die Identität der Stellung erkannt, aber die Lösung nicht
transformiert. Züge wurden angegeben, als sei Weiß am Zug. Irritierend.

> - Vector<Character> durch String ersetzen.

Ich dachte, veränderliche Dinge sind durch konstante Strings schlecht
repräsentiert?

> - Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
> bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.

In der Breitensuche sicher sinnvoll. Da wird man aber aufpassen müssen,
dass man nicht soviel Optimierungslogik erzeugt, dass die Optimierung
aufwändiger als die Lösung ist :-)

> - Vector durch ArrayList ersetzen.

Das hatte ich mir schon mal vorgenommen, mich in die Details einzulesen,
wann welche Liste/Vector besser ist.

> Ausserdem würde ich das explizite Gewerkel mit dem Hashcode und das
> Cloning auf den Prüfstand stellen. IMHO leidet die Codeverständlichkeit
> darunter, es bietet Raum für zusätzliche Fehlerquellen, und vom
> Bauchgefühl her würde ich da keinen Gewinn von erwarten - zumindest
> keinen signifikanten. Ich würde anstelle des "bigHashCode" die
> eigentlichen Objekte mit "normalem" #equals() und #hashCode() verwenden,
> und den copy constructor statt des #clone().

Ich habe das mal ausprobiert, dass ich keine HashSet<BigInteger>,
sondern wirklich eine HashSet<LSBoard> verwende. Erster Durchlauf:
Katastrophe. War im Nachhinein auch klar, denn in bigHashCode() bekommen
unterschiedliche, aber äquivalente Stellungen den gleichen Hashcode,
während bislang equals() wirklich nur identische Stellungen als gleich
erkennt, aber keine Permutationen.

Also equals() angepasst. Um das eindeutig zu bekommen, müssen die LSTube
irgendwie eindeutig sortiert werden. Also muss LSTube jetzt Comparable
implementieren. Für LSTube#compareTo(LSTube) ist mir im Moment noch
nichts besseres eingefallen als das Vergleichen von int hashCode(). Mit
dem Ergebnis, dass ich mich jetzt insgesamt 95% der Rechenzeit  in
LSBoard#equals() und LSTube#hashCode() aufhalte. Rechenzeitzunahmen
bislang zwischen 50 und 1500%. Ineffektiv bei der aktuellen
Datenrepräsentation. Ohne grundlegende Änderungen ist der status quo
wohl das beste erreichbare Ergebnis. Und es ist praxistauglich.

Die nächste Idee ist, die Gläser statt eines Vector<Character> durch ein
Bitfeld zu repräsentieren. Mit 31 Farben sollte ich gut hinkommen, das
wären 5 bit, max. 4 Plätze macht 20 bit, das ist gut in ein int
reinzupacken. hashCode() ist dann nur ein Getter für den int. Ich suche
noch effiziente Algorithmen für Stackoperationen auf einem Bitfeld.

Dann denke ich doch nochmal über deine Art nach, Züge zu repräsentieren.
Die beschreibt Reagenzgläser nicht durch ihren Platz, sondern durch
ihren Inhalt. Und du hast völlig recht, dass das bei der Zuggeneration
Zeit spart. Es ist halt „ausgabeunfreundlich“. Im Prinzip sind die
Gläser dann nicht in einer Liste o.ä., sondern in einer Menge. Wenn ich
da mal ne GUI drüberlege, brauche ich noch eine Liste, in der
festgehalten ist, welches Glas auf welchem Platz steht. Das wird
vermutlich in dem Moment lustig, in dem von zwei Gläser gleichen Inhalts
sich mindestens eins verändert ((a,a) (a,a) -> (a) (a,a,a)). Und ich
brauche eine Zuordnung des Zuges (a,a)->(a,a) zu den graphischen
Objekten. Lösbar; die Frage ist halt die nach der Effizienz.

Mit soviel Lerneffekt hatte ich gar nicht gerechnet, als ich angefangen
habe. Und mit Stefan Rams Ansatz, der offensichtlich in nochmal deutlich
kürzerer Zeit eine, aber nicht unbedingt die kürzeste Lösung findet,
habe ich mich noch gar nicht beschäftigt.

Ach ja, die eigentlichen Lerninhalte haben funktioniert: Ich lernte,
dass beim Refactoring eine umfangreiche Suite von Unit-Tests unendlich
hilfreich ist; dass 100% Code-Abdeckung durch Tests kein Fetisch ist;
dass checkstyle mit der gleichen Regeldatei in unterschiedlichen
Umgebungen seltsamerweise unterschiedliche Ergebnisse bringt; und dass
Maven und Jenkins jetzt laufen :-)

Und daher wende ich mich jetzt aktuelleren Aufgaben zu. Der Thread ist
gebookmarked, irgendwann im Wintersemester greife ich das wieder auf.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#12967

Responding to Christian H. Kuhn:

Da Du mit Deinem Projekt soweit erst mal zufrieden scheinst, nur in Kürze...

> Am 23.04.2016 um 14:57 schrieb Patrick Roemer:
>> - Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
>> Gläser zusammengefasst werden.
> 
> Geht halt nicht unbeschränkt. (a,a,a) () ist zwar ideell dasselbe wie ()
> (a,a,a), sieht aber anders aus. Das sind auf dem Screen zwei
> verschiedene Stellungen. Wenn ich die einheitlich repräsentiere, brauche
> ich nicht nur einen Algorithmus, der die tatsächliche Stellung in die
> vereinfachte überführt, sondern auch einen, der sie dann incl. Lösung
> zurücküberführt.

Unterschiedliche Repräsentationen: List für Game/UI, Map für Solver.

Hin: Trivial.
Zurück: Replay der Resultatzugliste auf der List, bei gleichbelegten
Gläsern irgendeins davon wählen.

>> - Vector<Character> durch String ersetzen.
> 
> Ich dachte, veränderliche Dinge sind durch konstante Strings schlecht
> repräsentiert?

Konzeptuell ist da nix veränderlich - eine Stellung und ein Zug
spezifizieren eine andere Stellung.

Auf Implementierungsebene hast Du Vectors mit geboxten Chars, klonst
mühsam alle und modifizierst dann zwei davon. Alternativ könntest Du
alle Stringreferenzen einfach kopieren und dann zwei neue Strings
erzeugen. Was klingt effizienter?

> Ich habe das mal ausprobiert, dass ich keine HashSet<BigInteger>,
> sondern wirklich eine HashSet<LSBoard> verwende. Erster Durchlauf:
> Katastrophe. War im Nachhinein auch klar, denn in bigHashCode() bekommen
> unterschiedliche, aber äquivalente Stellungen den gleichen Hashcode,
> während bislang equals() wirklich nur identische Stellungen als gleich
> erkennt, aber keine Permutationen.

Eventuell ein Zeichen dafür, dass Du für den Solver eine andere
Repräsentation willst - eine, deren #equals()/#hashCode() Du in
#bigHashCode() quasi schon implementiert hast.

> Ach ja, die eigentlichen Lerninhalte haben funktioniert: Ich lernte,
> dass beim Refactoring eine umfangreiche Suite von Unit-Tests unendlich
> hilfreich ist; dass 100% Code-Abdeckung durch Tests kein Fetisch ist;
> dass checkstyle mit der gleichen Regeldatei in unterschiedlichen
> Umgebungen seltsamerweise unterschiedliche Ergebnisse bringt; und dass
> Maven und Jenkins jetzt laufen :-)

Das klingt doch nach einer Erfolgsgeschichte. :)

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12949

Responding to Christian H. Kuhn:

Jetzt habe ich auch noch mal sinnentnehmend gelesen. ;)

> Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
> Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
> geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
> in die Queue getan. While bricht ab, wenn die Queue leer ist.
> 
> In der While-Schleife wird die Stellung und die bisherige Zugliste aus
> der Queue entnommen. Wenn die Stellung eine Lösung ist, wird ein
> Lösungsobjekt aus der Zugliste gebildet und zurückgegeben.

Ob eine Stellung eine Lösung ist, kann man doch schon prüfen, bevor man
sie in die Queue einreiht (und sie im Erfolgsfall direkt zurückgeben).

> Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
> weitergezählt.

Dito: Gesehene Stellungen würde ich vor dem Anhängen an die Queue
rausfiltern. ("Gesehen" bedeutet dann: Ist (oder war schon mal) in der
Queue. Man würde also die neu an die Queue angehängten Kandidaten direkt
in das Set der "gesehenen" Stellungen aufnehmen.)

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12959

Am 23.04.2016 um 16:05 schrieb Patrick Roemer:
>> Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
>> weitergezählt.

Done. 1% schneller.

> Dito: Gesehene Stellungen würde ich vor dem Anhängen an die Queue
> rausfiltern. ("Gesehen" bedeutet dann: Ist (oder war schon mal) in der
> Queue. Man würde also die neu an die Queue angehängten Kandidaten direkt
> in das Set der "gesehenen" Stellungen aufnehmen.)

Hatte ich schon drin. Hatte mich unklar ausgedrückt.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#12920

Stefan Ram wrote:

>   Dabei wird bei jeder neuen Rekursionstiefe von »playonce«
>   die Perspektive gewechselt, um auch die Züge des Gegners zu
>   spielen. Daher ist es in dem untenstehenden Pseudocode 
>   nötig das /Negative/ der Bewertung des nächsten Zuges
>   zu verwenden, weil diese aus der Sicht des /Gegners/ erfolgt.

Klassisches MINIMAX-Verfahren also.

>   Man muß sich auch überlegen, welche Variablen für mehrere
>   Rekursionstiefen geteilt werden können und welche bei
>   jeder Rekursion neu anzulegen sind. Im Zweifelsfalle
>   sollte man alle veränderbaren Zustände bei jeder Rekursion,
>   bei der sie verändert werden könnten, erst einmal
>   als Kopie der vorigen Zustände neu anlegen und dann am
>   Ende des Rekursionsschritts sicherstellen, daß der
>   vorige Zustand wiederhergestellt ist.

In C++ z.B. trivial durch pass by value mit geeignetem copy ctor

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#12921

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Am 09.04.2016 um 21:44 schrieb Stefan Ram:

> http://www.purl.org/stefan_ram/pub/tictactoe_java

Danke, schaue ich mir die Tage mal in Ruhe an.

mfg
QNo

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJXCle7AAoJEGVI2lsCpSdTZlwP/1J4vt76dCtOXlxr3ttJV+41
tMH+8ZyEKB3y6IDdYAXiRBuaFMXW2j5lqxWOODaV7Wq6qHE8wCp2I+xILug6imCU
edWZ2zoDceyGwkfrktAwgR4VFiC1zdZtmI4uwSFQnEDjPqecWOsSA/poi1w8rtF/
0Jwi7ccMuvQ5nUvBnuGfTXRFHe7pfCWQ0A5Svs/KfZgLeL6ztUL65SCcGEv9T2b/
Uhu8l2dA6CXo3XaePDPe6TpqYYa3Y2uP1L2F6GcE1frrqn9PgutreeiWJqxROY7t
Az3e3vK2HP+8NOwjcMxlsMjQ+rfFwTCOAzC07N7OzBTRQuO5oDzhvRvJ7qFPsffW
XQCeDvE+ROb18Mx9w8OIaKcXn5GtstD5JYsT9+yPGtpU1uKcNL4WMLNdbLLSQ60M
qZl8eoUZpVeefmBP+ETjBf88aHfnN3CUI39aFXQ4YeQfpTie/CUy4HrTQIDiXDKh
cJcHUEqV2tHjEff7fTJ6vxjMTBXeu5rM+0YpzwFcMPf+jEdTRjcWjVXURYXom3GB
FNRv0e1dIOUSzzAC/64DxXwZ3qmCNMAdvg6ezpLJM9wNJhyWRPXPAqFzqm5qf7yA
ibgQAHwFTZy5SBj2ndUzCYi463STuQTQ0abf25NykXNCpoqfrxNUj87yIWONrQyF
Ar8KM5jQnpDDIVVy/vUY
=+zCB
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#12926

Responding to Christian H. Kuhn:
> Oder die hashCode-Funktion
> für die Stellungen taugt nix. Den Verdacht hatte ich eh, aber eher in
> die andere Richtung: dass ich für eine neue Stellung den gleichen hash
> habe wie für eine bisherige und deshalb Lösungen nicht finde. Ideal
> wäre eine bijektive hash-Funktion, die aber den Zahlenraum int nicht
> sprengt ...

Ich habe mir gerade spasseshalber mal das Demovideo für das Spielchen
angeschaut. Wenn ich mich nicht verzählt habe, bringen die da ein
Beispiel mit 15 Gläsern zu je 4 "Bewohnern" und 10 Farben. Ich bin nicht
fit genug in Stochastik, um da ad hoc eine sinnvolle Obergrenze für
auszurechnen, aber vom Bauchgefühl her: Kannst Du knicken.

Ich vermute mal, dass Du eh eine Art Breitensuche machen müssen wirst.
Da hast Du zwangsweise schon größere Mengen an Kandidatenzuständen im
Speicher. Ich würde die "bereits gesehenen" Zustände in einem echten
HashSet halten (natürlich mit sinnvoller #hashCode-Implementierung, aber
eben mit #equals-Vergleich bei Übereinstimmung), und Optimierungsenergie
lieber erst mal darauf verwenden, den Suchraum zu minimieren.

Code sollte zunächst mal korrekt sein, und dann erst performant. Wenn Du
Gefahr läufst, eine Lösung nicht zu finden, weil es in einer Sackgasse
vorher mal den selben Hashcode gab, läuft was schief.

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12928

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Am 11.04.2016 um 11:21 schrieb Patrick Roemer:

> [...] eine sinnvolle Obergrenze [...] Kannst Du knicken.
Inzwischen: ACK. Das ist aber kein Grund, es nicht doch zu optimieren :-)

> Ich vermute mal, dass Du eh eine Art Breitensuche machen müssen
> wirst. Da hast Du zwangsweise schon größere Mengen an
> Kandidatenzuständen im Speicher. Ich würde die "bereits gesehenen"
> Zustände in einem echten HashSet halten (natürlich mit sinnvoller
> #hashCode-Implementierung, aber eben mit #equals-Vergleich bei
> Übereinstimmung), und Optimierungsenergie lieber erst mal darauf
> verwenden, den Suchraum zu minimieren.

Siehe <dn4chpF3vqkU1@mid.individual.net>.

Wobei du mich noch auf eine andere Idee bringst: Eine Rekursion darf
tatsächlich auch dann abbrechen, wenn die Stellung bei geringerer
Rechentiefe in einem anderen Zweig des Baumes aufgetaucht ist, nicht
aber, wenn sie im anderen Zweig bei tieferer Suche gefunden wird. Man
könnte statt einem Set eine Map nehmen, bei der zum Hash die
Rechentiefe mit vermerkt wird.

> Code sollte zunächst mal korrekt sein, und dann erst performant.
> Wenn Du Gefahr läufst, eine Lösung nicht zu finden, weil es in
> einer Sackgasse vorher mal den selben Hashcode gab, läuft was
> schief.

Das wir die ursprüngliche Befürchtung, für die ich aber in der Praxis
bisher keine Anzeichen habe. Ich habe einen BigInteger bigHashCode()
gewählt, der die Gläser nach fallender Größe ihres Hashcodes
verarbeitet und so allen Permutationen von Gläsern den gleichen Code
verpasst, und solange maximal 16 Farben und Gläser auftauchen und
nicht mehr als 4 Bewohner in ein Glas passen, müsste diese Funktion
bijektiv sein (jedenfalls wenn man Stellungen als identisch definiert,
wenn sie durch Glaspermutation auseinander entstehen). Und damit
sollte diese Fehlerquelle für eine übersehene Lösung wegfallen.

lg
QNo

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJXDP65AAoJEGVI2lsCpSdT4awP/A2v6HL7z8WHwRR9/u8GdxQK
c33wdQshdeh1NuOTlEGQxGSo9EeF21lOvey24K3dFlfIvgtTkSL3L+s6StqB1EYa
IIvfyF7lJeUT1+YFMRNaldi4HEVbF78ZHtgFA3uK46jyHiT8cxYWjbkRVt9rillq
Dq8kIDTKobS0bQJjL3w+6us6aWgexdurRtKMS7FXogpmQXFIEiWuC37rti7dvzE8
UsoTyLKmyhZcK5D6y3eOx0ZU2JEvfBPV4RJole0afrIbRUrKuKw835PhIeeMZGKk
UO6JCMJ36eAnXkYg7bG+w8U76bTLWUCdDgPsyIADStFRLNRRrMcF1a2ilsxLBJsb
diXYMQ+kj5vH9JIYmbG3HOPK0y4XD5e1Tzfx2LXAPiNHh5MKv2+KU5tADjhmTWZQ
rqrGOpMYwhkIshyPaMMIDLzkJWgHOjeYRd4WhUsb0GEDUICtVuE3nwAuRDuLgiaj
4C9BkdPqCzs7nmKhQbJdIR4qwhVHSRJ1b0puc/iG2dO69j7dAQ1aEtoAmSHF08Py
McbotYKhvmPcQ8CSftHGxispzzn3ApxFgXk2JtdYlYUKesMieoW1kY8eFd5LRSpQ
WmWHD+elDCQr1U5ECUoHTjyIK4DfNOCuNwwIw6yXtJJJg0hwwDHsE5W0fznUsoC8
8U48xHv2/ngXyyfRCkpd
=tnCp
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#12929

Responding to Christian H. Kuhn:
> Am 11.04.2016 um 11:21 schrieb Patrick Roemer:
> 
>> [...] eine sinnvolle Obergrenze [...] Kannst Du knicken.
> Inzwischen: ACK. Das ist aber kein Grund, es nicht doch zu optimieren :-)

Ich meinte damit: Eine bijektive Abbildung auf int kannst Du knicken. Da
gibt's auch nicht wirklich was dran zu optimieren. :)

> Wobei du mich noch auf eine andere Idee bringst: Eine Rekursion darf
> tatsächlich auch dann abbrechen, wenn die Stellung bei geringerer
> Rechentiefe in einem anderen Zweig des Baumes aufgetaucht ist, nicht
> aber, wenn sie im anderen Zweig bei tieferer Suche gefunden wird. Man
> könnte statt einem Set eine Map nehmen, bei der zum Hash die
> Rechentiefe mit vermerkt wird.

Ich halte es einfach für den grundfalschen Ansatz, mit Tiefensuche den
kompletten Zugbaum ablaufen zu wollen. Nimm eine Breitensuche, halte die
Objektrepräsentationen bereits gesehener Stellungen in einem HashSet und
liefere die erste gefundene Lösung zurück. Wenn man bei größeren
Szenarien feststellen sollte, dass durch das HashSet der Speicher
platzt, kann man immer noch schauen, ob und wie man das optimieren kann.

Mit dem Ansatz solltest Du für die einfachen Beispiele aus dem
Trailervideo in den Zehntelsekundenbereich kommen, ganz ohne
Optimierungskapriolen.

>> Code sollte zunächst mal korrekt sein, und dann erst performant.
>> Wenn Du Gefahr läufst, eine Lösung nicht zu finden, weil es in
>> einer Sackgasse vorher mal den selben Hashcode gab, läuft was
>> schief.
> 
> Das wir die ursprüngliche Befürchtung, für die ich aber in der Praxis
> bisher keine Anzeichen habe.

Wie auch - Du hast ja bisher nur sehr überschaubare Szenarien. Und
Hashkollisionen zeichnen sich üblicherweise dadurch aus, dass sie eher
selten auftreten.

> Ich habe einen BigInteger bigHashCode()
> gewählt, der die Gläser nach fallender Größe ihres Hashcodes
> verarbeitet und so allen Permutationen von Gläsern den gleichen Code
> verpasst, und solange maximal 16 Farben und Gläser auftauchen und
> nicht mehr als 4 Bewohner in ein Glas passen, müsste diese Funktion
> bijektiv sein (jedenfalls wenn man Stellungen als identisch definiert,
> wenn sie durch Glaspermutation auseinander entstehen). Und damit
> sollte diese Fehlerquelle für eine übersehene Lösung wegfallen.

Zum einen verstehe ich nicht recht, wo bei einem BigInteger dann noch
das Limit für die Bijektivität herkommen soll, zum anderen wäre die
Frage, wieviel Speicher man damit im Vergleich zu einer kompakten
Repräsentation eines Glases überhaupt noch spart.

Viele Grüße,
Patrick

[toc] | [prev] | [next] | [standalone]

#12931

Am 12.04.2016 um 18:28 schrieb Patrick Roemer:
> Nimm eine Breitensuche, halte die
> Objektrepräsentationen bereits gesehener Stellungen in einem HashSet und
> liefere die erste gefundene Lösung zurück. Wenn man bei größeren
> Szenarien feststellen sollte, dass durch das HashSet der Speicher
> platzt, kann man immer noch schauen, ob und wie man das optimieren kann.
> 
> Mit dem Ansatz solltest Du für die einfachen Beispiele aus dem
> Trailervideo in den Zehntelsekundenbereich kommen, ganz ohne
> Optimierungskapriolen.

Ausprobiert. Stellung: (a,b,c,b), (a,a,c,c), (c,a,b,b), (), (). Das ist
die erste Stellung im einfachsten Level. Die kürzeste Lösung hat 10 Züge.

Erster Ansatz: Wie beim kompletten Baum nur Hashes des aktuellen Zweigs
vorgehalten und verglichen. Lösungszeit 35s.

Zweiter Ansatz: In der Breitensuche muss ich eine Stellung auch dann
nicht mehr prüfen, wenn sie vorher in einem anderen Zweig vorgekommen
ist. Es wird also jede neue Stellung in das HashSet eingetragen.
Lediglich beim Ändern des Suchtiefezählers, nach dem ja von vorne
begonnen wird, wird das HashSet mit den gesehenen Stellungen gelöscht.
Lösungszeit 367ms. Du hast richtig abgeschätzt :-) Jetzt erzeuge ich
immer noch unnötig Stellungen, siehe dein Post mit dem Vorschlag für
andere Zugstruktur. Da muss ich noch drüber nachdenken.

> Zum einen verstehe ich nicht recht, wo bei einem BigInteger dann noch
> das Limit für die Bijektivität herkommen soll, 

Eben. BigInteger garantiert die Bijektivität. Ich will Hashkollisionen
völlig ausschließen.

> zum anderen wäre die
> Frage, wieviel Speicher man damit im Vergleich zu einer kompakten
> Repräsentation eines Glases überhaupt noch spart.

Vermutlich keinen. Der Hash eines Glases besteht aus 4 Bit pro Platz,
jedes Nibble repräsentiert die Belegung eines Platzes von leer bis Farbe
15, aufgefüllt auf 16 Bit. Der Hash einer Stellung multipliziert den
Hash ohne das aktuelle Glas mit 2^16 und addiert den Hash des aktuellen
Glases. Das IST eine kompakte Repräsentation eines Glases. Die
Repräsentation als ArrayList<LSTube> ist redundant und ermöglicht nur
die bessere Zugreifbarkeit. Eine mögliche spätere Version könnte auf die
ArrayList komplett verzichten und LSTube als Sammlung statischer
Methoden auf einer 16Bit-Zahl implementieren.

Beim Auffüllen der Tests auf 100% Abdeckung ist mir noch ein Fall
aufgestoßen, an den ich bisher nicht gedacht hatte. Es gibt Stellungen,
die keine Lösung haben. Beim Durchsuchen des kompletten Baumes ist das
kein Problem. Bei der Breitensuche brauche ich das zusätzliche
Abbruchkriterium, dass die erreichte Suchtiefe kleiner als die maximal
erlaubte ist.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#12964

Responding to Stefan Ram:
>>hffl
>>ldlm
>>fgeg
>>jcbj
>>heib
>>eidb
>>adje
>>jcig
>>amfm
>>dhhk
>>kagl
>>kcka
>>icbm
>>====
>>====
[...]
>   Das Programm kam bei zwei Läufen immer relative schnell bis
>   74 und blieb dann dort stehen. Das könnte bedeuten, daß es
>   vielleicht schon eine optimale Lösung gefunden hat. Da das
>   Programm aber stochastisch arbeitet, kann man das nicht 
>   sicher sagen.

Es sollte in 53 Zügen lösbar sein. Wenn ich nix falsch gemacht habe. ;)

Move(kagl,), Move(hffl,l), Move(amfm,), Move(ldlm,m), Move(ldl,ll),
Move(icbm,mm), Move(eidb,icb), Move(ld,eid), Move(l,lll), Move(kag,),
Move(fgeg,g), Move(jcig,gg), Move(amf,hff), Move(am,mmm), Move(a,ka),
Move(icbb,), Move(heib,b), Move(icb,bb), Move(kcka,kaa), Move(jci,hei),
Move(ic,jc), Move(heii,i), Move(hei,ii), Move(he,fge), Move(dhhk,kck),
Move(dhh,h), Move(dh,hh), Move(eidd,d), Move(eid,dd), Move(ei,iii),
Move(fgee,e), Move(adje,ee), Move(fge,eee), Move(fg,ggg), Move(hfff,f),
Move(hff,ff), Move(hf,fff), Move(h,hhh), Move(jcc,), Move(jc,c),
Move(jcbj,j), Move(jcb,bbb), Move(jc,cc), Move(j,jj), Move(adj,jjj),
Move(ad,ddd), Move(kaaa,a), Move(kaa,aa), Move(ka,aaa), Move(kckk,k),
Move(kck,kk), Move(kc,ccc), Move(k,kkk)

Viele Grüße,
Patrick

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | de.comp.lang.java

csiph-web