Waarom is dit belangrijk?
Zoekmethoden kunnen hiermee een beste route kiezen en ondertussen slechtere paden eerder opzij laten liggen. In de robotica maakt dat het plannen van bewegingen mogelijk, zodat een robot de kortste weg naar een doel uitrekent. Op school en op het werk wordt routeplanning daardoor betrouwbaarder, maar de zoektocht blijft soms traag, omdat een zekere uitkomst niet vanzelf een snel antwoord geeft.
Zo werkt het in de praktijk
In commerciële computerspellen zoeken meerdere personages samen een pad over een spelkaart. Ontwikkelaars gebruiken daarvoor een toelaatbare heuristiek die in acht richtingen rekent en obstakels negeert. Onderzoekers meten zulke schattingen op echte spelkaarten.
De University of Alberta en het Alberta Machine Intelligence Institute onderzoeken hoe een computermodel een toelaatbare heuristiek benadert. Zij vergelijken die schatting met patroondatabanken van de Rubiks kubus. De vraag is hoeveel voorbeelden nodig zijn voordat de schatting voor de hele zoekruimte klopt.
Het zoekalgoritme A* koppelt de toelaatbare heuristiek aan de keuze van de volgende stap. Bouwers leiden de schatting af uit een vereenvoudigd probleem of uit een patroondatabank. Die databank bewaart de exacte oplossing van een kleiner deelprobleem.




