Algorithme pour trouver un trou dans un graphe unidimensionnel infini

Question

Une vache se tient devant une clôture infinie. De l'autre côté, il y a de l'herbe. La vache veut aller à cette herbe. Quelque part le long de cette clôture est un trou à travers lequel la vache peut se rendre de l'autre côté. La distance d entre la vache et le trou a une distribution de probabilité f (d) qui lui est associée, c'est-à-dire la probabilité que le trou soit à un pas de la vache est donnée par f (k). Notez que nous considérons toutes les distances comme discrètes, c'est-à-dire qu'elles sont toujours mesurées en termes d'étapes prises par la vache. La vache peut prendre des pas entiers négatifs ainsi que des pas entiers positifs, par exemple k pas vers la gauche et pas vers la droite respectivement. En outre, nous savons que Σ (k = -∞)^∞ | k | ⋅f (k) < ∞. Nous voulons décrire un algorithme qui peut trouver le trou avec la probabilité 1.

Problème 1 Quelle est la condition suffisante pour qu'un algorithme puisse trouver le trou avec la probabilité 1? Problème 2 Décrivez un tel algorithme.

Answer 1

Il me semble que votre problème, comme indiqué, a une solution triviale:

• chèque de trou dans la position actuelle
• marche avant 1 étape, vérifiez trou
• promenade vers l'arrière 2 pas, vérifier le trou
• avancer 3 pas, vérifier le trou
• marche arrière 4 pas, vérifier le trou ...

Cette promenade visitera tous les entiers relatifs, avec une probabilité 1. Bien sûr, ce que vous voulez vraiment est d'optimiser le montant moyen des étapes que la vache devra prendre, ce qui est connu sous le nom search game problem. La solution est une "spirale" exponentielle à 1 dimension; il suffit de remplacer la séquence arithmétique 1-2-3-4-5 ci-dessus par une séquence géométrique, en multipliant par 2 à chaque fois.Soit:

• chèque de trou dans la position actuelle
• marche en avant une étape, la vérification des trous à chaque étape
• marche arrière 2 étapes, la vérification des trous à chaque étape
• marche avant 4 étapes , la vérification de trou à chaque étape
• marche arrière 8 étapes, la vérification des trous à chaque étape ...

Google pour « Le problème Cow-chemin », qui est une généralisation de la vôtre à un carrefour N-way (vous n'en avez que deux, "left" et "right")

Answer 2

Tout ce que vous pouvez faire est de vérifier si le trou est à une position donnée? Si c'est le cas, il semble que la seule chose à faire est de vérifier les positions par ordre décroissant de probabilité. Vous serez assuré de trouver un trou, mais cela peut prendre un temps arbitrairement long. (Vous pouvez garantir que vous trouverez un trou dans un certain nombre de recherches si et seulement si f a un support fini - c'est-à-dire, si seulement il y a un nombre fini de k pour lequel f (k)> 0). S'il y a un nombre inconnu de trous, vous pourrez seulement déterminer que vous les avez tous localisés si f a un support fini. D'autre part, si vous pouvez vérifier si la distance au trou est inférieure à une certaine quantité spécifiée, alors quelque chose comme une recherche binaire pondérée par le CDF pour f serait probablement la meilleure option.

Il serait utile que vous puissiez décrire le contexte du problème. À l'heure actuelle, le graphique ne semble pas vraiment entrer dans l'équation - vous avez juste un tas de coupes, et vous essayez de comprendre lequel a une balle en dessous.

Answer 3

Créez une balle, placez des murs intercalés de tailles variables entre les deux et voyez où le mur n'est pas tiré. continuez à partir de là. vous devez savoir comment tracer la fonction de trou (peut-être une approximation suffira, mais pas un trou sans fin).

Answer 4

findHole(S) 
{ 
    k = 0; 
    previous_k = 0; 

    current_f = f(k, S); 
    if (current_f == 1) return (S); 

    previous_f = 0; 
    //While the probability of finding a hole increases, 
    //we increase k and verify if the vertex at k steps is a hole 
    while (current_f >= previous_f) 
    { 
    previous_f = current_f; 
    previous_k = k; 

    //As closer to probability 1 we are, as smaller steps we make 
    k = (1 - current_f) * MAX_STEP_SIZE; 
    current_f = f(k, S); 
    if (current_f == 1) return (S); 
    } 

    //If we overshot our hole and the probability of finding 
    //a hole at k steps distance has started to decrease, we 
    //perform a binary search within the boundaries of the interval 
    //[previous_k, k], with probabilities in [previous_f, current_f], 
    //having a guarantee that our hole is within this interval 
    return binSearch(previous_k, k, S); 
}