Re: Rekursion bricht nicht ab

From	"Christian H. Kuhn" <qno-news@qno.de>
Newsgroups	de.comp.lang.java
Subject	Re: Rekursion bricht nicht ab
Date	2016-04-23 13:35 +0200
Message-ID	<do150dFc4c5U1@mid.individual.net> (permalink)
References	(3 earlier) <neec9f$sgh$1@newsreader4.netcologne.de> <dn4chpF3vqkU1@mid.individual.net> <nej7v8$29p$1@newsreader4.netcologne.de> <dn7iceFt0j4U1@mid.individual.net> <nenq58$rm$1@newsreader4.netcologne.de>

Show all headers | View raw

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

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