Manning i Klein w rozdziale 3 swojego artykułu pośród proponowanych heurystyk wymieniają m.in.: Możliwość wcześniejszego przygotowania oszacowań dla gramatyki jeżeli nie jest bardzo skomplikowana i przechowywanie ich – złożoność obliczeniowa takiej heurystyki jest na poziomie stałej jeśli pominiemy czas spędzony na przygotowywaniu danych. Stworzenie uproszczonej gramatyki będącej przybliżeniem rozpatrywanej i szacowanie wyników na jej podstawie, co jest dużo szybsze niż analizowanie wyjściowej gramatyki.
Więcej szczegółów na temat tych dwóch heurystyk można znaleźć w punktach 3.1 i 3.2 wspomnianego artykułu.
Efekty Manning i Klein deklarują, że zastosowanie algorytmu A* z opracowanymi przez nich heurystykami dało w rezultacie redukcję liczby odwiedzanych podczas analizowania węzłów nawet do mniej niż 3% dotychczas odwiedzanych przez metody klasyczne („exhaustive parsing”). Dla innych zaproponowanych heurystyk wartość ta wynosiła również po kilka procent.
Przypisy
Bibliografia
Linki zewnętrzne Justin Heyes-Jones A* algorithm tutorial – Tutorial o algorytmie A* Cuneyt Mertayak A Generic C++ A* Library – biblioteka do C++ realizująca algorytm A* A* Search Algorithm in JavaScript (Updated) – Brian Grinstead – strona o implementacji algorytmu A* w JavaScript (link do kodu źródłowego na licencji MIT w treści strony)
Kategoria:Algorytmy grafowe