Algoritmo para encontrar el agujero en un gráfico infinito unidimensional

Question

Una vaca está parada frente a una valla infinita. En el otro lado es hierba. La vaca quiere llegar a esta hierba. En algún lugar a lo largo de esta cerca hay un agujero a través del cual la vaca puede llegar al otro lado. La distancia d desde la vaca hasta el hoyo tiene una distribución de probabilidad f (d) asociada a ella, es decir, la probabilidad de que el hoyo esté a unos pasos de la vaca está dada por f (k). Tenga en cuenta que consideramos que todas las distancias son discretas, es decir, que siempre se miden en términos de pasos tomados por la vaca. La vaca puede tomar pasos enteros negativos así como pasos enteros positivos, es decir, k pasos a la izquierda y pasos a la derecha respectivamente. Además, sabemos que Σ (k = -∞)^∞ | k | ⋅f (k) < ∞. Queremos describir un algoritmo que puede encontrar el agujero con la probabilidad 1.

Problema 1 ¿Cuál es una condición suficiente para que un algoritmo pueda encontrar el agujero con la probabilidad 1? Problema 2 Describa dicho algoritmo.

Answer 1

Me parece que su problema, como se ha dicho, tiene una solución trivial:

• cheque por agujero en la posición actual
• caminar hacia adelante 1 paso, comprobar si hay agujero
• paseo 2 pasos hacia atrás, verificar para el agujero
• caminar hacia adelante 3 pasos, verificar para el agujero
• caminar hacia atrás 4 pasos, verificar para el agujero ...

Este paseo visitará todos los enteros relativos, con probabilidad 1. Por supuesto, lo que realmente quiere es optimizar la cantidad promedio de pasos que la vaca tendrá que tomar, lo que se conoce como el search game problem. La solución es una "espiral" exponencial unidimensional; simplemente reemplaza la secuencia aritmética 1-2-3-4-5 anterior con una geométrica, multiplicando por 2 cada vez.Esto es:

• cheque de agujero en la posición actual
• pie hacia adelante 1 paso, la comprobación de agujero en cada paso
• caminar hacia atrás 2 pasos, la comprobación de agujero en cada paso
• pie hacia adelante 4 pasos , revisando el agujero en cada paso
• caminar hacia atrás 8 pasos, la comprobación de agujero en cada paso ...

Google de "La Vaca-Path problema", que es una generalización de los suyos a una encrucijada en N (solo tiene dos, "izquierda" y "derecha")

Answer 2

¿Todo lo que puede hacer es verificar si el agujero está en una posición determinada? Si es así, parece que lo único que se debe hacer es verificar las posiciones en orden decreciente de probabilidad. Se le garantiza que encontrará un agujero, pero puede tomar un tiempo arbitrariamente largo. (Puede garantizar que encontrará un agujero dentro de una determinada cantidad de búsquedas si y solo si f tiene soporte finito, es decir, si solo hay un número finito de k para el cual f (k)> 0). Si hay un número desconocido de agujeros, solo podrá determinar si los ha localizado todos si f tiene soporte finito.

Por otro lado, si puede verificar si la distancia al hoyo es menor que cierta cantidad especificada, entonces algo como una búsqueda binaria ponderada por el CDF para f probablemente sea la mejor opción.

Sería útil si pudiera describir el contexto del problema. Tal como están las cosas, la gráfica realmente no parece entrar en la ecuación: solo tienes un montón de tazas, y estás tratando de descubrir cuál tiene una pelota debajo de ella.

Answer 3

crea una toma de bala, coloca muros de intervalo de tamaño variable entremedio y ve a qué pared no se dispara. seguir desde allí. sin embargo, debes saber cómo representar gráficamente la función del agujero (tal vez una aproximación servirá, pero no para un agujero sin 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); 
}