Algoritmo para encontrar un agujero en un gráfico tridimensional infinita

Question

Una vaca está de pie delante de una cerca infinito. Por otro lado está la hierba. La vaca quiere llegar a esta hierba. En algún lugar a lo largo de esta valla es un agujero a través del cual la vaca puede llegar al otro lado. La distancia d de la vaca en el agujero tiene una distribución de probabilidad f (d) asociado con él es decir, la probabilidad de que el agujero es k pasos de la vaca está dada por f (k). Tenga en cuenta que pensamos en todas las distancias como discreta es decir, que siempre se miden en términos de medidas adoptadas por la vaca cow.The puede tomar medidas negativas enteros, así como pasos enteros positivos, es decir k pasos a la izquierda y los pasos a la derecha, respectivamente. Además, sabemos que S (k = -8) ^ 8 | k | ·f (k) <8. Queremos describir un algoritmo que puede encontrar el agujero con probabilidad 1.

Problema 1 ¿Qué es una condición suficiente para que un algoritmo sea capaz de encontrar el agujero con probabilidad 1? Problema 2 Describe tal algoritmo.

Answer 1

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

• cheque de agujero en la posición actual
• caminar hacia adelante 1 paso, cheque de agujero
• caminar hacia atrás 2 pasos, compruebe si hay hoyos
• caminar 3 pasos hacia adelante, cheque de agujero
• caminar hacia atrás 4 pasos, compruebe si hay agujero ...

Este paseo visitará todos los enteros relativos, con probabilidad 1. Por supuesto, lo que realmente quiere es la optimización de la cantidad promedio de pasos que la vaca tendrá que tomar, que es conocido como el búsqueda de partidas problema . La solución es una exponencial 1-dimensional "espiral"; Usted acaba de cambiar la secuencia aritmética 1-2-3-4-5 anterior con el geométrico, multiplicando por 2 cada vez. Es decir:

• cheque de agujero en la posición actual
• caminar hacia adelante paso 1, la comprobación de agujero en cada paso
• caminar hacia atrás 2 pasos, la comprobación de agujero en cada paso
• caminar hacia adelante 4 pasos, la comprobación de 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 la suya a un cruce N-way (sólo tiene dos, "izquierda" y "derecha")

Answer 2

Can todo lo que hace es comprobar si el agujero está en una posición dada? Si es así, parece que lo único que hay que hacer es posiciones de verificación con el fin de disminuir la probabilidad. Se le garantiza a encontrar un agujero, pero se puede tomar un tiempo arbitrariamente largo. (Puede garantizar encontrará un agujero dentro de un cierto número de búsquedas si y sólo si f tiene soporte finito - es decir, si y sólo si hay sólo un número finito de k para el cual f (k)> 0). Si hay un número desconocido de agujeros, que sólo será capaz de determinar que los ha situado todo si f tiene soporte finito.

Por otro lado, si usted puede comprobar para ver si la distancia al agujero es menor que una cierta cantidad especificada, entonces algo así como una búsqueda binaria ponderada por el CDF para f sería probablemente la mejor opción.

Sería útil si se pudiera describir el contexto del problema. Tal como está, el gráfico no parece realmente a entrar en la ecuación -. Sólo hay un montón de copas, y que está tratando de averiguar lo que uno tiene una bola debajo de ella

Answer 3

crear una bala disparada, variables poner sized paredes de por medio intervalled y vea pared wich no se disparó. ir de allí. usted tiene que saber cómo representar gráficamente la función agujero aunque (tal vez una aproximación va a hacer, pero no a 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);
}