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

Groups > de.comp.lang.java > #12931

Re: Rekursion bricht nicht ab

Show all headers | View raw

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

Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web