Algorithme aléatoire Probabilité Maximisation

Question

Je suis un étudiant en informatique et je suis en train d'étudier pour les finales. Je suis tombé sur un problème qui était un peu hors de propos avec les différents problèmes de type de programmation dynamique. Je résumerai comme ceci:

On me donne un algorithme randomisé efficace, A, qui retourne un ensemble indépendant. Cet algorithme renvoie l'ensemble indépendant maximum avec une probabilité d'au moins 1/(n^3) où n est le nombre de sommets dans le graphe. Suggérer un autre algorithme, en utilisant A, qui renvoie l'ensemble maximum avec une probabilité d'au moins 1/2.

J'ai étudié des algorithmes randomisés, mais cela semble être un simple cas d'implémentation. Si je devais courir A n^3 fois, la probabilité que l'ensemble indépendant maximum soit proche de 1. Puis-je alors dire que l'exécuter n^3/2 donnerait l'effet désiré? Est-ce que j'essaye juste de rendre ceci plus dur? Toute aide est appréciée.

Answer 1

Proche mais pas précis, la probabilité pour l'un des passages de renvoyer la bonne réponse est d'au moins 1/n^3. Cela signifie que la probabilité d'obtenir la mauvaise réponse en une fois est de (1-1/n^3), ce qui signifie que la probabilité d'obtenir la bonne réponse après M s'exécute est 1- (1-1/n^3)^M . Maintenant, rappelez-vous la formule pour e (Wikipedia link), si vous courez n^3 fois, la probabilité est de 1-1/e qui est plus que 1/2 (bien que pas très proche de 1), il est également trivial d'obtenir le nombre exact de courses pour atteindre exactement 1/2 - (n^3) * ln (2).

Answer 2

Je n'ai pas étudié l'ensemble indépendant maximum donc je ne peux pas vous donner trop d'aide. Cependant, vous devez d'abord écrire l'algorithme avant de réclamer le nombre d'heures de fonctionnement.

Si vous exécutez l'algorithme A pour n^3, vous obtenez n^3 ensemble indépendant maximum. Cependant, vous ne devez renvoyer qu'un seul ensemble maximum. Comment trouvez-vous le bon dans ces n^3? Ici vous pouvez vouloir un algorithme de vérification qui manque dans votre question. Selon le problème lui-même (jeu indépendant maximum), il est possible que vous ayez assez d'informations pour trouver le bon jeu indépendant maximum qui nécessite un nombre de fonctionnement beaucoup plus petit que O (n^3).