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.
- Auteurs
- Sébastien Piat
- Type
- techreport
- Année
- 2017
- Numéro
- 1701
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.