Path: csiph.com!weretis.net!feeder4.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED!not-for-mail From: Patrick Roemer 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: References: 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: Xref: csiph.com de.comp.lang.java:12925 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