algorithme d'apprentissage augmenté

Un algorithme d'apprentissage augmenté (également appelé algorithme avec prédictions) est un algorithme qui utilise une prédiction pour améliorer ses performances. Alors que les algorithmes classiques ne prennent en entrée que l'instance du problème, les algorithmes d'apprentissage augmenté acceptent un paramètre supplémentaire. Ce paramètre est souvent une prédiction d'une propriété de la solution. Cette prédiction est ensuite utilisée par l'algorithme pour améliorer son temps d'exécution ou la qualité de son résultat. L'application la plus courante concerne les algorithmes en ligne , où une prédiction sur l'instance incertaine est fournie.

Prédiction d'une solution optimale. La prédiction fournit une solution au problème ou caractérise une solution optimale. Prédiction des données d'entrée. Ceci est principalement utilisé pour les problèmes en ligne . Prédiction des actions algorithmiques. Une prédiction adaptée à un algorithme spécifique qui suggère une exécution spécifique de cet algorithme. Les algorithmes d'apprentissage augmenté satisfont généralement aux trois propriétés suivantes : Cohérence. Un algorithme d'apprentissage augmenté est dit cohérent s'il est possible de démontrer qu'il offre de bonnes performances lorsqu'il est alimenté par une prédiction précise. Régularité. Un algorithme d'apprentissage augmenté est dit régulier si ses performances peuvent être bornées par une fonction de la qualité de la prédiction. Cette qualité peut être mesurée de manière spécifique au problème. On parle alors d'erreur de prédiction. Robustesse. Un algorithme d'apprentissage augmenté est dit robuste si ses performances dans le pire des cas peuvent être bornées même si la prédiction donnée est inexacte. Les algorithmes d'apprentissage augmenté ne prescrivent généralement pas la méthode de prédiction. C'est là que l'apprentissage automatique peut être utilisé. problème de la location de skis Le problème de la pagination pondérée Le problème de la couverture d'ensembles Planification non clairvoyante Le problème d'appariement biparti en ligne

Démarrage à chaud

structures de données

L' algorithme de recherche binaire est un algorithme permettant de trouver les éléments d'une liste triée . Il nécessite n étapes pour trouver un élément ayant une valeur connue dans une liste de longueur n . Avec une prédiction de la position de l'élément , l'algorithme d'apprentissage augmenté suivant peut être utilisé.

Tout d'abord, examinez la position dans la liste. Si elle est nulle , l'élément a été trouvé.
Si , examinez les positions jusqu'à ce qu'un index avec soit trouvé.
Effectuez maintenant une recherche binaire sur .
Si , faites la même chose que dans le cas précédent, mais considérez plutôt .y" $y x_{i} > y$ y

L'erreur est définie comme , où est l'indice réel de . Dans l'algorithme d'apprentissage augmenté, l'exploration des positions prend étapes. Ensuite, une recherche binaire est effectuée sur une liste de taille au plus , ce qui prend étapes. Le temps d'exécution total de l'algorithme est donc . Ainsi, lorsque l'erreur est faible, l'algorithme est plus rapide qu'une recherche binaire classique. Ceci démontre la cohérence de l'algorithme. Même dans le pire des cas, l'erreur sera au plus . L'algorithme effectue alors au plus étapes, ce qui le rend robuste.

Démarrage à chaud

structures de données

Plus d'exemples

Algorithmes d'approximation

Conception de mécanismes