Algorithme d'approximation
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
Un algorithme d'approximation calcule une solution approximative d'un problème en un temps raisonable (en général polynomial), mais il se différencie d'une heuristique par le fait qu'il offre en plus un rapport d'approximation que l'on peut prouver.
On distingue deux types d'approximation : sous forme de distance k à l'optimal et sous la forme de rapport ε à l'optimal. Si, pour un problème donné, V est la valeur de la solution exacte et A la valeur de la solution approchée ; on écrira la première A − V = k et la seconde 
.
Il existe deux classes d'algorithmes d'approximation polynomiaux pour le second type de rapport d'approximation : les PTAS (de l'anglais : Polynomial Time Approximation Scheme) et les FPTAS (toujours de l'anglais : Fully Polynomial Time Approximation Scheme). Les premiers ont une complexité temporelle polynomiale en la taille du problème (disons n), par exemple 
alors que les seconds sont polynomiaux en la taille du problème et en la qualité de l'approximation, par exemple 
Les FPTAS sont, en général, meilleurs que les PTAS, au prix d'une complexité spatiale plus importante.
