Algorithme de Las Vegas - Las Vegas algorithm

En informatique , un algorithme de Las Vegas est un algorithme aléatoire qui donne toujours des résultats corrects ; c'est-à-dire qu'il produit toujours le résultat correct ou qu'il informe de l'échec. Cependant, le temps d'exécution d'un algorithme de Las Vegas diffère selon l'entrée. La définition habituelle d'un algorithme de Las Vegas inclut la restriction que le temps d' exécution attendu soit fini, où l'espérance est réalisée sur l'espace d'informations aléatoires, ou entropie, utilisé dans l'algorithme. Une définition alternative exige qu'un algorithme de Las Vegas se termine toujours (est efficace ), mais peut générer un symbole ne faisant pas partie de l'espace de solution pour indiquer l'échec de la recherche d'une solution. La nature des algorithmes de Las Vegas les rend appropriés dans des situations où le nombre de solutions possibles est limité, et où vérifier l'exactitude d'une solution candidate est relativement facile tout en trouvant une solution est complexe.

Les algorithmes de Las Vegas sont importants dans le domaine de l' intelligence artificielle et dans d'autres domaines de l'informatique et de la recherche opérationnelle . En IA, les algorithmes de recherche locale stochastique (SLS) sont considérés comme du type Las Vegas. Les algorithmes SLS ont été utilisés pour traiter des problèmes de décision NP-complet et des problèmes d' optimisation combinatoire NP-difficile . Cependant, certaines méthodes de recherche systématique, telles que les variantes modernes de l' algorithme de Davis-Putnam pour la satisfiabilité propositionnelle (SAT), utilisent également des décisions non déterministes et peuvent donc également être considérées comme des algorithmes de Las Vegas.

Histoire

Les algorithmes de Las Vegas ont été introduits par László Babai en 1979, dans le contexte du problème de l'isomorphisme des graphes , en tant que double des algorithmes de Monte Carlo . Babai a introduit le terme « algorithme de Las Vegas » à côté d'un exemple impliquant des lancers de pièces : l'algorithme dépend d'une série de lancers de pièces indépendants, et il y a une petite chance d'échec (aucun résultat). Cependant, contrairement aux algorithmes de Monte Carlo, l'algorithme de Las Vegas peut garantir l'exactitude de tout résultat rapporté.

Exemple

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Comme mentionné ci-dessus, les algorithmes de Las Vegas renvoient toujours des résultats corrects. Le code ci-dessus illustre cette propriété. Une variable k est générée aléatoirement ; une fois k généré, k est utilisé pour indexer le tableau A . Si cet index contient la valeur 1, alors k est renvoyé ; sinon, l'algorithme répète ce processus jusqu'à ce qu'il trouve 1. Bien que cet algorithme de Las Vegas soit garanti pour trouver la bonne réponse, il n'a pas de durée d'exécution fixe ; en raison de la randomisation (à la ligne 3 du code ci-dessus), il est possible qu'un temps arbitrairement long s'écoule avant que l'algorithme ne se termine.

Définition

Cette section fournit les conditions qui caractérisent le fait qu'un algorithme soit de type Las Vegas.

Un algorithme A est un algorithme de Las Vegas pour la classe de problèmes X, si

1. chaque fois que pour une instance de problème donnée x∈X, il renvoie une solution s, s est garanti être une solution valide de x
2. sur chaque instance donnée x, le temps d'exécution de A est une variable aléatoire RT _A,x

Il existe trois notions de complétude pour les algorithmes de Las Vegas :

• des algorithmes complets de Las Vegas peuvent être garantis pour résoudre chaque problème soluble dans le temps d'exécution t max, où t max est une constante dépendante de l'instance.

Soit P(RT _A,x t) la probabilité que A trouve une solution pour une instance soluble x dans le temps dans t, alors A est exactement complet si pour chaque x il existe

un t max tel que P(RT _A,x ≤ t _max ) = 1.

• des algorithmes de Las Vegas approximativement complets résolvent chaque problème avec une probabilité convergeant vers 1 lorsque le temps d'exécution approche l'infini. Ainsi, A est approximativement complet, si pour chaque instance x, lim _t→∞ P(RT _A,x ≤ t) = 1.
• Les algorithmes de Las Vegas essentiellement incomplets sont des algorithmes de Las Vegas qui ne sont pas approximativement complets.

L'exhaustivité approximative présente avant tout un intérêt théorique, car les délais pour trouver des solutions sont généralement trop longs pour être utiles dans la pratique.

Scénarios d'application

Les algorithmes de Las Vegas ont des critères d'évaluation différents en fonction de la configuration du problème. Ces critères sont divisés en trois catégories avec des limites de temps différentes puisque les algorithmes de Las Vegas n'ont pas de complexité temporelle définie. Voici quelques scénarios d'application possibles :

Type 1 : Il n'y a pas de limite de temps, ce qui signifie que l'algorithme s'exécute jusqu'à ce qu'il trouve la solution.

Type 2 : Il y a une limite de temps t _max pour trouver le résultat.

