Re: Rekursion bricht nicht ab

Path	csiph.com!weretis.net!feeder4.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED!not-for-mail
From	Patrick Roemer <sangamon@netcologne.de>
Newsgroups	de.comp.lang.java
Subject	Re: Rekursion bricht nicht ab
Date	Sun, 10 Apr 2016 22:15:43 +0200
Organization	news.netcologne.de
Lines	46
Distribution	world
Message-ID	<neec9f$sgh$1@newsreader4.netcologne.de> (permalink)
References	<dmqm4qFkm0hU1@mid.individual.net> <neb2mi$m27$1@newsreader4.netcologne.de> <dmv3g8Fngq5U2@mid.individual.net>
NNTP-Posting-Host	xdsl-213-196-254-224.netcologne.de
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8
Content-Transfer-Encoding	8bit
X-Trace	newsreader4.netcologne.de 1460319344 29201 213.196.254.224 (10 Apr 2016 20:15:44 GMT)
X-Complaints-To	abuse@netcologne.de
NNTP-Posting-Date	Sun, 10 Apr 2016 20:15:44 +0000 (UTC)
User-Agent	Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.24) Gecko/20100411 Thunderbird/2.0.0.24 Mnenhy/0.7.6.0
In-Reply-To	<dmv3g8Fngq5U2@mid.individual.net>
Xref	csiph.com de.comp.lang.java:12925

Show key headers only | View raw

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

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