Vervolg van de discussie over zoektechnieken, met bijzondere aandacht voor best first zoeken.

• df: depth first
• iteratief verdiepend zoeken
• bf: breadth first
• zoeken met heuristiek: best first

Taak 1. Je past de best first zoektechniek toe op de graaf met de trans2/trans3 overgangen voor de Soma cubus. Het generieke best first algoritme (uit Bratko) vind je hiernaast. Probleemspecifieke elementen zijn:

• s(Van,Naar,Prijs): bepalen van een gewicht/prijs voor een overgang
• h(Knoop,Schatting): heuristische inschatting van de nog af te leggen weg naar de doelsituatie

Taak 2. Je implementeert de Conway/Guy methode om de 240 soma oplossingen te genereren. Hiernaast in bonuswk8.pl de definitie voor orient/3: orient(Steps,In,Out) geeft de 48 manieren om een stuk van positie In naar Out te brengen. (De iterative deepening methode moet je nog steeds zelf maken.)

Ter vergelijking: het eindproject voor 2009 was een best first regime voor doolhoven. Code voor het genereren en visualiseren van willekeurige perfecte (geen lussen, geen lege plekken) n x m doolhoven vind je hiernaast (maze.pl). Het bestand deep.pl is een testset met 9 x 9 doolhoven waarbij de doelknoop maximaal ver van de startknoop verwijderd is: een simpele bf methode inspecteert dan veel overbodige knopen (deepmazes.pdf visualiseert deze testset).