Type 3 : L'utilité d'une solution est déterminée par le temps nécessaire pour trouver la solution.

Notez que les types 1 et 2 sont des cas particuliers du type 3.

Pour le type 1 où il n'y a pas de limite de temps, la durée d'exécution moyenne peut représenter le comportement d'exécution. Ce n'est pas le même cas pour le type 2.

Ici, P ( RT de t _max ), qui est la probabilité de trouver une solution dans le temps, décrit le comportement d' exécution.

Dans le cas du Type 3, son comportement à l'exécution ne peut être représenté que par la fonction de distribution à l'exécution rtd : R → [0,1] définie comme rtd ( t ) = P ( RT ≤ t ) ou son approximation.

La distribution à l'exécution (RTD) est le moyen distinctif de décrire le comportement à l'exécution d'un algorithme de Las Vegas.

Avec ces données, nous pouvons facilement obtenir d' autres critères tels que la moyenne d' exécution, écart - type, médiane, percentiles, ou les probabilités de succès P ( RT ≤ t ) pour arbitraire des délais t .

Applications

Analogie

Les algorithmes de Las Vegas surviennent fréquemment dans les problèmes de recherche . Par exemple, celui qui recherche des informations en ligne peut rechercher les informations souhaitées sur des sites Web connexes. La complexité temporelle va donc d'avoir de la "chance" et de trouver le contenu immédiatement, d'être "malchanceux" et de passer beaucoup de temps. Une fois le bon site Web trouvé, il n'y a aucune possibilité d'erreur.

Tri rapide aléatoire

INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

Un exemple simple est QuickSort randomisé , où le pivot est choisi au hasard et divise les éléments en trois partitions : éléments inférieurs à pivot, éléments égaux à pivot et éléments supérieurs à pivot. Le QuickSort aléatoire nécessite beaucoup de ressources mais génère toujours le tableau trié en tant que sortie.

Il est évident que QuickSort génère toujours la solution, qui dans ce cas le tableau trié. Malheureusement, la complexité temporelle n'est pas si évidente. Il s'avère que le temps d'exécution dépend de l'élément que nous choisissons comme pivot.

• Le pire des cas Θ( n ² ) lorsque le pivot est le plus petit ou le plus grand élément.

