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

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

Re: Rekursion bricht nicht ab

Show all headers | View raw

In article <nfg4g6$11j$1@newsreader4.netcologne.de>, Patrick Roemer 
(sangamon@netcologne.de) says...

> >> Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung 
habe,
> >> suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
> >> alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
> >> bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
> >> nächsten Version probieren.
> > 
> > An der Stelle ist ein BloomFilter eine interessante Datenstruktur.
> > Ein Bloomfilter kanndir mit Sicherheit sagen, dass er eine bytefolge 
> > noch nie gesehen hat, kann aber fälschlicherweise behaupten, er würde 
> > eine bytefolge schon kennen, auch wenn er sie noch nie gesehen hat.
> > 
> > Kurz, er antwortet so: 
> > Filter, habe ich das schon geprüft? Sicher nicht!
> > Filter, habe ich das schon geprüft? Wahrscheinlich ja.
> 
> Den Hinweis verstehe ich in diesem Kontext nicht.

Jetzt, wo ich den Post nochmal lese, muss ich dir recht geben, dass es 
wohl nicht ganz passt, weil er ja erst tiefer herab steigt, wenn die 
kürzere Tiefe nichts brachte und die Lösung möglicherweise weiter unten 
im Baum liegt.

> Zum anderen will man vermeiden, bereits untersuchte Stellungen noch
> einmal zu durchlaufen. Da bringt ein Bloomfilter aber auch nix. Wenn ich
> eine Stellung sicher nicht gesehen habe, muss ich sie untersuchen. Wenn
> ich eine Stellung wahrscheinlich schon gesehen habe, muss ich sie auch
> untersuchen, denn es könnte ja sein, dass sie doch nicht gesehen wurde,
> und dass es sich um die Stellung handelt, die zur (kürzesten oder gar
> einzigen) Lösung führt. Das war ja genau das Problem mit Christians
> initialem #hashCode()-Ansatz. (Ist ja auch nah verwandt.)

Die Idee beim Filter war eher, dass Bäume, die schon als "tot" erkannt 
wurden, nicht neu durchlaufen werden müssen.
Alles was nicht garantiert tot ist, enthält eine mögliche Lösung.
Bei einem Baum (0 links, 1 rechts)
0000 (keine Lösung)
0001 (keine Lösung)
0010 (keine Lösung)
0011 (keine Lösung)
Würde man sich folgende (Teil-)Bäume im Filter merken können:
0000 
0001 
0010 
0011 
000
001
00 

Nehmen wir an, mit dem Wissen baue ich nun alle möglichen Bäume von 
Grund auf neu auf, so wird der Filter bei "00" sagen: "Kenne ich schon, 
ist tot, such weiter.", also kann man bei 01 starten und spart sich alle 
zuvor genannten Teilbäume.

Aber dummerweise hatte ich übersehen, dass es eine Breitensuche ist, da 
wird halt nicht zuerst 0000 durchlaufen, dann 0001, dann 0010...
(jetzt mal vereinfacht für eine maximale Tiefe von 4), insofern bringt 
das nix.

> Habe ich da was falsch verstanden oder übersehen?

Nein, ich glaube eher, ich habe etwas falsch verstanden.

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]

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