K plus courts chemins dans Vcsn

From LRDE

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Résumé

Le calcul des K plus courts chemins dans un automate peut être très coûteux, surtout sur des automates énormes comme ceux utilisés en linguistique. Ainsiaprès avoir implémenté l'une des solutions considérée comme l'état de l'art (appelée l'algorithme de Yen) dans Vcsn, l'étape suivante était l'implémentation de la meilleure solution pour ce calcul sur des automates avec des cycles: Eppstein. Ce travail va décrire nos différentes implementations et comparer leurs performances.