${\style d'affichage T(n)=T(0)+T(n-1)+\Thêta (n)}$

${\displaystyle T(n)=\Thêta (1)+T(n-1)+\Thêta (n)}$

${\style d'affichage T(n)=T(n-1)+\Thêta (n)}$

${\displaystyle T(n)=\Thêta (n^{2})}$

• Cependant, grâce à la randomisation, où le pivot est choisi au hasard et correspond exactement à une valeur médiane à chaque fois, le QuickSort peut être effectué dans ( n log n ).

${\style d'affichage T(n)\leq 2*T(n/2)+\Thêta (n)}$

${\displaystyle T(n)=\Thêta (n\log(n))}$

Le temps d'exécution de QuickSort dépend fortement de la façon dont le pivot est sélectionné. Si une valeur de pivot est trop grande ou trop petite, alors la partition sera déséquilibrée. Ce cas donne un mauvais temps d'exécution. Cependant, si la valeur de pivot est proche du milieu du tableau, alors la division sera raisonnablement bien équilibrée. Ainsi, son autonomie sera bonne. Étant donné que le pivot est choisi au hasard, le temps de fonctionnement sera bon la plupart du temps et mauvais occasionnellement.

Dans le cas d'un cas moyen, il est difficile à déterminer car l'analyse ne dépend pas de la distribution d'entrée mais des choix aléatoires que fait l'algorithme. La moyenne de QuickSort est calculée sur tous les choix aléatoires possibles que l'algorithme pourrait faire lors du choix du pivot.

Bien que le temps d'exécution le plus défavorable soit Θ( n ² ), le temps d'exécution moyen est ( n log n ). Il s'avère que le pire des cas n'arrive pas souvent. Pour de grandes valeurs de n , le temps d'exécution est Θ( n log n ) avec une probabilité élevée.

Notez que la probabilité que le pivot soit l'élément de valeur médiane à chaque fois est de un sur n nombres, ce qui est très rare. Cependant, c'est toujours le même temps d'exécution lorsque la division est de 10 à 90 % au lieu de 50 à 50 % car la profondeur de l'arbre de récursivité sera toujours de O (log n ) avec O ( n ) fois pris à chaque niveau de récursivité.

Algorithme glouton aléatoire pour le problème des huit reines

Le problème des huit reines est généralement résolu avec un algorithme de retour en arrière. Cependant, un algorithme de Las Vegas peut être appliqué ; en fait, c'est plus efficace que le retour en arrière.

Placez 8 dames sur un échiquier afin que personne n'en attaque une autre. Rappelez-vous qu'une reine attaque d'autres pièces sur la même ligne, colonne et diagonale.

Supposons que k lignes, 0 k ≤ 8, soient occupées avec succès par des reines.

Si k = 8, alors arrêtez avec succès. Sinon, passez à la ligne k + 1.

Calculez toutes les positions sur cette ligne non attaquées par les reines existantes. S'il n'y en a pas, échouez. Sinon, choisissez-en un au hasard, incrémentez k et répétez.

Notez que les algorithmes échouent simplement si une reine ne peut pas être placée. Mais le processus peut être répété et chaque fois générera un arrangement différent.

Classe de complexité

La classe de complexité des problèmes de décision qui ont des algorithmes de Las Vegas avec un temps d' exécution polynomial attendu est ZPP .

Il se trouve que

${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

ce qui est intimement lié à la façon dont les algorithmes de Las Vegas sont parfois construits. À savoir, la classe RP se compose de tous les problèmes de décision pour lesquels un algorithme aléatoire en temps polynomial existe qui répond toujours correctement lorsque la bonne réponse est "non", mais peut se tromper avec une certaine probabilité limitée à un lorsque la réponse est " Oui". Lorsqu'un tel algorithme existe à la fois pour un problème et son complément (avec les réponses « oui » et « non » interverties), les deux algorithmes peuvent être exécutés simultanément et de façon répétée : exécuter chacun pour un nombre constant d'étapes, à tour de rôle, jusqu'à ce qu'un d'entre eux renvoie une réponse définitive. C'est la méthode standard pour construire un algorithme de Las Vegas qui s'exécute en temps polynomial attendu. Notez qu'en général, il n'y a pas de limite supérieure du pire cas sur le temps d'exécution d'un algorithme de Las Vegas.

Algorithme optimal de Las Vegas

Afin de rendre un algorithme de Las Vegas optimal, le temps d'exécution attendu doit être minimisé. Cela peut être fait par :

1. L'algorithme de Las Vegas A ( x ) s'exécute de manière répétée pour certains nombres t ₁ étapes. Si A ( x ) s'arrête pendant le temps d'exécution, alors A ( x ) est terminé ; sinon, répétez le processus depuis le début pour une autre t ₂ étapes, et ainsi de suite.
2. Concevoir une stratégie optimale parmi toutes les stratégies pour A ( x ), compte tenu des informations complètes sur la distribution de T _A ( x ).

L'existence de la stratégie optimale pourrait être une observation théorique fascinante. Cependant, ce n'est pas pratique dans la vraie vie car il n'est pas facile de trouver l'information de distribution de T _A ( x ). De plus, il ne sert à rien de répéter l'expérience pour obtenir les informations sur la distribution puisque la plupart du temps, la réponse n'est nécessaire qu'une seule fois pour tout x .

Relation avec les algorithmes de Monte Carlo

Les algorithmes de Las Vegas peuvent être comparés aux algorithmes de Monte Carlo , dans lesquels les ressources utilisées sont limitées mais la réponse peut être incorrecte avec une certaine probabilité (généralement faible) . Un algorithme de Las Vegas peut être converti en un algorithme de Monte Carlo en l'exécutant pendant une durée définie et en générant une réponse aléatoire lorsqu'il ne parvient pas à se terminer. Par une application de l'inégalité de Markov , nous pouvons fixer la limite sur la probabilité que l'algorithme de Las Vegas dépasse la limite fixée.

Voici un tableau comparant les algorithmes de Las Vegas et de Monte Carlo :

Si un moyen déterministe de tester l'exactitude est disponible, il est alors possible de transformer un algorithme de Monte Carlo en un algorithme de Las Vegas. Cependant, il est difficile de convertir un algorithme de Monte Carlo en un algorithme de Las Vegas sans un moyen de tester l'algorithme. D'un autre côté, changer un algorithme de Las Vegas en un algorithme de Monte Carlo est facile. Cela peut être fait en exécutant un algorithme de Las Vegas pendant une période de temps spécifique donnée par le paramètre de confiance. Si l'algorithme trouve la solution dans le temps imparti, alors c'est un succès et sinon, la sortie peut simplement être "désolé".

Voici un exemple d'algorithmes de Las Vegas et de Monte Carlo à titre de comparaison :

Supposons qu'il existe un tableau de longueur paire n . La moitié des entrées du tableau sont des 0 et la moitié restante sont des 1. Le but ici est de trouver un index qui contient un 1.

//Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
//Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
return "Failed"

Puisque Las Vegas ne se termine pas tant qu'il n'en trouve pas 1 dans le tableau, il ne joue pas avec l'exactitude mais avec le temps d'exécution. D'un autre côté, Monte Carlo s'exécute 300 fois, ce qui signifie qu'il est impossible de savoir que Monte Carlo trouvera "1" dans le tableau dans les 300 fois de boucles jusqu'à ce qu'il exécute réellement le code. Il peut trouver la solution ou non. Par conséquent, contrairement à Las Vegas, Monte Carlo ne joue pas avec le temps d'exécution mais avec la justesse.

Voir également

• Algorithme de Monte-Carlo
• Algorithme d'Atlantic City
• Aléatoire

Les références

Citations

Sources