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-12 15:57 +0200
Message-ID	<dn4d6fF44v0U1@mid.individual.net> (permalink)
References	<dmqm4qFkm0hU1@mid.individual.net> <nefq9s$ofr$1@newsreader4.netcologne.de>

Show all headers | View raw

-----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-----

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