Versie van 4 jan 2006 21:25 bewerken LimoWreck (overleg \| bijdragen) uitgebreid bevestigde gebruikers 81.565 bewerkingen kGeen bewerkingssamenvatting ← Oudere bewerking		Versie van 4 jan 2006 21:25 bewerken ongedaan maken LimoWreck (overleg \| bijdragen) uitgebreid bevestigde gebruikers 81.565 bewerkingen kGeen bewerkingssamenvatting Nieuwere bewerking →
Regel 11: Er is echter geen enkele garantie dat het A-algoritme beter presteert dan een eenvoudiger zoekalgoritme. In een omgeving die op een doolhof lijkt, kan bijvoorbeeld de enige weg naar de bestemming zo liggen dat men eerst een stuk zuidwaarts moet gaan eer men een bocht naar het noorden maakt. In dit geval zal het verkennen van de knopen in het noorden, die op de kaart dichter bij de bestemming liggen, aanvankelijk wat tijd kosten. ==Beschrijving== ~~==Overview==~~ A search algorithm that is guaranteed always to find the shortest path to a goal is called ''admissible''. If A uses a [[heuristic (computer science)\|heuristic]] that never overestimates the distance (or in general, the cost) to the goal, A* can be proven to be admissible. A heuristic that makes the A* search admissible is itself called an ''admissible heuristic''. If the estimate simply always returns zero, which is never an overestimate, then A* will effectively perform Dijkstra's algorithm and still find an optimal solution, albeit not as quickly. The best possible heuristic, although usually impractical to compute, is the actual minimal distance to the goal. One example of a practical admissible heuristic is the straight-line distance to the goal on a map. It can be proven that A* considers no more nodes than any other admissible search algorithm, provided that the alternative algorithm does not have a more accurate heuristic estimate. In this sense, A* is the computationally most-efficient algorithm that's guaranteed to find the shortest path. ~~== Description ==~~ Het A-algortime begint in een geselecteerde knoop. Van deze knoop bepaalt men de "kost" om de knoop te bezoeken, voor de initiële knoop is dit gewoonlijk nul. A schat dan de afstand vanaf de huidige knoop tot de bestemming. Deze schatting en de kost worden opgeteld, en vormen de [[heuristiek]] die aan het pad naar deze knoop wordt toegekend. De knoop wordt vervolgens toegevoegd in een [[prioriteitswachtlijn]], die soms "open" genoemd wordt.

A*-algoritme: verschil tussen versies