Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > de.comp.lang.java > #12925
| From | Patrick Roemer <sangamon@netcologne.de> |
|---|---|
| Newsgroups | de.comp.lang.java |
| Subject | Re: Rekursion bricht nicht ab |
| Date | 2016-04-10 22:15 +0200 |
| Organization | news.netcologne.de |
| Message-ID | <neec9f$sgh$1@newsreader4.netcologne.de> (permalink) |
| References | <dmqm4qFkm0hU1@mid.individual.net> <neb2mi$m27$1@newsreader4.netcologne.de> <dmv3g8Fngq5U2@mid.individual.net> |
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
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