recursive best-first search).
Zastosowanie Algorytm A* w analizie składniowej PCFG Algorytm A* znajduje zastosowanie w analizie składniowej bezkontekstowych gramatyk probabilistycznych (PCFG) w celu przyspieszenia analizy przy zachowaniu poprawności wyniku – w przeciwieństwie do niektórych metod PCFG, algorytm A* zwróci zawsze drzewo Viterbiego, czyli o maksymalnym możliwym prawdopodobieństwie, w przeciwieństwie do metod „best-first” (w języku polskim pojawiający się czasem pod ogólniejszą nazwą „algorytm zachłanny”) i „finite-beam”, które tego nie gwarantują.
Algorytm A* w tym zastosowaniu zaproponowali Dan Klein i Christopher Manning.
Przykład działania Dla następującej gramatyki:
poprzednik reguła prawdopodobieństwo S S → NPN VP 1 VP VP → V NPA 0,75 VP → V NPA NPG 0,25 V V → schował 1 PP PP → do NPG 1 NPN NPN → NN 0,6 NPN → NN PP 0,4 NPG NPG → NG 0,7 NPG → NG PP 0,3 NPA NPA → NA 0,6 NPA → NA PP 0,4 NN NN → szewc 0,4 NN → pasta 0,3 NN → buty 0,3 NG NG → szewca 0,3 NG → pasty 0,4 NG → butów 0,3 NA NA → szewca 0,25 NA → pastę 0,3 NA → buty 0,45
i zdania „Szewc schował pastę do butów”, użytego jako przykład w artykule probabilistyczna gramatyka bezkontekstowa, w procesie rozbioru zdania trafiamy na jedną niejednoznaczność, więc możliwe scenariusze od tego momentu są następujące:
Plik:ParsePCFG.gif