Algorithme anytime
# Algorithme anytime

En informatique, un algorithme anytime ("à tout moment") est un algorithme capable de donner une solution valide à un problème même s'il est interrompu avant d'avoir terminé. L'algorithme trouve de meilleures solutions au fur et à mesure de son exécution.

La plupart des algorithmes s'exécutent complètement : ils donnent une seule réponse, après une certaine quantité de calculs. Toutefois, dans certains cas il est souhaitable d'interrompre le traitement avant sa fin normale, par exemple pour réallouer des ressources critiques. Les algorithmes traditionnels ne fournissent alors aucune réponse utilisable. Les algorithmes anytime en revanche donnent une réponse partielle, dont la qualité dépend de la quantité de calculs déjà effectués, et qui est une approximation de la réponse correcte.

## Utilité

Le but des algorithmes anytime est d'être capable de

* produire un résultat à tout moment, sur demande
* produire des résultats de meilleure qualité, en échange de temps de calcul supplémentaire.

Ils sont flexibles en temps et en ressources. Ils sont importants dans le domaine de l'intelligence artificielle pour des problèmes difficiles et longs à calculer, car ils apportent une réponse acceptable en un temps raisonnable. Par exemple, il est crucial pour un système de tir sur cible mouvante d'effectuer ses calculs très rapidement, et même une réponse approchée peut être un progrès significatif à condition qu'elle arrive suffisamment tôt.

Les parcours d'arbres de décision sont friands de la propriété "anytime" : en effet il est souvent trop long, voire impossible, de parcourir l'arbre en entier.

Une particularité des algorithmes anytime est leur faculté de donner plusieurs réponses successives, pour une même donnée d'entrée. On peut mesurer de façon bien définie les progrès réalisés sur les réponses successives, et décider d'allouer ou pas plus de temps pour affiner la solution.

