🚀 go-pugleaf

Passero wrote:
> "John Bokma" <postmaster@castleamber.com> schreef in bericht
> news:Xns95978C98DB168castleamber@130.133.1.4...
> 
>>Passero wrote:
>>
>>>Voor school moeten we voor het vak AI een schuifraam maken die de pc
>>>oplost. We moeten 3 methoden implementeren waaronder 1 blinde en 2
>>>heuristieke.
>>>
>>>Bij mijn blinde methode krijg ik soms volgende fout:
>>>java.lang.OutOfMemoryError
>>>Het rare is dat hij niet uit mijn programma springt en dat ik die
>>>error ook niet kan opvangen. Het is duidelijk dat er geen geheugen
>>>meer vrij is en dat hij daarom moet stoppen. Kan ik dat toch opvangen
>>>zodat ik de gebruiker een bericht kan geven of kan ik het geheugen
>>>aanpassen zodat hij toch verder kan rekenen? Het is mij ook opgevallen
>>>dat hij soms die error geeft ergens tussen stap 257000 en 258000 en
>>>dan een andere keer tussen 256000 en 257000. Hoe komt dat en wat zou
>>>ik eraan kunnen doen?
>>
>>Je algoritme herzien. Wat is je blinde methode?
> 
> 
> Diepte-eerst methode. Dus hij gaat random een beweging genereren,
> controleren of hij die mag doen, stel dat het lege blokje uiterst links
> staat en hij wil links bewegen dan mag hij dat niet. En dat doen tot wanneer
> je de juiste oplossing hebt. Als je op het einde zit keer je 1 knoop terug.
> Het is letterlijk het algoritme uit de cursus dus dat klopt wel degelijk ;)

Een zoekdiepte van 256000 moves? Dan werkt depth-first echt niet.

Waarschijnlijk blijft je algorithme een schuifje heen en weer schuiven.
Nadat hij dat zo'n miljoen keer heeft gedaan, zul je vast wel door je
geheugen heen zijn. En zo niet: dan schuift hij gewoon nog een miljoen
keer op en neer. De kans dat je toevallig de goede oplossing gokt is erg
klein. Depth-first werkt gewoon niet zo goed met onbeperkte zoekruimtes.

Probeer eens iterative deepening. Dat houdt in dat je een limiet aan
de diepte stelt. Als je dan binnen maximale diepte n niets vindt,
dan ga je het opnieuw proberen met (n+1) als maximale diepte.
Dit is in het algemeen een goede tussenvorm tussen geheugengebruik
(dat is veel minder dan breadth-first) en snelheid (die mislukte
diepten kosten niet veel extra tijd vergeleken met de tijd die de
juiste diepte kost en je zoekt nooit te diep).

Een extra optimalisatie is om nooit je vorige zet ongedaan te maken.

Met recursie is dit allemaal erg kort op te schrijven. 20-50 regels
moeten genoeg kunnen zijn voor de kern van je algorithme.

Sjoerd

PS: Heb ik de truk die je zelf had moeten uitvinden verklapt?